- 50.50.1: . Let G be a graph in which every vertex has degree 2. Is G necessa...
- 50.50.2: Let T be a tree. Prove that the average degree of a vertex in T is ...
- 50.50.3: There are exactly three trees with vertex set f1; 2; 3g. Note that ...
- 50.50.4: Let d1; d2; : : : ; dn be n 2 positive integers (not necessarily di...
- 50.50.5: Let e be an edge of a graph G. Prove that e is not a cut edge if an...
- 50.50.6: Complete the proof of Theorem 50.4. That is, prove that if G is a g...
- 50.50.7: Prove the following converse to Proposition 50.8: Let T be a tree w...
- 50.50.8: Let T be a tree whose vertices are the integers 1 through n. We cal...
- 50.50.9: Let G be a forest with n vertices and c components. Find and prove ...
- 50.50.10: Prove that a graph is a forest if and only if all of its edges are ...
- 50.50.11: In this problem, you will develop a new proof that every tree with ...
- 50.50.12: Let T be a tree with u; v 2 V .T /, u 6D v, and uv E.T /. Prove tha...
- 50.50.13: Let G be a connected graph with jV .G/j D jE.G/j. Prove that G cont...
- 50.50.14: Prove: a. Every cycle is connected. b. Every cycle is 2-regular. c....
- 50.50.15: Let e be an edge of a graph G. Prove that e is a cut edge if and on...
- 50.50.16: Let G be a graph. A cycle of G that contains all the vertices in G ...
- 50.50.17: Consider the following algorithm. Input: A connected graph G. Outpu...
- 50.50.18: Consider the following algorithm. Input: A connected graph G. Outpu...
- 50.50.19: Let G be a connected graph. The Weiner index of G, denoted W .G/, i...
Solutions for Chapter 50: Trees
Full solutions for Mathematics: A Discrete Introduction | 3rd Edition
Commuting matrices AB = BA.
If diagonalizable, they share n eigenvectors.
A = S-1 AS. A = eigenvalue matrix and S = eigenvector matrix of A. A must have n independent eigenvectors to make S invertible. All Ak = SA k S-I.
Dimension of vector space
dim(V) = number of vectors in any basis for V.
Echelon matrix U.
The first nonzero entry (the pivot) in each row comes in a later column than the pivot in the previous row. All zero rows come last.
Eigenvalue A and eigenvector x.
Ax = AX with x#-O so det(A - AI) = o.
Elimination matrix = Elementary matrix Eij.
The identity matrix with an extra -eij in the i, j entry (i #- j). Then Eij A subtracts eij times row j of A from row i.
Four Fundamental Subspaces C (A), N (A), C (AT), N (AT).
Use AT for complex A.
Invert A by row operations on [A I] to reach [I A-I].
IIA II. The ".e 2 norm" of A is the maximum ratio II Ax II/l1x II = O"max· Then II Ax II < IIAllllxll and IIABII < IIAIIIIBII and IIA + BII < IIAII + IIBII. Frobenius norm IIAII} = L La~. The.e 1 and.e oo norms are largest column and row sums of laij I.
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.
Orthonormal vectors q 1 , ... , q n·
Dot products are q T q j = 0 if i =1= j and q T q i = 1. The matrix Q with these orthonormal columns has Q T Q = I. If m = n then Q T = Q -1 and q 1 ' ... , q n is an orthonormal basis for Rn : every v = L (v T q j )q j •
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.
Reduced row echelon form R = rref(A).
Pivots = 1; zeros above and below pivots; the r nonzero rows of R give a basis for the row space of A.
Saddle point of I(x}, ... ,xn ).
A point where the first derivatives of I are zero and the second derivative matrix (a2 II aXi ax j = Hessian matrix) is indefinite.
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.
Solvable system Ax = b.
The right side b is in the column space of A.
Standard basis for Rn.
Columns of n by n identity matrix (written i ,j ,k in R3).
Trace of A
= sum of diagonal entries = sum of eigenvalues of A. Tr AB = Tr BA.
Vector space V.
Set of vectors such that all combinations cv + d w remain within V. Eight required rules are given in Section 3.1 for scalars c, d and vectors v, w.
Stretch and shift the time axis to create Wjk(t) = woo(2j t - k).