 13.1: Determine the number of forests of order 6.
 13.2: Give an example of a connected graph G that is not a tree such that...
 13.3: It is known that if T is a nontrivial tree and v is a leaf of T , t...
 13.4: Prove that an edge e of a connected graph G is a bridge if and only...
 13.5: Let G be a connected graph that is not a tree containing two distin...
 13.6: Let G be a connected graph of order n 4 and size m such that m = (3...
 13.7: A rooted tree T has maximum degree _(T ) = 4 and height 5. What is ...
 13.8: What is the largest number of vertices of degree 5 that a tree with...
 13.9: What is the maximum number of spanning trees that a connected graph...
 13.10: Construct the binary search tree resulting from the following list ...
 13.11: Give an example of a connected graph G of order 8 or more that is n...
 13.12: A tree T has three vertices of degree 4 and five vertices of degree...
 13.13: The degrees of the vertices of a connected graph G are 5, 5, 4, 4, ...
 13.14: How many edges must be deleted from a 4regular connected graph G o...
 13.15: A certain tree T has three vertices of degree 10 and two vertices o...
 13.16: A tree T of order 52 has only vertices of degree 1, 3 and 5. There ...
 13.17: A tree T of order n is known to satisfy the following properties: (...
 13.18: Suppose that we have a collection of four coins, two authentic and ...
 13.19: Use Kruskals algorithm to find a minimum spanning tree T in the con...
 13.20: Use Prims algorithm to find a minimum spanning tree T in the connec...
 13.21: (a) Show that the 3regular graph K4 contains two spanning trees T1...
 13.22: (a) Let G be a graph of even order n 6, every vertex of which has d...
 13.23: Give an example of three nonisomorphic trees having the same order...
 13.24: Let T be a tree of order n with V (T ) = {v1, v2, . . . , vn} and d...
 13.25: A tree T has k endvertices and vertices of degree 3 where k 2 and ...
 13.26: The degrees of the vertices of a graph G are 2, 2, 2, 1, 1. Which o...
 13.27: A certain nontrivial tree T has order n. Its complement T contains ...
 13.28: It has been noted that there are seven nonisomorphic nontrivial tr...
Solutions for Chapter 13: TREES
Full solutions for Discrete Mathematics  1st Edition
ISBN: 9781577667308
Solutions for Chapter 13: TREES
Get Full SolutionsDiscrete Mathematics was written by and is associated to the ISBN: 9781577667308. This expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Discrete Mathematics, edition: 1. Since 28 problems in chapter 13: TREES have been answered, more than 13784 students have viewed full stepbystep solutions from this chapter. Chapter 13: TREES includes 28 full stepbystep solutions.

Associative Law (AB)C = A(BC).
Parentheses can be removed to leave ABC.

Back substitution.
Upper triangular systems are solved in reverse order Xn to Xl.

Big formula for n by n determinants.
Det(A) is a sum of n! terms. For each term: Multiply one entry from each row and column of A: rows in order 1, ... , nand column order given by a permutation P. Each of the n! P 's has a + or  sign.

Characteristic equation det(A  AI) = O.
The n roots are the eigenvalues of A.

Conjugate Gradient Method.
A sequence of steps (end of Chapter 9) to solve positive definite Ax = b by minimizing !x T Ax  x Tb over growing Krylov subspaces.

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

Eigenvalue A and eigenvector x.
Ax = AX with x#O so det(A  AI) = o.

Fast Fourier Transform (FFT).
A factorization of the Fourier matrix Fn into e = log2 n matrices Si times a permutation. Each Si needs only nl2 multiplications, so Fnx and Fn1c can be computed with ne/2 multiplications. Revolutionary.

Free variable Xi.
Column i has no pivot in elimination. We can give the n  r free variables any values, then Ax = b determines the r pivot variables (if solvable!).

Identity matrix I (or In).
Diagonal entries = 1, offdiagonal entries = 0.

lAII = l/lAI and IATI = IAI.
The big formula for det(A) has a sum of n! terms, the cofactor formula uses determinants of size n  1, volume of box = I det( A) I.

Linear transformation T.
Each vector V in the input space transforms to T (v) in the output space, and linearity requires T(cv + dw) = c T(v) + d T(w). Examples: Matrix multiplication A v, differentiation and integration in function space.

Markov matrix M.
All mij > 0 and each column sum is 1. Largest eigenvalue A = 1. If mij > 0, the columns of Mk approach the steady state eigenvector M s = s > O.

Norm
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.

Pivot columns of A.
Columns that contain pivots after row reduction. These are not combinations of earlier columns. The pivot columns are a basis for the column space.

Similar matrices A and B.
Every B = MI AM has the same eigenvalues as A.

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.

Tridiagonal matrix T: tij = 0 if Ii  j I > 1.
T 1 has rank 1 above and below diagonal.

Unitary matrix UH = U T = UI.
Orthonormal columns (complex analog of Q).

Wavelets Wjk(t).
Stretch and shift the time axis to create Wjk(t) = woo(2j t  k).