|
Icosian Game A century after Euler’s discovery (see Problem 4), another
famous puzzle–this one invented by the renown Irish mathematician Sir William Hamilton (1805-1865)–was presented to the world under the name of the Icosian Game. The game was played on a circular wooden board on which the following graph was carved:  Find a Hamiltonian circuit–a path that visits all the graph’s vertices
exactly once before returning to the starting vertex–for this graph. Hits:
No efficient algorithm for solving this problem for an arbitrary graph is
known. This particular graph does have Hamiltonian circuits which are not difficult to find. (You need to find just one of them.) Solution:
A Hamiltonian circuit is marked on the graph below:
 Think:
Does that mean there exist Hamiltonian circuits if and only if all the vertices have odd degrees? Different with Eulerian circuits and Eulerian paths:
Eulerian circuits and Eulerian paths must walk around the edges,every edges will walked.
But Hamiltonian circuits is just pass the vertices, don't need walk all edges.
|
|
|
