- 12.3.1: In the argument that Euler gave to solve the Konigsberg Bridge (see...
- 12.3.2: Solve the problem dealing with walking through an art exhibit, stat...
- 12.3.3: Prove Theorem 12.43: Let G be a connected graph. Then G has an Eule...
- 12.3.4: Classify each graph or multigraph in Figure 12.49 as containing (a)...
- 12.3.5: Give an example of a graph G of order 6, where (a) G is Eulerian an...
- 12.3.6: Prove or disprove the following. (a) Let G be a multigraph with an ...
- 12.3.7: Let n 3 be an integer. Prove that Cn is Eulerian if and only if n 5...
- 12.3.8: Prove for 1 s t that Ks,t is Eulerian if and only if both s and t a...
- 12.3.9: Prove for n 2, that Qn is Eulerian if and only if n is even.
- 12.3.10: A graph G of order 8 has the property that G v is Eulerian for ever...
- 12.3.11: It is known that every graph of order n 2 contains at least two ver...
- 12.3.12: Suppose that G is an Eulerian graph of order n 3 containing exactly...
- 12.3.13: Let G be a connected graph of order n 6 that has neither an Euleria...
- 12.3.14: Draw K3,4, W5 and P4 + P5.
- 12.3.15: Draw the following: (a) P4 + P4. K3 + K3. K2,3 + K2. (b) P4 P4. K3 ...
- 12.3.16: Draw Q4.
- 12.3.17: What is the order and the size of the n-cube Qn?
- 12.3.18: For an integer n 2, the vertex set of the graph Rn is the set of n-...
- 12.3.19: Let G1, G2 and G3 be pairwise disjoint connected regular graphs and...
- 12.3.20: Let G be an r-regular graph of odd order n and let F = G, where F a...
- 12.3.21: Prove or disprove: There exist two connected graphs G and H both of...
- 12.3.22: Figure 12.50 shows a map of city divided into six land regions, den...
- 12.3.23: Inspector House is investigating the mysterious death of Count Evan...
Solutions for Chapter 12.3: Eulerian Graphs
Full solutions for Discrete Mathematics | 1st Edition
Adjacency matrix of a graph.
Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected). Adjacency matrix of a graph. Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected).
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.
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 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!).
Full row rank r = m.
Independent rows, at least one solution to Ax = b, column space is all of Rm. Full rank means full column rank or full row rank.
Hankel matrix H.
Constant along each antidiagonal; hij depends on i + j.
Krylov subspace Kj(A, b).
The subspace spanned by b, Ab, ... , Aj-Ib. Numerical methods approximate A -I b by x j with residual b - Ax j in this subspace. A good basis for K j requires only multiplication by A at each step.
Left nullspace N (AT).
Nullspace of AT = "left nullspace" of A because y T A = OT.
Linearly dependent VI, ... , Vn.
A combination other than all Ci = 0 gives L Ci Vi = O.
Orthogonal matrix Q.
Square matrix with orthonormal columns, so QT = Q-l. Preserves length and angles, IIQxll = IIxll and (QX)T(Qy) = xTy. AlllAI = 1, with orthogonal eigenvectors. Examples: Rotation, reflection, permutation.
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 •
The diagonal entry (first nonzero) at the time when a row is used in elimination.
Plane (or hyperplane) in Rn.
Vectors x with aT x = O. Plane is perpendicular to a =1= O.
Projection p = a(aTblaTa) onto the line through a.
P = aaT laTa has rank l.
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.
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.
Symmetric matrix A.
The transpose is AT = A, and aU = a ji. A-I is also symmetric.
Unitary matrix UH = U T = U-I.
Orthonormal columns (complex analog of Q).
v + w = (VI + WI, ... , Vn + Wn ) = diagonal of parallelogram.
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.