Question 2.50

20.

  1. The graph below is known as a four spokes and three concentric circles graph. What conditions on and guarantee that an spokes and concentric circles graph has a Hamiltonian circuit? (Assume , .)
    image
  2. The graph below is known as a grid graph. What conditions on and guarantee that an grid graph has a Hamiltonian circuit?
image

Can you think of a real-world situation in which finding a Hamiltonian circuit in an grid graph would represent a solution to the problem? If an grid graph has no Hamiltonian circuit, can you find a tour that repeats a minimum number of vertices and starts and ends at the same vertex?

70