Graph Theory Lessons
Lesson
12: (continued) Hamilton Circuits
Hamilton Circuits
A Hamilton
circuit on a graph G is a circuit that visits each vertex of
G exactly once. It does not have to use every edge of G.
Draw a graph in the left part of the applet below and, if your graph has an
Hamilton circuit, it will be drawn in the right window.
Hamilton circuits
You can consider the Hamilton circuits in a digraph. The applet below will draw Hamilton circuits in a digraph.
Directed Hamilton circuits
To use the Petersen program to get a Hamilton circuit you need to select Properties
and Hamilton Circuit. You will see the circuit traced out on the
graph.
-
Which of the complete graphs Kn
have Hamilton circuits?
-
Which of the platonic graphs have Hamilton circuits?
-
Under what conditions on r and s does
the complete bipartite graph Kr,s have a Hamilton circuit?
It can be quite difficult to prove that a graph does not have a Hamilton
circuit. For example, try to prove that the Petersen graph does not have
a Hamilton circuit. If after 15 minutes you don't have a proof you can
look at a proof here. This is not the only proof.
You can design your own based on those arguments.
n-cubes
We define a one dimensional cube (the
1-cube) as a graph with two vertices and one edge. Recursively, if you
have the (n-1)-cube, you get the n-cube by taking two isomorphic
copies of the (n-1)-cube and adding edges between corresponding
vertices. Thus the 2-cube is a rectangle, the 3-cube is the
usual 3-dimensional cube, and the 4-cube is as shown in figure 18.
|
|
Fig. 18,
The 4-cube.
|
The applet below shows a few more n-cubes.
More n-cubes
e-mail: C.
Mawata
© C. Mawata