 10.1.10.1.1: Which of these graphs are trees?
 10.1.10.1.2: Which of these graphs are trees?
 10.1.10.1.3: Answer these questions about the rooted tree illustrated. a) Which ...
 10.1.10.1.4: Answer the same questions as listed in Exercise 3 for the rooted tr...
 10.1.10.1.5: Is the rooted tree in Exercise 3 a full m ary tree for some positi...
 10.1.10.1.6: Is the rooted tree in Exercise 4 a full m ary tree for some positi...
 10.1.10.1.7: What is the level of each vertex of the rooted tree in Exercise 3?
 10.1.10.1.8: What is the level of each vertex of the rooted tree in Exercise 4?
 10.1.10.1.9: Draw the subtree of the tree in Exercise 3 that is rooted at a) a. ...
 10.1.10.1.10: Draw the subtree ofthe tree in Exercise 4 that is rooted at a) a. b...
 10.1.10.1.11: a) How many nonisomorphic unrooted trees are there with three verti...
 10.1.10.1.12: a) How many nonisomorphic unrooted trees are there with four vertic...
 10.1.10.1.13: a) How many nonisomorphic unrooted trees are there with five vertic...
 10.1.10.1.14: Show that a simple graph is a tree if and only if it is connected, ...
 10.1.10.1.15: Let G be a simple graph with n vertices. Show that G is a tree if a...
 10.1.10.1.16: Which complete bipartite graphs Km,n, where m and n are positive in...
 10.1.10.1.17: How many edges does a tree with 1 0,000 vertices have?
 10.1.10.1.18: How many vertices does a fu1l 5ary tree with 1 00 internal vertice...
 10.1.10.1.19: How many edges does a full binary tree with 1 000 internal vertices...
 10.1.10.1.20: How many leaves does a full 3ary tree with 1 00 vertices have?
 10.1.10.1.21: Suppose 1 000 people enter a chess tournament. Use a rooted tree mo...
 10.1.10.1.22: A chain letter starts when a person sends a letter to five others. ...
 10.1.10.1.23: A chain letter starts with a person sending a letter out to 10 othe...
 10.1.10.1.24: Either draw a full mary tree with 76 leaves and height 3, where m ...
 10.1.10.1.25: Either draw a full mary tree with 84 leaves and height 3, where m ...
 10.1.10.1.26: A full m ary tree T has 81 leaves and height 4. a) Give the upper ...
 10.1.10.1.27: Construct a complete binary tree of height 4 and a complete 3ary t...
 10.1.10.1.28: How many vertices and how many leaves does a complete m ary tree o...
 10.1.10.1.29: Prove a) part (ii) of Theorem 4. b) part (iii) of Theorem 4.
 10.1.10.1.30: Show that a full mary balanced tree of height h has more than m h...
 10.1.10.1.31: How many edges are there in a forest of t trees containing a total ...
 10.1.10.1.32: Explain how a tree can be used to represent the table of contents o...
 10.1.10.1.33: How many different isomers do these saturated hydrocarbons have?
 10.1.10.1.34: What does each of these represent in an organizational tree? a) the...
 10.1.10.1.35: Answer the same questions as those given in Exercise 34 for a roote...
 10.1.10.1.36: a) Draw the complete binary tree with 15 vertices that represents a...
 10.1.10.1.37: Let n be a power of2. Show that n numbers can be added in log n ste...
 10.1.10.1.38: A labeled tree is a tree where each vertex is assigned a label. Two...
 10.1.10.1.39: The eccentricity of a vertex in an unrooted tree is the length ofth...
 10.1.10.1.40: The eccentricity of a vertex in an unrooted tree is the length ofth...
 10.1.10.1.41: The eccentricity of a vertex in an unrooted tree is the length ofth...
 10.1.10.1.42: Show that a center should be chosen as the root to produce a rooted...
 10.1.10.1.43: Show that a tree has either one center or two centers that are adja...
 10.1.10.1.44: Show that every tree can be colored using two colors.
 10.1.10.1.45: Draw the first seven rooted Fibonacci trees.
 10.1.10.1.46: How many vertices, leaves, and internal vertices does the rooted Fi...
 10.1.10.1.47: What is wrong with the following "proof" using mathematical inducti...
 10.1.10.1.48: Show that the average depth of a leaf in a binary tree with n verti...
Solutions for Chapter 10.1: Trees
Full solutions for Discrete Mathematics and Its Applications  6th Edition
ISBN: 9780073229720
Solutions for Chapter 10.1: Trees
Get Full SolutionsSince 48 problems in chapter 10.1: Trees have been answered, more than 35782 students have viewed full stepbystep solutions from this chapter. Chapter 10.1: Trees includes 48 full stepbystep solutions. This expansive textbook survival guide covers the following chapters and their solutions. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073229720. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 6.

Block matrix.
A matrix can be partitioned into matrix blocks, by cuts between rows and/or between columns. Block multiplication ofAB is allowed if the block shapes permit.

Cholesky factorization
A = CTC = (L.J]))(L.J]))T for positive definite A.

Column space C (A) =
space of all combinations of the columns of A.

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.

Covariance matrix:E.
When random variables Xi have mean = average value = 0, their covariances "'£ ij are the averages of XiX j. With means Xi, the matrix :E = mean of (x  x) (x  x) T is positive (semi)definite; :E is diagonal if the Xi are independent.

Determinant IAI = det(A).
Defined by det I = 1, sign reversal for row exchange, and linearity in each row. Then IAI = 0 when A is singular. Also IABI = IAIIBI and

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

Hilbert matrix hilb(n).
Entries HU = 1/(i + j 1) = Jd X i 1 xj1dx. Positive definite but extremely small Amin and large condition number: H is illconditioned.

Kirchhoff's Laws.
Current Law: net current (in minus out) is zero at each node. Voltage Law: Potential differences (voltage drops) add to zero around any closed loop.

Multiplication Ax
= Xl (column 1) + ... + xn(column n) = combination of columns.

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.

Orthogonal subspaces.
Every v in V is orthogonal to every w in W.

Rank one matrix A = uvT f=. O.
Column and row spaces = lines cu and cv.

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 ().

Schur complement S, D  C A } B.
Appears in block elimination on [~ g ].

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

Standard basis for Rn.
Columns of n by n identity matrix (written i ,j ,k in R3).

Sum V + W of subs paces.
Space of all (v in V) + (w in W). Direct sum: V n W = to}.

Symmetric matrix A.
The transpose is AT = A, and aU = a ji. AI is also symmetric.

Vector addition.
v + w = (VI + WI, ... , Vn + Wn ) = diagonal of parallelogram.