Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

196 GRAPH THEORY [CHAP. 8

TRAVELING–SALESMAN PROBLEM

8.73.Apply the nearest-neighbor algorithm to the complete weighted graphGin Fig. 8-68(b)beginning at: (a) vertexA;

(b) vertexB.

8.74. Consider the complete weighted graphGin Fig. 8-57 with 5 vertices.

(a) Beginning at vertexA, list theH=(n− 1 )!/ 2 =12 Hamiltonian circuits ofG, and find the weight of each of

them.

(b) Find a Hamiltonian circuit of minimal weight.

GRAPH ALGORITHMS

8.75.Consider the graphGin Fig. 8-57 (where the vertices are ordered alphabetically).

(a) Find the adjacency structure (AS) ofG.

(b) Using the DFS (depth-first search) Algorithm 8.5 onGand beginning at vertexC, find the STACK sequence

and the order in which the vertices are processed.

(c) Repeat (b) beginning at vertexK.

8.76.Using the BFS (breadth-first search) Algorithm 8.6 on the graphGin Fig. 8-57, find the QUEUE sequence and the

order the vertices are processed beginning at: (a) vertexC; (b) vertexK.

8.77.Repeat Problem 8.75 for the graphGin Fig. 8-65(a).

8.78.Repeat Problem 8.76 for the graphGin Fig. 8-65(a).

8.79.Repeat Problem 8.75 for the graphGin Fig. 8-65(b).

8.80.Repeat Problem 8.76 for the graphGin Fig. 8-65(b).

Answers to Supplementary Problems

8.34. (a) 2, 4, 3, 2, 2, 2, 3, 2; (b)ABL,ABKL,AJ BL,AJ BKL; (c)BLC,BKLC,BAJBLC,BAJBKLC;

(d) 3; (e) 4.

8.35. (a)AJ BA,BKLB,CDMC; (b)B,C,L; (c) only {C,L}.

8.36. (a)E′={BJ,BK,CD}; (b)E′={AJ, CM, LC}; (c)E′={BJ,DM}; (d)E′={KL,LC,CM}, Also, (a) and (b)

are isomorphic, and (a), (b), and (c) are homeomorphic.

8.38. Hint: Consider a maximal simple pathα, and show that its endpoints have degree 1.

8.40. There are five of them, as shown in Fig. 8-69.

Fig. 8-69

8.42. Hint: Use Theorem 8.1.

8.43. First delete all edges inGnot inH, then delete all vertrices inGnot inH.

8.44. (a) Eulerian since all vertices are even:ABCDEACEBDA. (b) None, since four vertices are odd. (c) Euler path

beginning atBand ending atD(or vice versa):BADCBED.