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

190 GRAPH THEORY [CHAP. 8

(b) The adjacency structure ofGappears in Problem 8.30. The following shows the sequence of waiting lists in

QUEUE and the vertices being processed:

QUEUE A DCB DC LKD LK MJ L MJ M 


Vertex AB C D K L J M

In other words the vertices are processed in the order:A,B,C,D,K,L,J,M.

TRAVELING–SALESMAN PROBLEM

8.32.Apply the nearest-neighbor algorithm to the complete weighted graphGin Fig. 8-57 beginning at:

(a) vertexA;(b) vertexD.

Fig. 8-57

(a) Starting atA, the closest vertex isBwith distance 100; fromB, the closest isCwith distance 125; and fromCthe

closest isEwith distance 275. FromEwe must go toDwith distance 75; and finally fromDwe must go back

toAwith distance 150. Accordingly, the nearest-neighbor algorithm beginning atAyields the following weighted

Hamiltonian circuit:

|ABCEDA|= 100 + 125 + 275 + 75 + 150 = 725

(b) Starting atD, we must go toE, thenA, thenBthenCand finally back toD. Accordingly, the nearest-neighbor

algorithm beginning atDyields the following weighted Hamiltonian circuit:

|DEABCD|= 75 + 175 + 100 + 125 + 300 = 775

8.33. Prove Theorem 8.13. The complete graphKnwithn≥3 vertices hasH =(n− 1 )!/2 Hamiltonian

circuits.

The counting convention for Hamiltonian circuits enables us to designate any vertex in a circuit as the starting point.

From the starting point, we can go to anyn−1 vertices, and from there to any one ofn−2 vertices, and so on until

arriving at the last vertex and then returning to the starting point. By the basic counting principle, there are a total of

(n− 1 )(n− 2 )··· 2 · 1 =(n− 1 )!circuits that can be formed from a stating point. Forn≥3, any circuit can be paired

with one in the opposite direction which determines the same Hamiltonian circuit. Accordingly, there are a total of

H=(n− 1 )!/2 Hamiltonian circuits.