 6.1: For the graph shown in Fig. 19, (a) find three different Hamilton c...
 6.2: For the graph shown in Fig. 20, (a) find three different Hamilton c...
 6.3: Find all possible Hamilton circuits in the graph in Fig. 21. Write ...
 6.4: Find all possible Hamilton circuits in the graph in Fig. 22. Write ...
 6.5: For the graph shown in Fig. 23, (a) find a Hamilton path that start...
 6.6: For the graph shown in Fig. 24, (a) find a Hamilton path that start...
 6.7: Suppose D, G, E, A, H, C, B, F, D is a Hamilton circuit in a graph....
 6.8: Suppose G, B, D, C, A, F, E, G is a Hamilton circuit in a graph. (a...
 6.9: Consider the graph in Fig. 25. (a) Find the five Hamilton paths tha...
 6.10: Consider the graph in Fig. 26. (a) Find all the Hamilton circuits i...
 6.11: Consider the graph in Fig. 27. (a) Find all the Hamilton circuits i...
 6.12: Consider the graph in Fig. 28. (a) Find all the Hamilton circuits i...
 6.13: For the graph shown in Fig. 29, (a) find a Hamilton path that start...
 6.14: For the graph shown in Fig. 30, (a) find a Hamilton path that start...
 6.15: Explain why the graph shown in Fig. 31 has neither Hamilton circuit...
 6.16: Explain why the graph shown in Fig. 32 has no Hamilton circuit but ...
 6.17: For the weighted graph shown in Fig. 33, (a) find the weight of edg...
 6.18: For the weighted graph shown in Fig. 34, (a) find the weight of edg...
 6.19: For the weighted graph shown in Fig. 35, (a) find a Hamilton path t...
 6.20: For the weighted graph shown in Fig. 36, (a) find a Hamilton path t...
 6.21: Suppose you have a supercomputer that can generate one billion Hami...
 6.22: Suppose you have a supercomputer that can generate one trillion Ham...
 6.23: a) How many edges are there in K20? (b) How many edges are there in...
 6.24: a) How many edges are there in K200? (b) How many edges are there i...
 6.25: In each case, find the value of N. (a) KN has 120 distinct Hamilton...
 6.26: In each case, find the value of N. (a) KN has 720 distinct Hamilton...
 6.27: Find an optimal tour for the TSP given in Fig. 37, and give its cost.
 6.28: Find an optimal tour for the TSP given in Fig. 38, and give its cost.
 6.29: A truck must deliver furniture to stores located in five different ...
 6.30: A social worker starts from her home A, must visit clients at B, C,...
 6.31: You are planning to visit four cities A, B, C, and D. Table 6 shows...
 6.32: An unmanned rover must be routed to visit four sites labeled A, B, ...
 6.33: Consider a TSP with nine vertices labeled A through I. (a) How many...
 6.34: Consider a TSP with 11 vertices labeled A through K. (a) How many t...
 6.35: For the weighted graph shown in Fig. 41, (i) find the indicated tou...
 6.36: A delivery service must deliver packages at Buckman (B), Chatfield ...
 6.37: The BruteForce Bandits is a rock band planning a fivecity concert...
 6.38: A space mission is scheduled to visit the moons Callisto (C), Ganym...
 6.39: This exercise refers to the furniture truck TSP introduced in Exerc...
 6.40: This exercise refers to the social worker TSP introduced in Exercis...
 6.41: Darren is a sales rep whose territory consists of the six cities in...
 6.42: The Platonic Cowboys are a country and western band based in Nashvi...
 6.43: Find the repetitive nearestneighbor tour (and give its cost) for t...
 6.44: Find the repetitive nearestneighbor tour for the social worker TSP...
 6.45: This exercise is a continuation of Darrens sales trip problem (Exer...
 6.46: This exercise is a continuation of the Platonic Cowboys concert tou...
 6.47: Suppose that in solving a TSP you use the nearestneighbor algorith...
 6.48: Suppose that in solving a TSP you use the nearestneighbor algorith...
 6.49: Find the cheapestlink tour (and give its cost) for the furniture t...
 6.50: Find the cheapestlink tour for the social worker TSP discussed in ...
 6.51: For the BruteForce Bandits concert tour discussed in Exercise 37, ...
 6.52: For the weighted graph shown in Fig. 47, find the cheapestlink tour...
 6.53: For Darrens sales trip problem discussed in Exercise 41, find the c...
 6.54: For the Platonic Cowboys concert tour discussed in Exercise 42, fin...
 6.55: A rover on the planet Mercuria has to visit six sites labeled A thr...
 6.56: A robotic laser must drill holes on five sites (A, B, C, D, and E) ...
 6.57: Suppose that in solving a TSP you find an approximate solution with...
 6.58: Suppose that in solving a TSP you find an approximate solution with...
 6.59: You have a busy day ahead of you. You must run the following errand...
 6.60: In Exercises 60 and 61, you are scheduling a dinner party for six p...
 6.61: In Exercises 60 and 61, you are scheduling a dinner party for six p...
 6.62: If the number of edges in K500 is x and the number of edges in K502...
 6.63: A 2 by 2 grid graph. The graph shown in Fig. 51 represents a street...
 6.64: Find (if you can) a Hamilton circuit in the 2 by 2 grid graph discu...
 6.65: A 3 by 3 grid graph. The graph shown in Fig. 52 represents a street...
 6.66: A 3 by 4 grid graph. The graph shown in Fig. 53 represents a street...
 6.67: Explain why the cheapest edge in any graph is always part of the Ha...
 6.68: (a) Explain why a graph that has a bridge cannot have a Hamilton ci...
 6.69: Nick is a traveling salesman. His territory consists of the 11 citi...
 6.70: . Julie is the marketing manager for a small software company based...
 6.71: Complete bipartite graphs. A complete bipartite graph is a graph wi...
 6.72: m by n grid graphs. An m by n grid graph represents a rectangular s...
 6.73: ores theorem. A connected graph with N vertices is said to satisfy ...
 6.74: diracs theorem. If G is a connected graph with N vertices and deg1X...
Solutions for Chapter 6: The Mathematics of Touring
Full solutions for Excursions in Modern Mathematics  8th Edition
ISBN: 9781292022048
Solutions for Chapter 6: The Mathematics of Touring
Get Full SolutionsThis expansive textbook survival guide covers the following chapters and their solutions. Chapter 6: The Mathematics of Touring includes 74 full stepbystep solutions. This textbook survival guide was created for the textbook: Excursions in Modern Mathematics, edition: 8. Excursions in Modern Mathematics was written by and is associated to the ISBN: 9781292022048. Since 74 problems in chapter 6: The Mathematics of Touring have been answered, more than 11808 students have viewed full stepbystep solutions from this chapter.

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

Affine transformation
Tv = Av + Vo = linear transformation plus shift.

Companion matrix.
Put CI, ... ,Cn in row n and put n  1 ones just above the main diagonal. Then det(A  AI) = ±(CI + c2A + C3A 2 + .•. + cnA nl  An).

Elimination matrix = Elementary matrix Eij.
The identity matrix with an extra eij in the i, j entry (i # j). Then Eij A subtracts eij times row j of A from row i.

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.

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 .

Kronecker product (tensor product) A ® B.
Blocks aij B, eigenvalues Ap(A)Aq(B).

Krylov subspace Kj(A, b).
The subspace spanned by b, Ab, ... , AjIb. 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 inverse A+.
If A has full column rank n, then A+ = (AT A)I AT has A+ A = In.

Linear combination cv + d w or L C jV j.
Vector addition and scalar multiplication.

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

Multiplier eij.
The pivot row j is multiplied by eij and subtracted from row i to eliminate the i, j entry: eij = (entry to eliminate) / (jth pivot).

Normal matrix.
If N NT = NT N, then N has orthonormal (complex) eigenvectors.

Pascal matrix
Ps = pascal(n) = the symmetric matrix with binomial entries (i1~;2). Ps = PL Pu all contain Pascal's triangle with det = 1 (see Pascal in the index).

Random matrix rand(n) or randn(n).
MATLAB creates a matrix with random entries, uniformly distributed on [0 1] for rand and standard normal distribution for randn.

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

Trace of A
= sum of diagonal entries = sum of eigenvalues of A. Tr AB = Tr BA.

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

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.