Problem Set V, for Wednesday, November 7

Mathematics 61

Hamiltonian Cycles and the Traveling Salesperson Problem (page 219 in Discrete Source or page 346 in Discrete Mathematics):
(See Exercise 3 -- which has an answer in the book -- for another example of an argument showing that a graph is not Hamiltonian.)

• Exercise 7.
• Exercise 8.
• Exercise 10.   The example should be a simple graph.
• Exercise 11.
• Exercise 17.   Give the total length of the cycle.   (The traveling salesperson problem is stated on page 215 or 342.   The research literature tends to use the traditional "salesman" term for this problem.)

A Shortest-Path Algorithm (page 224 in Discrete Source or page 351 in Discrete Mathematics):
In the following three exercises, also list the explored (i.e., circled) vertices, in the order in which the algorithm adds them.   Note that doing #2 and #3 together saves some work.

• Exercise 2.
• Exercise 3.
• Exercise 5.

There is a supplementary webpage on Complexity of Decision Problems.

Click here for answers in .pdf format.