 9.4.9.4.1: Does each of these lists of vertices form a path in the following g...
 9.4.9.4.2: Does each of these lists of vertices form a path in the following g...
 9.4.9.4.3: In Exercises 35 determine whether the given graph is connected.
 9.4.9.4.4: In Exercises 35 determine whether the given graph is connected.
 9.4.9.4.5: In Exercises 35 determine whether the given graph is connected.
 9.4.9.4.6: How many connected components does each of the graphs in Exercises ...
 9.4.9.4.7: What do the connected components of acquaintanceship graphs represent?
 9.4.9.4.8: What do the connected components of a collaboration graph represent?
 9.4.9.4.9: Explain why in the collaboration graph of mathematicians a vertex r...
 9.4.9.4.10: In the Hollywood graph (see Example 4 in Section 9. 1 ), when is th...
 9.4.9.4.11: Determine whether each of these graphs is strongly connected and if...
 9.4.9.4.12: Determine whether each of these graphs is strongly connected and if...
 9.4.9.4.13: What do the strongly connected components of a telephone call graph...
 9.4.9.4.14: Find the strongly connected components of each of these graphs. a) ...
 9.4.9.4.15: Find the strongly connected components of each of these graphs. a) b)
 9.4.9.4.16: Show that all vertices visited in a directed path connecting two ve...
 9.4.9.4.17: Find the number of paths oflength n between two different vertices ...
 9.4.9.4.18: Use paths either to show that these graphs are not isomorphic or to...
 9.4.9.4.19: Use paths either to show that these graphs are not isomorphic or to...
 9.4.9.4.20: Use paths either to show that these graphs are not isomorphic or to...
 9.4.9.4.21: Use paths either to show that these graphs are not isomorphic or to...
 9.4.9.4.22: Find the number of paths of length n between any two adjacent verti...
 9.4.9.4.23: Find the number of paths oflength n between any two nonadjacent ver...
 9.4.9.4.24: Find the number of paths between c and d in the graph in Figure 1 o...
 9.4.9.4.25: Find the number of paths from a to e in the directed graph in Exerc...
 9.4.9.4.26: Show that every connected graph with n vertices has at least n  1 ...
 9.4.9.4.27: Let G = (V, E) be a simple graph. Let R be the relation on V consis...
 9.4.9.4.28: Show that in every simple graph there is a path from any vertex of ...
 9.4.9.4.29: In Exercises 293 1 find all the cut vertices of the given graph.
 9.4.9.4.30: In Exercises 293 1 find all the cut vertices of the given graph.
 9.4.9.4.31: In Exercises 293 1 find all the cut vertices of the given graph.
 9.4.9.4.32: Find all the cut edges in the graphs in Exercises 293 1.
 9.4.9.4.33: Suppose that v is an endpoint of a cut edge. Prove that v is a cut ...
 9.4.9.4.34: Show that a vertex c in the connected simple graph G is a cut verte...
 9.4.9.4.35: Show that a simple graph with at least two vertices has at least tw...
 9.4.9.4.36: Show that an edge in a simple graph is a cut edge if and only if th...
 9.4.9.4.37: A communications link in a network should be provided with a backup...
 9.4.9.4.38: Find a vertex basis for each of the directed graphs in Exercises 7...
 9.4.9.4.39: What is the significance of a vertex basis in an influence graph (d...
 9.4.9.4.40: Show that if a connected simple graph G is the union of the graphs ...
 9.4.9.4.41: Show that if a simple graph G has k connected com . ponents and the...
 9.4.9.4.42: Use Exercise 41 to show that a simple graph with n vertices and k c...
 9.4.9.4.43: Show that a simple graph G with n vertices is connected if it has m...
 9.4.9.4.44: Describe the adjacency matrix of a graph with n connected component...
 9.4.9.4.45: How many nonisomorphic connected simple graphs are there with n ver...
 9.4.9.4.46: Explain how Theorem 2 can be used to find the length of the shortes...
 9.4.9.4.47: Use Theorem 2 to find the length of the shortest path between a and...
 9.4.9.4.48: Use Theorem 2 to find the length ofthe shortest path from a to c in...
 9.4.9.4.49: Let P, and P2 be two simple paths between the vertices u and v in t...
 9.4.9.4.50: Show that the existence of a simple circuit of length k, where k is...
 9.4.9.4.51: Explain how Theorem 2 can be used to determine whether a graph is c...
 9.4.9.4.52: Use Exercise 51 to show that the graph G, in Figure 2 is connected ...
 9.4.9.4.53: Show that a simple graph G is bipartite if and only if it has no ci...
 9.4.9.4.54: In an old puzzle attributed to Alcuin of York (735804), a farmer n...
 9.4.9.4.55: Use a graph model and a path in your graph, as in Exercise 54, to s...
 9.4.9.4.56: Suppose that you have a threegallon jug and a fivegallon jug, and...
Solutions for Chapter 9.4: Graphs
Full solutions for Discrete Mathematics and Its Applications  6th Edition
ISBN: 9780073229720
Solutions for Chapter 9.4: Graphs
Get Full SolutionsSince 56 problems in chapter 9.4: Graphs have been answered, more than 35928 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 9.4: Graphs includes 56 full stepbystep solutions. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 6. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073229720.

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

Change of basis matrix M.
The old basis vectors v j are combinations L mij Wi of the new basis vectors. The coordinates of CI VI + ... + cnvn = dl wI + ... + dn Wn are related by d = M c. (For n = 2 set VI = mll WI +m21 W2, V2 = m12WI +m22w2.)

Cofactor Cij.
Remove row i and column j; multiply the determinant by (I)i + j •

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

Diagonalizable matrix A.
Must have n independent eigenvectors (in the columns of S; automatic with n different eigenvalues). Then SI AS = A = eigenvalue matrix.

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.

Four Fundamental Subspaces C (A), N (A), C (AT), N (AT).
Use AT for complex A.

Graph G.
Set of n nodes connected pairwise by m edges. A complete graph has all n(n  1)/2 edges between nodes. A tree has only n  1 edges and no closed loops.

Incidence matrix of a directed graph.
The m by n edgenode incidence matrix has a row for each edge (node i to node j), with entries 1 and 1 in columns i and j .

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

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.

Nilpotent matrix N.
Some power of N is the zero matrix, N k = o. The only eigenvalue is A = 0 (repeated n times). Examples: triangular matrices with zero diagonal.

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 •

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.

Reflection matrix (Householder) Q = I 2uuT.
Unit vector u is reflected to Qu = u. All x intheplanemirroruTx = o have Qx = x. Notice QT = Q1 = Q.

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

Triangle inequality II u + v II < II u II + II v II.
For matrix norms II A + B II < II A II + II B II·

Vandermonde matrix V.
V c = b gives coefficients of p(x) = Co + ... + Cn_IXn 1 with P(Xi) = bi. Vij = (Xi)jI and det V = product of (Xk  Xi) for k > i.

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.

Vector v in Rn.
Sequence of n real numbers v = (VI, ... , Vn) = point in Rn.