Download

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