pptx

Report
Tutorial 5 of CSCI2110
Eulerian Path & Hamiltonian Cycle
Tutor: Zhou Hong (周宏)
[email protected]
About Me
• Name: Zhou Hong (周宏)
• Office: SHB117
• Office Hour: Friday 10:00 am – 12:00 noon
or by appointment
• Topics Responsibility: Graph Theory
Outline
• Eulerian Path
• Hamiltonian Cycle
• Stable Matching
Eulerian Path & Eulerian Cycle
Eulerian Path: a path that visits every edge exactly once
Eulerian Cycle: a cycle that visits every edge exactly once
Exercise: T/F Questions
• A Simple Path is a Path
• A Simple Cycle is a Cycle
• A Simple Cycle is a Simple Path
• A Path is a Cycle
• A Eulerian Cycle is a Eulerian Path
Eulerian Cycle
Euler’s theorem: A connected graph has an Eulerian cycle if and only if
every vertex is of even degree.
Necessary Condition for Eulerian Cycle:
If a connected graph G has an Eulerian cycle, then every vertex in
G is of even degree.
Example:
6
2
1
4
7
3
An Eulerian Cycle:
1 2 3 4 5 6 7 8
5
8
Check that every vertex is of even degree
Eulerian Cycle
Euler’s theorem: A connected graph has an Eulerian cycle if and only if
every vertex is of even degree.
Proof (Eulerian Cycle ⇒ Even Degrees):
• Let G be a connected graph with an Eulerian cycle C, v be
arbitrary vertex in G.
• Every occurrence of v in the Eulerian cycle C will account two
edges adjacent to v.
• Since C use every edge of G exactly once, degree of v must be
even.
1 2 3 4 5 6 7 8
Eulerian Path
Euler’s theorem: A connected graph has an Eulerian path (but not cycle)
if and only if there are two vertices with odd degrees.
Necessary Condition for Eulerian Path:
If a connected graph G has an Eulerian path (but not cycle), then
exactly two vertices in G are of odd degrees.
Example:
6
2
1
4
3
An Eulerian Path:
Check that only
1 2 3 4 5 6 7
5
7
are of odd degrees.
Eulerian Path
Euler’s theorem: A connected graph has an Eulerian path (but not cycle)
if and only if there are two vertices with odd degrees.
Proof (Eulerian Path ⇒ Two vertices of Odd Degrees):
• Let G be a connected graph with an Eulerian path P.
• Every intermediate occurrence of a vertex v in the Eulerian path
P will account two edges adjacent to v.
• If a vertex v occurs as starting or ending point of P, then only
one edge is associated with v.
• Since P use every edge of G exactly once, starting and ending
vertices of P are of odd degrees, all the other vertices have even
degrees.
Eulerian Path
Euler’s theorem: A connected graph has an Eulerian path (but not cycle)
if and only if there are two vertices with odd degrees.
Sufficient Condition for Eulerian Path:
In a connected graph G, if there are exactly two vertices have
odd degrees, then G has an Eulerian Path (but not cycle).
Exercise:
Prove the above Sufficient Condition. (Hint: reduce to Eulerian Cycle)
Eulerian Path
Proof of Sufficient Condition:
• Let the two odd degree vertices in G be u,v.
• Add an edge e between u,v to form a new connected graph G’.
• Now, every vertex in G’ has even degree.
• We have reduced to Eulerian cycle problem, therefore, G’ has an
Eulerian cycle.
• Remove e from the cycle, we get a Eulerian path of G. (u,v are
starting and ending points of the path)
G
G’
u
v
Hamiltonian Path & Hamiltonian Cycle
Hamiltonian Path: a path that visits every vertex exactly once.
Hamiltonian Cycle: a cycle that visits every vertex exactly once
(except for the vertex that is both the start and end).
A Hamiltonian Cycle in a dodecahedron
Hamiltonian Path in Homework 3
Semi-Complete Directed Graph G=(V,A):
∀ u,v ∈ V, either (u,v) ∈ A or (v,u) ∈ A (but not both)
Tips: the following example is similar to
Q3 of HW3, but not the same.
Hamiltonian Cycle in Undirected Graph
Consider the following statement:
If a graph G has n ≥ 3 vertices and degree of each vertex is at least n/2,
then G has a Hamiltonian Cycle.
Do we need to specify that G is connected?
NO
Exercise:
Prove that minimum degree of G is at least n/2 implies G is connected
Key Observation:
Any pair of vertices share at least one common neighbor.
Proof Idea
• Start with a longest simple path P=v1v2...vk.
• We can find a simple cycle C among v1 to vk in graph G.
• If k < n, since G is connected, there must exists a
vertex adjacent to some vertex in the cycle C.
– Which implies we can get a longer simple path through C.
P
v3
v2
v1
v4
v
…
vk-2
vk-1
vk
Find a Simple Cycle
Now, what we need to do is just finding a cycle among v1 to vk. But how?
If there exists a pair of vertices vi and vi+1, such that vi+1 is adjacent to v1
and vi is adjacent to vk, then we can find a cycle C = vi+1vi+2…vkvivi-1…v2v1vi+1.
vi
v2
v1
vi+1
P
…
vk-2
vk-1
vk
Existence of Such Vertex Pair vi and vi+1
• Since P is the longest simple path in G, all neighbors of v1 and vk must be
in P, otherwise P can be extended.
• Proof by contradiction, suppose no desired pair of vertices exists.
– All vertices before (in P) neighbors of v1 are not adjacent to vk
• This implies there are deg(v1) ≥ n/2 vertices in P are not adjacent to
vertex vk. Together with vertices adjacent to vk (≥ n/2) and vk itself,
there are at least n+1 vertices in P, contradiction.
P
v3
v2
v1
v4
…
vk-2
vk-1
vk
Stable Matching
The Marrying Procedure
Morning: boys propose to their favorite girl on list.
If a boy has an empty list already, he stays home
and does his CSC2110 homework.
Afternoon: girls accept their favorite suitor and
reject the rest (possibly breaking up with her
current boyfriend)
Evening: boys who got rejected write off the top girl
from their lists
This procedure is then repeated until all boys
propose to a different girl
Boys Optimal & Girls Pessimal Algorithm
All boys get the best partner simultaneously!
All girls get the worst partner simultaneously!
That is, among all possible stable matching,
boys get the best possible partners simultaneously.
Can a girl do better by lying?
YES!
Girls with True Preference (Day 1)
Boys
Girls
A:213
1:ABC
B:123
2:BAC
C:231
3:CBA
Girls with True Preference (Day 2)
OKAY, marriage day!
Boys
Girls
A:213
1:ABC
B:123
2:BAC
Girl 2 gets her
second best choice
C:231
3:CBA
Girl 2 Tells a Lie (Day 1)
Boys
Girls
A:213
1:ABC
B:123
2:BCA
C:231
3:CBA
Girl 2 Tells a Lie (Day 2)
Boys
Girls
A:213
1:ABC
B:123
2:BCA
C:231
3:CBA
Girl 2 Tells a Lie (Day 3)
Boys
Girls
A:213
1:ABC
B:123
2:BCA
C:231
3:CBA
Girl 2 Tells a Lie (Day 4)
OKAY, marriage day!
Boys
Girls
A:213
1:ABC
B:123
2:BCA
Girl 2 gets her
best choice
C:231
3:CBA
Thank You!
Q&A?

similar documents