Transcript 6.1 Hamilton Circuits and Hamilton Path

6.1 Hamilton Circuits and
Hamilton Path
6.2: Complete Graph
• A Hamilton path is a path that goes
through each vertex of the graph once and
only once.
F, A, B, E, C, G, D is a
Hamilton path
• A Hamilton circuit is a circuit that goes
through each vertex of the graph once and
only once (starting point and ending point
is the same)
F, B, E, C, G, D, A, F is a
Hamilton circuit
Example:
• Identify Euler path, Euler circuit, Hamilton
path, and/or Hamilton circuit
Euler Path
Hamilton Path
No Euler circuit
or path
Hamilton path
Hamilton circuit
• A complete graph with N vertices is a
graph in which every pair of distinct
vertices is joined by an edge. Symbol is KN
• KN has N(N-1) / 2 edges
• Examples:
K3
K3 has 3(2)/2
= 3 edges
K4
4(3)/2 = 6 edges
K6
6(5)/2 = 15 edges
• The number of Hamilton circuits in KN is
(N-1)!
Review Factorials in class
• Example:
This complete graph has 4 vertices so there are
(4-1)! = 3! = 3·2 ·1= 6 Hamilton circuit
Let A be the reference point:
A, B, C, D, A
A, B, D, C, A
A, C, B, D, A
Mirror
A, C, D, B, A
Image
A, D, B, C, A
(same
circuit)
A, D, C, B, A
B
A
D
C
6.3 Traveling Salesman
Problems
• Traveling Salesman problem is a real life
problem that involves Hamilton circuits in
complete graphs
• Examples:
– Routing school buses
– Package deliveries
– Scheduling jobs on a machine
– Running errands around town
– Traveling to many different destinations
• A weighted graph is a graph with
numbers attached to its edges. These
numbers are called weights.
• A complete weighted graph is a
complete graph with weights.
45
70
20
A business man has to travel to 4 different cities and return to his home
town at the end of the trip. The weights of these edges are one-way
airfares between any two cities. A reward is offered to anyone who can
find him the cheapest trip.
Reward??? Hmm,
What is it?