文档介绍：Hamilton Circuits
Hamilton Circuits
Hamilton Paths
Tucker, binatorics, Section , Tamsen Hunter
a
b
c
d
Definition of Hamilton Path: a path that touches every vertex at most once.
Hamilton Circuits
Hamilton Circuits
a
b
c
d
Definition of Hamilton Circuit: a path that touches every vertex at most once and returns to the starting vertex.
Building Hamilton Circuits
Rule 1: If a vertex x has degree 2, both of the edges incident to x must be part of a Hamilton Circuit
a
f
b
h
c
k
i
e
d
j
g
The red lines indicate the vertices with degree two.
Hamilton Circuit
Rule 2: No proper subcircuit, that is, a circuit not containing all vertices, can be formed when building a Hamilton Circuit
c
a
b
d
e
f
g
h
i
Hamilton Circuit
Rule 3: Once the Hamilton Circuit is required to use two edges at a vertex x, all other (unused) edges incident at x can be deleted.
a
f
b
h
c
k
i
e
d
j
g
The red lines indicate the edges that have been removed.
Hamilton Circuits
Applying the Rules One & Two
a
f
b
h
c
k
i
e
d
j
g
Rule One: a and g are vertices of degree 2, both of the edges connected to those 2 vertices must be used.
Rule Two: You must use all of the vertices to make a Hamilton Circuit, leaving out a vertex would not form a circuit.
Hamilton Circuits
Applying the Rule Three
a
f
b
h
c
k
i
e
d
j