Transcript Document

MATH 310, FALL 2003
(Combinatorial Problem
Solving)
Lecture 6, Friday, September 12
2.2 Hamilton Circuits

Homework (MATH 310#2F):
• Read 2.3. Write down a list of all newly introduced terms
(printed in boldface or italic)
• Do Exercises 2.2: 2,4a-g,16,20
• Volunteers:
• ____________
• ____________
• Problem: 16.

On Monday you will also turn in the list of all new terms
with the following marks
• + if you think you do not need the definition on your cheat sheet,
• check (if you need just the term as a reminder),
• - if you need more than just the definition to understand the term.
Hamilton Circuits and Paths


A ciruit that visits
every vertex of a
graph is called a
Hamilton circuit.
A path that visits
every vertex of a
graph is called a
Hamilton path.
The Three Rules



Rule1. If a vertex x has degree 2, both
edges incident to x must be part of any
Hamilton circuit.
Rule 2. No proper subcircuit can be
formed when building a Hamilton circuit.
Rule 3. Once the Hamilton circuit is
required to use two edges at a vertex x,
all other edges incident to x must be
removed from consideration.
Example 1


Show that the
graph on the left
has no Hamilton
circuit.
Hint: Apply Rule 1
four times.
Example 2


Show that the
graph on the left
has no Hamilton
circuit.
Hint: Apply Rule 1
twice and use
symmetry.
Example 3

click

Show that the
graph on the left
has no Hamilton
circuit.
Hint: Apply Rule 1
twice and use
symmetry.
A Useful Result (not from
the textbook)

If a connected
graph G contains k
vertices whose
removal
disconnects G into
more than k
pieces, then G has
no Hamilton
circuit.
Theorem 1 (Dirac, 1952)

A graph with n vertices, n > 2, has a
Hamilton circuit if the degree of
each vertex is at least n/2.
Theorem 2 (Chvatal, 1972)

Let G be a connected graph with n
vertices: x1, x2, ..., xn, so that
deg(x1) · deg(x2) · ... · deg(xn). If
for each k · n/2, either deg(xk) > k
or deg(xn-k) ¸ n – k, then G has a
Hamilton circuit.
Theorem 3 (Grinberg, 1968)

Suppose a plane graph G has a Hamilton
circuit H. Let ri denote the number of
regions inside the Hamilton circuit
bounded by i edges. Let r’i be the number
of regions outside the circuit bounded by i
edges. Then the numbers ri and r’i satisfy
the equation:

(3 - 2)(r3 – r’3) + (4 - 2)(r4 – r’4) + (5 - 2)(r5 – r’5) + ... = 0
Example 4

Here we have:



By Grinberg we should also
have:





(a) r4 + r’4 = 3
(b) r6 + r’6 = 6
(c) 2(r4 – r’4) + 4(r6 – r’6) =
0.
r4  r’4 ) r6  r’6.
Hence |r6 – r’6| ¸ 2.
|r6 – r’6| ¸ 2 \implies |r4 –
r’4| ¸ 4.
Contradiction! The graph in
Figure 2.8 has no Hamilton
circuit.
Tournament

A tournament is a
directed graph
obtained from a
complete graph by
giving a direction
to each edge.
Theorem 4
Every tournament has a (directed)
Hamilton path.
 Proof. By induction on the number of
vertices.

Example 5: Gray Code

Example: n = 3.
There are 8 binary
sequences:








000
001
010
011
100
101
110
111


There are 2n binary
sequences of length
n.
An ordering of 2n
binary sequences with
the property that any
two consecutive
elements differ in
exactly one position is
called a Gray code.
Hypercube



The graph with one
vertex for each n-digit
binary sequence and
an edge joining
vertices that
correspond to
sequences that differ
in just one position is
called an ndimensional cube or
hypercube.
v = 2n
e = n 2n-1
4-dimensional Cube.
0110
0010
0111
0011
1110
1010
1011
1111
0001
1101
1001
0000
0100
1000
1100
4-dimensional Cube and a Famous
Painting by Salvador Dali

Salvador Dali (1904 –
1998) produced in
1954 the Crucifixion
(Metropolitan Museum
of Art, New York) in
which the cross is a
3-dimensional net of
a 4-dimensional
hypercube.
Gray Code - Revisited
010
011

110
100
000
111
101
001
A Hamilton path in
the hypercube
produces a Gray
code.