### pptx

```Tutorial 5 of CSCI2110
Eulerian Path & Hamiltonian Cycle
Tutor: Zhou Hong (周宏)
[email protected]
• 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
• 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
• 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 girls get the worst partner simultaneously!
That is, among all possible stable matching,
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?
```