 10.6.6E: Find the length of a shortest path between these pairs of vertices ...
 10.6.1E: For each of these problems about a subway system, describe a weight...
 10.6.3E: In Exercises 2–4 find the length of a shortest path between a and z...
 10.6.4E: In Exercises 2–4 find the length of a shortest path between a and z...
 10.6.5E: Find a shortest path between a and z in each of the weighted graphs...
 10.6.2E: In Exercises 2–4 find the length of a shortest path between a and z...
 10.6.8E: Find a shortest path (in mileage) between each of the following pai...
 10.6.7E: Find shortest paths in the weighted graph in Exercise 3 between the...
 10.6.9E: Find a combination of flights with the least total air time between...
 10.6.10E: Find a least expensive combination of flights connecting the pairs ...
 10.6.11E: Find a shortest route (in distance) between computer centers in eac...
 10.6.15E: Extend Dijkstra’s algorithm for finding the length of a shortest pa...
 10.6.12E: Find a route with the shortest response time between the pairs of c...
 10.6.16E: Extend Dijkstra’s algorithm for finding the length of a shortest pa...
 10.6.13E: Find a least expensive route, in monthly lease charges, between the...
 10.6.14E: Explain how to find a path with the least number of edges between t...
 10.6.18E: Is a shortest path between two vertices in a weighted graph unique ...
 10.6.17E: The weighted graphs in the figures here show some major roads in Ne...
 10.6.20E: What is the length of a longest simple path in the weighted graph i...
 10.6.19E: What are some applications where it is necessary to find the length...
 10.6.21E: Floyd’s algorithm, displayed as Algorithm 2. can be used to find th...
 10.6.22E: Floyd’s algorithm, displayed as Algorithm 2. can be used to find th...
 10.6.25E: Solve the traveling salesperson problem for this graph by finding t...
 10.6.23E: Floyd’s algorithm, displayed as Algorithm 2. can be used to find th...
 10.6.24E: Show that Dijkstra’s algorithm may not work if edges can have negat...
 10.6.29E: Construct a weighted undirected graph such that the total weight of...
 10.6.30E: Show that the problem of finding a circuit of minimum total weight ...
 10.6.26E: Solve the traveling salesperson problem for this graph by finding t...
 10.6.27E: Find a route with the least total airfare that visits each of the c...
 10.6.28E: Find a route with the least total airfare that visits each of the c...
 10.6.31E: The longest path problem in a weighted directed graph with no simpl...
Solutions for Chapter 10.6: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 10.6
Get Full SolutionsSince 31 problems in chapter 10.6 have been answered, more than 185399 students have viewed full stepbystep solutions from this chapter. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Chapter 10.6 includes 31 full stepbystep solutions. This expansive textbook survival guide covers the following chapters and their solutions.

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

Complex conjugate
z = a  ib for any complex number z = a + ib. Then zz = Iz12.

Ellipse (or ellipsoid) x T Ax = 1.
A must be positive definite; the axes of the ellipse are eigenvectors of A, with lengths 1/.JI. (For IIx II = 1 the vectors y = Ax lie on the ellipse IIA1 yll2 = Y T(AAT)1 Y = 1 displayed by eigshow; axis lengths ad

Fourier matrix F.
Entries Fjk = e21Cijk/n give orthogonal columns FT F = nI. Then y = Fe is the (inverse) Discrete Fourier Transform Y j = L cke21Cijk/n.

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 column rank r = n.
Independent columns, N(A) = {O}, no free variables.

GramSchmidt orthogonalization A = QR.
Independent columns in A, orthonormal columns in Q. Each column q j of Q is a combination of the first j columns of A (and conversely, so R is upper triangular). Convention: diag(R) > o.

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.

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.

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.

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.

Nullspace N (A)
= All solutions to Ax = O. Dimension n  r = (# columns)  rank.

Polar decomposition A = Q H.
Orthogonal Q times positive (semi)definite H.

Pseudoinverse A+ (MoorePenrose inverse).
The n by m matrix that "inverts" A from column space back to row space, with N(A+) = N(AT). A+ A and AA+ are the projection matrices onto the row space and column space. Rank(A +) = rank(A).

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

Rank r (A)
= number of pivots = dimension of column space = dimension of row space.

Rayleigh quotient q (x) = X T Ax I x T x for symmetric A: Amin < q (x) < Amax.
Those extremes are reached at the eigenvectors x for Amin(A) and Amax(A).

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

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.

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