GEN025 2013 Day 22 Quiz 6: Pick up at H113. (Re-/Late) submission (of Quiz 6) will be accepted at Quiz 7 today. Voting for Papers: June 1 – June 7 Resources for Your Study: Math Helpdesk Moodle: Slides, Responses to Comment Sheets, Forum for Questions, Link to my HP containing Old Quizzes and Finals with Solutions 1 Euler Graphs and Hamilton Graphs Euler Graph オイラーグラフ：A graph having a closed path which visits every edge exactly once すべての辺をちょうど一回通る閉路が存在するグラフ Hamilton Graph ハミルトングラフ：A graph having a closed path which visits every vertex exactly once すべての頂点をちょうど一回通る閉路が存在するグラフ 2 Euler Graphs and Hamilton Graphs Euler Graph オイラーグラフ：A graph having a closed path which visits every edge exactly once すべての辺をちょうど一回通る閉路が存在するグラフ ⇔ A connected graph such that every vertex is of even degree 連結で全ての頂点の次数が偶数であるグラフ Hamilton Graph ハミルトングラフ：A graph having a closed path which visits every vertex exactly once すべての頂点をちょうど一回通る閉路が存在するグラフ 3 Seven Bridges of K¨ onigsberg: Find a walk through the city that would cross each bridge once and only once. L. Euler (1875) 4 Seven Bridges of K¨ onigsberg: Find a walk through the city that would cross each bridge once and only once. L. Euler (1875) 5 Room with Seven Doors: A security guard wants to check the security system by passing each door exactly once and returns to the starting point. Is it possible to find such a way for this room. 6 Room with Seven Doors: A security guard wants to check the security system by passing each door exactly once and returns to the starting point. Is it possible to find such a way for this room. 7 Quiz 7, 2010 A B D C F E G H I J K L M (a) Explain that there is a Eulerian path but this is not a Eulerian graph. (b) Add an edge to make the graph to be Eulerian. (c) Find a Hamiltonian circuit of the graph. 8 Theorem 7.3. Γ = (V, E) をハミルトングラフとする。S ⊂ V を Γ の頂点の部分集合とする。∆ を Γ から S を取り除いた（頂点 S と同時に S を含む辺も取り除く）グラフとする。このとき、 ω(∆) ≤ |S| である。(Let Γ = (V, E) be a Hamilton graph and let S ⊂ V . If ∆ is a graph obtained from Γ removing vertices in S and edges with at least one of the ends is in S, then ω(∆) ≤ |S|.) Proof. C を、ハミルトン閉路とすると、C を s 個の連結成分にわけるためには、最低、s 点、取り除かなければならない。従って、 ω(∆) ≤ |S| である。 9 Theorem 7.3. Γ = (V, E) : Hamiltonian ⇒ ∀S ⊆ V, ω(∆(S)) ≤ |S|, where ∆(S) is a graph obtained from Γ removing vertices in S and edges with at least one of the ends is in S ∃S ⊆ V, ω(∆(S)) > |S| ⇒ Γ = (V, E) : not Hamiltonian 10 Quiz 7, 2011. Show that the graph is not Hamiltonian by applying Theorem 7.3. Describe S, ∆, and ω(∆). d a m b c e g f h j i k n l o 11 Quiz 7, 2011. Show that the graph is not Hamiltonian by applying Theorem 7.3. Describe S, ∆, and ω(∆). d d a m a m b c e g f h j i k n l o b e g f h j i k n l o c S = {c, e, h, k, m}. ω(∆) = 6 > 5 = |S| 12 Problem 6 Explain that each of the following three graphs below are not Hamiltonian by applying Theorem 7.3. What is S? Draw ∆. What is ω(∆)? 13 Problem 6 Explain that each of the following three graphs below are not Hamiltonian by applying Theorem 7.3. What is S? Draw ∆. What is ω(∆)? 14 Definition. (復習) 頂点集合 V が X と Y とに分けられ、辺はすべて X の頂点と、Y の頂点からなるとき、(X と Y を部集合とする) 二部グラフ (bipartite graph) という。二部グラフは頂点が 2 色で塗り分けられ、同じ色の頂点同士は隣接していないグラフである。 A graph Γ = (V, E) is called bipartite, if V has a partition into two subsets X and Y such that each edge connects a vertex of X and a vertex of Y . A graph is bipartite if its vertex set can be colored black and white such that no vertices of the same color are adjacent. 15 Example: Problem 3. Black 32 White 30 ∃S ⊆ V, ω(∆(S)) > |S| ⇒ Γ = (V, E) : not Hamiltonian 16 Problem 4 (a). Is the 7 × 7 Knight graph Hamiltonian? 7 × 7 のチェス盤でナイトの動けるところを隣接としたナイトグラフはハミルトングラフか。 White 25 Black 24 ∃S ⊆ V, ω(∆(S)) > |S| ⇒ Γ = (V, E) : not Hamiltonian 17 Problem 4 (c). Is the 4 × n Knight graph Hamiltonian? 4 × n のチェス盤でナイトの動けるところを隣接としたナイトグラフはハミルトングラフか。 n = 10 OW 10 IB 10 OB 10 IW 10 18 Problem 4 (c). Is the 4 × n Knight graph Hamiltonian? 4 × n のチェス盤でナイトの動けるところを隣接としたナイトグラフはハミルトングラフか。 OW 10 n = 10 OB 10 IW 10 ∃S ⊆ V, ω(∆(S)) > |S| ⇒ Γ = (V, E) : not Hamiltonian 19