Problem Set V, for Wednesday, May 6

Mathematics 61, section 1

Hamiltonian Cycles and the Traveling Salesperson Problem:
(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 research literature tends to use the traditional "salesman" term for this problem.)

A Shortest-Path Algorithm:
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.