 15.1: Let S = {1, 2, . . . , n}, where n 2 is an integer, and let f : S S...
 15.2: There are eight students in a graduate computer science class. Each...
 15.3: Let D be a digraph and for each vertex u of D, let R(u) be the set ...
 15.4: (a) Show that the length of a longest directed path in an orientati...
 15.5: Prove or disprove: There exists a 4regular graph G of order 7 and ...
 15.6: Which of the digraphs in Figure 15.42 are tournaments?
 15.7: Let D be a digraph with V (D) = {1, 3, 5, 7, 9, 11} and let A = {4,...
 15.8: Let T be a strong tournament of order 3 or more. Show that if (u, v...
 15.9: Let (u, v) be a directed edge of a tournament T . Show that if od v...
 15.10: Show that a tournament can contain three vertices of outdegree 1 bu...
 15.11: Determine whether the tournaments T1 and T2 in Figure 15.43 are (a)...
 15.12: Determine the minimum number t of arcs that needs to be reversed in...
 15.13: Prove or disprove: If T is a tournament of order n 4 that is not tr...
 15.14: Let T be a tournament of odd order n. Which of the following is tru...
 15.15: Let T be a tournament of even order n. Which of the following is tr...
 15.16: Let T be a tournament of order n 10. Suppose that T contains two ve...
 15.17: What is the largest positive integer k such that for every tourname...
 15.18: Let u and v be two vertices in a tournament T . Prove that if ~d(u,...
 15.19: Let u and v be two vertices in a tournament T . Prove that if u and...
 15.20: A high school class of 28 students is to elect a president of the c...
 15.21: Let T be a nontrivial tournament. Let D be a digraph with V (D) = V...
 15.22: A coloring of the arcs of a strong, aperiodic digraph D with unifor...
 15.23: Figure 15.45 shows a proper coloring of the arcs of a strong, aperi...
Solutions for Chapter 15: DIRECTED GRAPHS
Full solutions for Discrete Mathematics  1st Edition
ISBN: 9781577667308
Solutions for Chapter 15: DIRECTED GRAPHS
Get Full SolutionsDiscrete Mathematics was written by and is associated to the ISBN: 9781577667308. This textbook survival guide was created for the textbook: Discrete Mathematics, edition: 1. Since 23 problems in chapter 15: DIRECTED GRAPHS have been answered, more than 12271 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 15: DIRECTED GRAPHS includes 23 full stepbystep solutions.

Augmented matrix [A b].
Ax = b is solvable when b is in the column space of A; then [A b] has the same rank as A. Elimination on [A b] keeps equations correct.

Basis for V.
Independent vectors VI, ... , v d whose linear combinations give each vector in V as v = CIVI + ... + CdVd. V has many bases, each basis gives unique c's. A vector space has many bases!

Companion matrix.
Put CI, ... ,Cn in row n and put n  1 ones just above the main diagonal. Then det(A  AI) = ±(CI + c2A + C3A 2 + .•. + cnA nl  An).

Condition number
cond(A) = c(A) = IIAIlIIAIII = amaxlamin. In Ax = b, the relative change Ilox III Ilx II is less than cond(A) times the relative change Ilob III lib II· Condition numbers measure the sensitivity of the output to change in the input.

Cramer's Rule for Ax = b.
B j has b replacing column j of A; x j = det B j I det A

Dimension of vector space
dim(V) = number of vectors in any basis for V.

Dot product = Inner product x T y = XI Y 1 + ... + Xn Yn.
Complex dot product is x T Y . Perpendicular vectors have x T y = O. (AB)ij = (row i of A)T(column j of B).

Free columns of A.
Columns without pivots; these are combinations of earlier columns.

Linearly dependent VI, ... , Vn.
A combination other than all Ci = 0 gives L Ci Vi = O.

Normal equation AT Ax = ATb.
Gives the least squares solution to Ax = b if A has full rank n (independent columns). The equation says that (columns of A)·(b  Ax) = o.

Nullspace matrix N.
The columns of N are the n  r special solutions to As = O.

Plane (or hyperplane) in Rn.
Vectors x with aT x = O. Plane is perpendicular to a =1= O.

Positive definite matrix A.
Symmetric matrix with positive eigenvalues and positive pivots. Definition: x T Ax > 0 unless x = O. Then A = LDLT with diag(D» O.

Projection matrix P onto subspace S.
Projection p = P b is the closest point to b in S, error e = b  Pb is perpendicularto S. p 2 = P = pT, eigenvalues are 1 or 0, eigenvectors are in S or S...L. If columns of A = basis for S then P = A (AT A) 1 AT.

Random matrix rand(n) or randn(n).
MATLAB creates a matrix with random entries, uniformly distributed on [0 1] for rand and standard normal distribution for randn.

Rotation matrix
R = [~ CS ] rotates the plane by () and R 1 = RT rotates back by (). Eigenvalues are eiO and eiO , eigenvectors are (1, ±i). c, s = cos (), sin ().

Row space C (AT) = all combinations of rows of A.
Column vectors by convention.

Semidefinite matrix A.
(Positive) semidefinite: all x T Ax > 0, all A > 0; A = any RT R.

Singular Value Decomposition
(SVD) A = U:E VT = (orthogonal) ( diag)( orthogonal) First r columns of U and V are orthonormal bases of C (A) and C (AT), AVi = O'iUi with singular value O'i > O. Last columns are orthonormal bases of nullspaces.

Spanning set.
Combinations of VI, ... ,Vm fill the space. The columns of A span C (A)!