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?