グラフ理論 講義ノート #5
井上 純一
北海道大学 大学院情報科学研究科
URL : http://chaosweb.complex.eng.hokudai.ac.jp/˜j inoue/

平成 19 年 5 月 21 日

目次
6

6.1

77
オイラー・グラフ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6.2

ハミルトン・グラフ

オイラー・グラフとハミルトン・グラフ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

演習問題 4 の解答例
前回 演習問題 3 は計算量の多い問題だったので, 今回の演習問題では証明を 2 つ試みてもらった.

(1) グラフ G に存在する全ての点集合 V (G) を奇数次, 偶数次の部分集合: Vodd = {u | deg(u) が奇数 },Veven = {u | deg(u) が偶数 } に分ける. このとき, 与えられた関係式は2(G) =

deg(u) +u∈Vodddeg(u)(129)u∈Vevenと書けるが, 明らかに, 上式のうちの 2(G) と u∈Veven deg(u) は偶数である. 従って, 上関係式の両辺の偶奇を合わせるために u∈Vodd deg(u) は偶数でなければならないが, この和の中の各要素 deg(u)が奇数であることを考えれば, この和に現れる各要素の総数は偶, すなわち, 次数が奇数である点は偶数個なければならない. 従って, 『任意のグラフ G において, 次数が奇数である点の個数は必ず偶数個ある』ことが示された.

(2) グラフ G の点の数を n とする. このとき, G が単純グラフであれば, 明らかに G の可能な最大次数はn − 1 である. 従って, もし, n 点すべての次数が異なると仮定すると, それらの次数は 0, 1, 2, · · · , n − 1となるが, 明らかに次数 0 の点と可能な最大次数 n − 1 の点がグラフ G 中に共存することはできない.
従って, 『単純グラフ G の点の個数が 2 以上ならば, G には必ず同じ次数を持つ 2 つの点が存在する』
ことが示せた.

6

オイラー・グラフとハミルトン・グラフ
ここでは情報工学的に応用される場面も多いオイラー・グラフとハミルトン・グラフについて学ぶ.

77グラフ理論 2007 #5

6.1

北海道大学 大学院情報科学研究科 井上純一

オイラー・グラフ

オイラー・グラフ (Eulerian graph) : 全ての辺を含む閉じた小道がある連結グラフ.
半オイラー・グラフ (semi-Eulerian graph) : 全ての辺を含む小道がある連結グラフ (閉じていない).

Eulerian graphSemi-Eulerian graph

図 89: オイラー・グラフ (左) と半オイラー・グラフ (右) の一例.
定理 6.2連結グラフ G がオイラー・グラフとなる必要十分条件は G の点の次数が全て偶数であることである.

(証明)⇒ (必要性)G のオイラー小道 P がある一点を通過する毎に 2 を加えていくと, 全ての辺はちょうど 1 回ずつ含まれるので, 各点でこの和はその点の次数に等しく, しかも, それは偶数である.
⇐ (十分性)
各点の次数は偶数であり, かつ, 連結であるとすると, 教科書 p. 43 補題 6.1 より, この連結グラフ G には閉路 C がある. 従って, このもとでオイラー・グラフとして G が構成できればよい. つまり, このもとで具体的なオイラー・グラフの構成法を提示すれば証明は終了である.
さて, 自明であるが, 閉路 C に G の全ての点が含まれていれば, その閉路そのものがオイラー・グラフとなるので証明は終了する. 従って, 以下ではこれ以外のケースに対して, オイラー・グラフの構成法を提示
する.
まず, 図 90 のように G から閉路 C の辺を除去してできるグラフ (一般には非連結であるが, オイラー小道がある) を H とする. G の連結性より, グラフ H の各成分は C と少なくとも 1 点を共有していることに注意しょう. 従って, このような状況下で, C 上の任意の一点からスタートし, C の辺をたどる. そして, H
H
HC

図 90: 考える連結グラフ G は閉路 C とそれぞれオイラー小道を含む成分 H からなる. C 自身はオイラー・グラフであるから, 奇数次の点を含まない. 従って, H も奇数次の点を含まない.
の孤立点でない点に出くわすたびに, その点を含む H の成分のオイラー小道 (C 自身はオイラー・グラフで
ここは 78 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

あるから, 奇数次の点を含まず, 従って, 各成分である H も奇数次の点を含まない) をたどり, その点に戻・・という操作を繰り返し, C 上の出発点に戻るという作業を行うことにより, また C の辺をたどって行く・
り, オイラー小道が得られ, たどって来た道をつなげることにより, 求めるべきオイラー・グラフを描くことができる (証明終わり).
次にオイラー・グラフに関する例題を一つ見ておこう.

'$

例題 6.1
オイラー・グラフに関して以下の問いに答えよ.

(1) どんな n に対して完全グラフ Kn はオイラー・グラフになるか ?
(2) 完全二部グラフ Ks,t のどのような場合がオイラー・グラフとなるか ?
(3) どのような n に対して車輪 Wn はオイラー・グラフとなるか ?
&

%

(解答例)
(1) 完全グラフ Kn の任意の 1 点の次数は n − 1 であるから, n − 1 = 偶数 の場合に限り, Kn はオイラー・グラフとなる. 従って, 例えば, K5 はオイラー・グラフであるが, K4 はオイラー・グラフではない.

(2) 図 91 のように, s ≥ 2, 及び, t が偶数であれば, a → 1 → b → 2 → a → 3 → b → 4 → a → 5 → b のような経路で, a, b を交互に経由したオイラー小道を作ることは常に可能である (図の例では t が奇数なので, できるグラフは半オイラーであり, オイラーではない. t = 6 の場合にはオイラーとなることを各自が確認してみること). 従って, s ≥ 2 のとき, 完全二部グラフ Ks,t はオイラー・グラフとなる.
K 2,5
1

2

a

3

4

5

b

図 91: 完全二部グラフ K2,5 . オイラー小道が存在し, オイラー・グラフである.

(3) 車輪は全ての n に対して, Cn−1 と 1 点との結合部の次数は 3(奇数) であるから, オイラー・グラフとはならない.

さて, 定理 6.2 により, 我々は与えられたグラフの各点の次数を調べることにより, そのグラフがオイラー・
グラフか否かを調べることができるようになった. 従って, 以下のような問題に対し, 我々は直ちに答えることができる.

ここは 79 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一'$
問題
7 つの催し会場 a,b,c,d,e,f,g の主催者がその順路を決める際に, 一筆書きに基づく道順を採用しょうとしている. 各会場から出ている道の本数は以下の表の通りである.
会場

a

b

c

d

e

f

g

道数

4

4

4

4

4

4

2

この場合, 主催者の望む「一筆書き順路」は作成可能であるか ?

&%この問題の答えはもちろん, 「可能」である (全ての点の次数が偶数であるから).
しかし, 実際にこのグラフの中からオイラー小道を探すとなると, グラフに含まれる点の数が多くなるに従って難しくなることはわかるであろう. どのようにすれば系統的にオイラー小道を作ることができるであろうか ?
この問いに対する答えとして, Fleury (フラーリー) のアルゴリズムが知られている. この証明は教科書

p. 45 を読んで頂くことにして, ここでは, アルゴリズムを挙げておくので, 各自, 上の催し会場の順路作成に用いてみること (⇒ 例題 6.3).

Fleury のアルゴリズム
任意の点から出発し, 次の規則に従う限り自由に辺をたどればオイラー小道が得られる.

(1) たどった辺は除去し, 孤立点が生じた場合にはそれも除去する.
(2) どの段階でも, 他にたどる辺がない場合以外には橋をたどるな.

6.2

ハミルトン・グラフ

ハミルトン・グラフ (Hamiltonian graph) : ハミルトン閉路によりなるグラフ.
ハミルトン閉路 (Hamiltonian cycle) : グラフ G の各点をちょうど一度だけ通る閉じた小道.
半ハミルトン・グラフ (semi-Hamiltonian graph) : 全ての点を通る道があるグラフ (閉じてはいない).
与えられたグラフがハミルトン・グラフであるかどうかに関しての判定には次の Ore (オーレ) の定理が役立つ場合が多い.
定理 7.1 (Ore (オーレ) の定理)
単純グラフ G には n(≥ 3) 個の点があるとする. 隣接していない任意の 2 点 v, w に関してdeg(v) + deg(w)

≥ n

(130)

が成立するとき G はハミルトン・グラフである.

(証明)
背理法で示す.

ここは 80 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

「グラフ G はハミルトニアン・グラフではないが (130) を満たす」と仮定し, この矛盾を導く.

G は (ぎりぎり) ハミルトン・グラフではないとすると, G には全ての点を含む道 :v1 → v2 → v3 → · · · → vn
がある. しかし, ここで, v1 と vn が隣接しているとしてしまうと, グラフ G がハミルトン・グラフになってしまうので, v1 と vn は隣接していないものとする.
従って, v1 , vn に関しても不等式 (130) が成立し (背理法の仮定),

deg(v1 ) + deg(vn )≥ nが成り立つ. よって, v1 , vn の次数は 2 以上なので (n = 3 の場合, deg(v1 ) = 2, deg(vn ) = 1 はどうなのか,と思う人がいるかもしれないが, このときの 3 点の配列を考えると, これはあたらないことがわかるであろう), vi は v1 に隣接し, vi−1 は vn に隣接するような 2 点 vi , vi−1 が存在する (図 92 参照). このとき, 単純

v1

vn
v2

v i-1

vi

v n-1

図 92: Ore の定理の十分性の証明で用いるグラフ.
グラフ G には

v1 → v2 → · · · → vi−1 → vn → vi → v1
なる閉路が存在することになり, 矛盾. (証明終わり) 1 .
最後に Ore の定理に関する次の例題を見ておくことにしょう.



例題 6.2

(2003 年度レポート課題 #4 問題 1 )グラフ G には n 個の点があり, (n − 1)(n − 2)/2 + 2 本の辺があるとする. このとき, Ore の定理
を用いて, このグラフ G はハミルトン・グラフであることを示せ.




(解答例)
辺の数が n − 1 本の完全グラフ Kn−1 の辺の本数は (n − 1)(n − 2)/2 本であり, ハミルトン・グラフが多重辺等を含まない単純グラフであることを考慮すると, G は Kn−1 と 1 点 v の合計 n 点からなり, v は Kn−1を構成する任意の 2 点 w, x と図 93 のように結びついていると考えてよい. 従って, この場合の辺の数は(n − 1)(n − 2)/2 + 2 本であり, 問題文に条件として与えられた辺の本数となる.
さて, Kn を構成する任意の 2 点は必ず隣接するので, 考えられる可能性としては, 任意の隣接しない 2 点
が Kn−1 を構成する任意の 1 点 u1 (= w, x) と点 v の場合であるが, このときにはdeg(u1 ) + deg(v)= n−2+2=n(131)となり, Ore の定理を等式ぎりぎりで満たすことがわかる.
また, 上記以外にも例えば Kn−1 を構成する任意の一辺を削除し, この辺で点 v と Kn−1 の任意の一点を結1 この定理はハミルトン・グラフであるための十分条件を与えていることに注意. 従って, 条件式 (130) を満たさないようなハミ

ルトン・グラフも存在する ⇒ 例題 6.3 の 3 を参照のこと.

ここは 81 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

K n-1

x

w

v

図 93: 完全グラフ Kn−1 と点 v が 2 点 w, x で繋がっているグラフ G. 点の個数は n, 辺の本数は (n − 1)(n − 2)/2 + 2 である.
ぶ場合もありうるが, この場合には deg(v) = 3, 辺を削除した点 z の次数 deg(z) = n − 3 であるから, 結局

deg(v) + deg(z) = n となり, やはり Ore の定理を満たす. このような変換を繰り返しても, Ore の定理が破れることがないことは明らかなので結局, 題意, 即ち「n 個の点および (n − 1)(n − 2)/2 + 2 本の辺からなるグラフ G はハミルトン・グラフである」ことが示された.

'

例題 6.3$(2004 年度 演習問題 5 )1. 本講義ノート中に挙げた「催し会場の順路問題」において(1) 各会場間の関係を表すグラフを描け.
(2) (1) で求めたオイラー・グラフにおいて, Fleury のアルゴリズムを用いることにより, オイラー小道を求めよ.
2. オイラー・グラフで, ある点 v から出発する限りは, 同じ辺を 2 度と通らないようにして勝手な方向に辺をたどればオイラー小道が得られるとき, そのグラフは点 v から任意周回可能であるという.

(1) 図 94(左) に与えたグラフは任意周回可能であることを示せ.
(2) オイラー・グラフではあるが, 任意周回可能ではないグラフの例を一つ挙げよ.
(3) 任意周回可能なグラフが展示会場の設計に向いている理由を述べよ.
3. 図 94(右) の Groetzsch グラフはハミルトンであることを示せ.
&

%

5
1
7
v
2

6

4
8

3
9

図 94: ここで任意周回可能であることを示すグラフ (左). 右図は Groetzsch グラフ.

(解答例)
1. 会場配置を連結グラフで表し, Fleury のアルゴリズムを用いることにより, 実際にオイラー小道を求めてみよう.

(1) 問題に与えられた表に従って a〜g の会場を配置すると図 95(左) のようになる.

ここは 82 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

a

a

b

g

10

b

11

1

6

g

13
12

5

c

c

f

7
9

4

f

3

d

8

d
2

e

e

図 95: 各会場間の関係を表すグラフ (左) と求めるオイラー小道 (右).

(2) Fleury のアルゴリズムを用いることにより, 望むべき巡回路が得られる. 図 95(右) に描いた経路がオイラー小道を与える.

2.(1) 図 96 において, 点 v = 4 から出発したとして, 第一歩で v → 1, v → 3, v → 5, v → 7, v → 8, v → 9の異なる 6 通りのいずれを選ぶか・・・・等々により, ことなる経路が得られる. 少々面倒であるが, 全
5
1
7
v
2

6

4
8

3
9

図 96: ここで任意周回可能性について考察するグラフ.
ての可能な経路を書き下してみると (例えば, 一番目の下線が引かれた番号に対応する経路を図示す
ると図 97 のようになる)

4123456748694 ,

4123456749684, 4123456847694, 4123456849674

4123456947684 ,

4123456948674, 4123476548694, 4123476549684

4123476845694 ,

4123476849654, 4123476945684, 4123476948654

4123486547694 ,

4123486549674, 4123486745694, 4123486749654

4123486945674 ,

4123486947654, 4123496547684, 4123496548674

4123496745684 ,

4123496748674, 4123496845674, 4123496847654

4321456748694 ,

4123456749684, 4321456847694, 4123456849674

4321456947684 ,

4123456948674, 4321476548694, 4123476549684

4321476845694 ,

4123476849654, 4321476945684, 4123476948654

4321486547694 ,

4123486549674, 4321486745694, 4123486749654

4321486945674 ,

4123486947654, 4321496547684, 4123496548674

4321496745684 ,

4123496748674, 4321496845674, 4123496847654

4567486941234 ,

4567486943214, 4567496841234, 4567496843124
ここは 83 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

5

2

6

1
8
9

3

7
10

4
12

11

図 97: 下線が引かれた番号に対する具体的な経路.

4567412348694 ,

4567412349684, 4567432148694, 4567432149684

4568476941234 ,

4987476943214, 4568496741234, 4568496743214

4568412347694 ,4568412349674, 4568432147694, 4568432149674

4569476841234 ,

4569476841234, 4569486741234, 4569486743214

4569412347684 ,

4569412348674, 4569432147684, 4569432148674

4765486941234 ,

4765486943214, 4765496841234, 4765496843124

4765412348694 ,

4765412349684, 4765432148694, 4765432149684

4768456941234 ,

4768456943214, 4768496541234, 4768496543214

4768412345694 ,

4768412349654, 4768432145694, 4768432149654

4769456841234 ,

4769456841234, 4769486541234, 4769486543214

4769412345684 ,

4769412348654, 4769432145684, 4769432148654

4865476941234 ,

4865476943214, 4865496741234, 4865496743124

4865412347694 ,

4865412349674, 4865432147694, 4865432149674

4867456941234 ,

4867456943214, 4867496541234, 4867496543214

4867412345694 ,

4867412349654, 4867432145694, 4867432149654

4869456741234 ,

4869456741234, 4869476541234, 4869476543214

4869412345674 ,

4869412347654, 4869432145674, 4869432147654

4965476841234 ,

4965476843214, 4965486741234, 4965486743124

4965412347684 ,

4965412348674, 4965432147684, 4965432148674

4967456841234 ,

4967456843214, 4967486541234, 4967486543214

4967412345684 ,

4967412348654, 4967432145684, 4967432148654

4968456741234 ,

4968456741234, 4968476541234, 4968476543214

4968412345674 ,

4968412347654, 4968432145674, 4968432147654

以上, 全部で 144 通りの経路 (オイラー小道) が可能であり, 従って, このグラフは任意周回可能なグラフである.

ここは 84 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

6
7
9

5
4
8

10

11

3
v
2
1

図 98: 任意周回が不可能であるグラフの一例.

(2) 図 98 にその一例を与える. 図 98 のグラフは各点の次数が偶数であり, 定理 6.2 より, このグラフはオイラー・グラフであり, 確かにオイラー小道, 例えば, v → 3 → 2 → 1 → v → 4 → 5 → 6 → 7 →
4 → 8 → 9 → 10 → 11 → 8 → v.
しかし, 例えば図 98 の矢印に示した通りの進路を選ぶと, 図の点 8, 9, 10, 11 からなる「孤立した」成分が現れてしまう. 従って, 点 8 での進路の選択によっては, オイラー小道ができなくなる. この意
味で, 図 98 に与えたグラフは任意周回不可能なグラフであると言える.
さて, それでは, 任意のオイラー・グラフが与えられたとして, そのグラフが任意周回可能か, あるいは, 不可能であるか, という判定は一般にグラフのどのような特徴によって決まるのであろうか ?
図 99 に図 98 とは異なる任意周回不可能なグラフを 2 点挙げた. これらのグラフを考察すると, い
4

1

5

3
4

3

v

6

2

2

v

7

1

図 99: 上にあげたいずれのグラフも任意周回が不可能である.
ずれも次数が 4 以上の点が 2 点以上含まれることがわかる. もし, 次数 4 以上の点が 2 点以上含まれるのであれば, 図 99 の 2(左図) や 4 のように, この点において, 孤立した成分を生成させてしまうよ
うな経路の取り方は常に可能である. 従って, 任意周回を可能にするためには, 次数 4 以上の点を二つ以上含まないようなオイラー・グラフを用いることが肝要である.

(3) 展示場では, 客が各展示場から任意に次の展示場を選び, しかも, 各展示場を一回ずつまわって, 最初の展示場に戻ってこれることが望ましい. 従って, この性質を満たす任意周回可能グラフの各頂点に展示場を設置することが, 適切な展示場の設計である.

3. 図 100 に答えを載せる. この図 100 は Ore の定理によるハミルトンであるための十分性は満たしてはいないが (例えば deg(7) + deg(10) = 3 + 4 = 7 < 11 で満たさない), 図 100 にハミルトン閉路を示したように確かにハミルトンである.

ここは 85 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

10

7

11

6

9

3

8

5

2

4
1

図 100: 求めるべきハミルトン閉路.

'

例題 6.4$(2005 年度 演習問題 5 )1. 二部グラフ G に奇数個の点がある場合, G はハミルトン・グラフでないことを示せ.
2. 図にあげたグラフはハミルトン・グラフでないことを示せ.

&

%

(解答例)
1. まずは点数 n = 4 の場合の二部グラフの例を図 101(左) に載せるが, これは明らかにハミルトン閉路を含むのでハミルトン・グラフである. 次に n = 6 の場合の二部グラフの一例とその同形なグラフを図

n=6

n=4

図 101: n = 4 の場合の二部グラフの例 (左). 右図は n = 6 の場合の二部グラフの一例 (上) とそれと同形なグラフ (下). 閉路が存在する.

101(右) に載せるが, これも明らかにハミルトン閉路を含むのでハミルトン・グラフである. これら 2つの例からわかるように, 二部グラフを白点と黒点が交互に来るように閉路グラフとして描ける場合には必ずハミルトン・グラフになる.
一方, n が奇数の場合には図 102 に n = 7 の例で示すように, このような白, 黒点の配置は不可能であり, 必ず閉路上には黒黒, あるいは白白が並んでしまう. 従って, 二部グラフはその点数が奇数の場合

ここは 86 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

n=7

図 102: n = 7 の場合には二部グラフを閉路で表現することができない.
にはハミルトン・グラフにはならない.

2. まず, 問題に与えられたグラフの中央の点を除去したグラフを考えると, これにはハミルトン閉路が存在する (図 103 参照). 以下の議論ではこれを基準として考える. また, 話の見通しを良くするため, この閉路と同形なグラフを考えることにしょう (図 103 の下図). 問題のグラフはこのグラフに 1 点を加
12

11

3

1

4

2
7
8

12

1

11

2

10

5

12

11

10

9

8

4

5

7

6

9

10

9

8

3

4

5

1

2

3

6

7

6

13

図 103: 問題に与えられたグラフの中央の点を除去すると, それはハミルトン・グラフでハミルトン閉路が存在する (左). 問題に与えられたグラフと同形なグラフ (右). このグラフにハミルトン閉路があるか否かを考察すればよい.
えて, その点 (13 としょう) と図 103(左) の点 2,4,6 とを結んでできるので, それを具体的に描くと図103(右) のようになる. そこで, このグラフでは点 13 は点 2,4,6 と点 3,5 に「1 つ飛ばし」で結ばれていることから, 点 2 を出発して, 点 3,4,5, 及び, 点 13 を経由して点 6 に至るためには, 必ず, 点 3 か点
5 にはとまらずに通過しなければならないことに注目しよう. また, 点 2 から 2 → 3 → 4 と進んで, 点
9 に移った場合には, 9 → 8 と進むと, それ以後部分グラフ {10, 11, 12} には進めなくなり, 逆に, 9 →
8 へと移った場合には部分グラフ {6, 7, 8} へは進めなくなる.
このことから直ちに全ての点を 1 回ずつ通って元に戻る閉路は存在しないことがわかるので, このグ
ラフはハミルトン・グラフではないことになる. もちろん, ここで考えた経路以外にも点 1 → 点 12

→ · · · のように回る経路も存在するが, 結局, ここで考えた, 点 {2, 3, 4, 5, 6, 13} を含んだ「部分グラフ」にぶつかれば上記の問題が生じ, 決してハミルトン閉路を描くことはできないことになる.
※ 補足説明Ore の定理はハミルトン・グラフであるための十分条件であるため, Ore の定理を満たしていれば, つまり,完全グラフのように十分な辺数があれば, ハミルトン閉路があることが示せるが, Ore の定理を満たさない
場合, 一般的に言ってハミルトン・グラフか否かを証明することはとても難しくなる. この手の「判定問題」
では重宝になる必要条件もいくつかあるようだが, それは十分条件と比べて数が少なく, 実用的なものもさほど無さそうである. 必要十分条件についてはまだ何も見つかっていない.
ここは 87 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

従って, ハミルトン・グラフか否かの証明はグラフの特性に応じてケース・バイ・ケースで取り組まなけ
ればならないが, おおまかに言えば, まずあたってみる価値のある方法は 2 つあり, 一つは上の例題で紹介した「グラフを二部グラフで表し, その点数が奇数であることで非ハミルトン性を示す」やり方 (方法 1).
もう一つは辺数に関して背理法で矛盾を導くという方法 (方法 2) である.
ここでは簡単に方法 2 を説明しておきたい. まず, 例として図 104 のような点数 11, 辺数 15 のグラフに対し, 「ハミルトン閉路 C が存在する」と仮定する. その閉路 C 上では各点には必ず 2 本の辺が接続して
a
15
1

2
9

10
b
11

e

14
5

12
13

6

d

8
c

3

7
4

図 104: 背理法を用いて非ハミルトングラフであることを示すのに例として用いるグラフ.
いなければならないことに注目すると, 互いに隣接していない a, b, c, d, 及び, e の 5 点のそれぞれの次数は3, 3, 4, 3, 3 であるので, C 上に無い辺数は少なくとも (3 − 2) + (3 − 2) + (4 − 2) + (3 − 2) + (3 − 2) = 5(本) であり, 従って, 閉路 C には高々15 − 5 = 10 (本) しか辺が無いことがわかる. しかし, 点数 11 でハミルトン閉路を作る場合にはその閉路の辺数は 11 となるので, 辺数 10 ではこれは不可能ということになり,
我々が用いた「ハミルトン閉路が存在する」という仮定に矛盾が生じたので図 104 のグラフにはハミルト
ン閉路が無い, と結論付けることができる.

'

例題 6.5$(2006 年度 演習問題 5 )G はハミルトン・グラフであるとし, S は G の k 個の点からなる任意の集合であるとする. このとき, グ
ラフ G − S (G から S の点とそれらに接続している辺を全て除去して得られるグラフ) の成分は k 個以
下であることを具体的なハミルトン・グラフに対して一つ例示せよ.

&

%

(解答例)
ハミルトングラフはハミルトン閉路を含み, その閉路 C は●○を互い違いに並べてできる輪であるから, 完
全二部グラフ Ks,s で表すことができる (s = 2, 3, · · ·). 従って, G はこの閉路を構成する辺と他の接続辺からなる図 105 のようなグラフであると考えてよい. ここで, G の中から任意の k 個の点を取り出して構成される集合 S を G から引いてできるグラフの成分数は, k 個の点が全て隣接する場合には明らかに 1 であり,これが G − S の成分数の最小値を与える (図 106 参照). しかし, ここで問題とするのは G − S の成分の最大値である. この最大値を与えるような集合 S の選び方は明らかに S を構成する k 個の点が全て隣接しない場合であるから, その場合の G − S の成分数を評価すればよい. このために, 閉路 C 上の k 個の点をを 2つずつ組んでペアにし (こうしたペアの総数は l = k/2), C 上にこのペアが一つできるごとに G − S の成分
がどのように変化していくのかを調べる. すると図 107(左) を参考にした考察より, ペア数が 1 の場合には成分数は 2, ペア数が 2 の場合には成分数が 4, ...., ペア数が l の場合には成分数が 2l となり, この 2l は S
ここは 88 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

GC

図 105: ここで考えるハミルトングラフ. 閉路 C がここでのハミルトン閉路.

k=1

S

図 106: S の要素が全て隣接する場合の例. 実線の部分でグラフ G を切断することになり, 得られる G − S の成分数は明らかに 1
である.

の点の総数 k であったから, 結局

G − S の成分数≤ kとなり, 題意を満たすことになる. ところで上記の議論では G の中の閉路 C に関して考え, この閉路を構成する辺以外の接続辺をひとまずは考えなかったわけだが, 図 107(右) のような接続辺が加わったとしても,G − S の成分数は減りこそはするが, 決して増えることはない. よって, この場合にも題意は満たされることになる.
'

例題 6.6$(2005 年度情報工学演習 II(B) #1)

K3 , K5 , K7 , および K9 にはハミルトン閉路があることを Ore の定理により示し, それぞれのグラフにおいて, 互いに共通な辺を持たない — 辺素な— ハミルトン閉路がいくつあるかを調べよ. ついで, この結果を一般化し, K2k+1 (k ≥ 1) の辺素なハミルトン閉路数を求める公式を作れ (類推によって公式を求めた場合にはその正当性を証明すること).

&

%

(解答例)
まず, 完全グラフにハミルトン閉路が存在することは, 一般の Kn に対して示せる. Kn の全ての点の次数は n − 1 なので, n − 1 + n − 1 = 2n − 2 ≥ n (n ≥ 3) なので, Ore の定理を満たすことは明らか・・・となりそうであるが, 実は Ore の定理の条件式 : deg(v) + deg(u) ≥ n の点 u, v は「互いに隣接しない点」である
ので, 完全グラフは全ての点が隣接しているわけであるから, これをそのまま適用することはできない.
そこで, Ore の定理を書き換えよう. 「グラフに含まれる任意の点 v の次数が f (n) 以上である」つまり,

deg(v) ≥ f (n) と仮定する. ここで, f (n) は n の関数である. このとき, 点 u についてもこれが成り立つべ
ここは 89 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

2
4

2
4

1

1
3

3

図 107: S の成分が全て隣接しない場合で, |S| = 4 の場合. 得られる G − S の成分数は 4 である. また, ハミルトン閉路を構成す
る辺以外に接続辺ができたとしても, この成分数は減りこそはするが, 決して増えない (右図).
きなので, deg(u) ≥ f (n). この 2 つの不等式の辺々を足すと deg(v) + deg(u) ≥ 2f (n) であるが, これとOre の定理の条件式を比較すると, 2f (n) = n, つまり, f (n) = n/2 であることがわかる. 従って, Ore の定理は次のように言い直すことができる.
グラフに含まれる全ての点に対しdeg(v)

≥

n
2

(132)

が成立するならば, そのグラフはハミルトン・グラフである. これを Dirac (ディラック) の定理と呼んでいる. 今の場合全ての点の次数は n − 1 であるから, n ≥ 3 であればこの条件を満たす. 従って, ハミルトン
閉路は存在する.
後半の部分は具体的に互いに辺素はハミルトン閉路を見つけるアルゴリズムを与えてしまおう. まず, 完
全グラフの描き方として n (奇数) 個の点を閉路グラフとなるように配置する. そして, 各点を自分以外の点と結んでいくようにして完全グラフ Kn を描くことにする (図 108 参照). このとき, 出発する点 v を適当に選ぶと, 1 個目のハミルトン閉路は v から閉路グラフの外周をたどり, v に戻ることにより得られる. 2 個
目は v から 1 つ飛びに順次点をたどっていき, v に戻ることにより得られる. 3 個目は v から 2 つとびに順
次回り v に戻ることにより, 4 個目は v から 3 つとびに順次回り・・・というようにして得られるハミルトン
閉路は全て互いに辺素なものとなることは明らかである. このような点 v から引き続く点の選択の余地としては (n − 1)/2 通りだけ存在する ( 点 v の次数の半分. なぜ半分になるか, は残りの半分は全ての閉路を逆向きにたどることに相当するので, 「無向きハミルトン閉路」としては同一視する) ので, n = 2k + 1 の場合には (2k + 1 − 1)/2 = k 通りとなり, 従って, 完全グラフ K2k+1 の互いに辺素なハミルトン閉路の個数は k であることがわかった. 図 108 に K3 , K5 , および, K7 の場合の互いに辺素なハミルトン閉路を図示
する.
しかし, ここで注意しなければならないのは, 2k + 1 が 1 と自分自身以外の約数を持つ場合, その「約数個飛び」で閉路を描いていくと, 全ての点を巡る前に閉じたグラフができてしまう (図 109 参照). 従って,


この場合には互いに辺素なグラフの個数は k から 2k + 1 の約数の個数 k を引いたものになる. 従って, 互いに辺素なハミルトン閉路の個数を M (K2k+1 ) とすると
k(2k + 1 が素数のとき)(133)
M (K2k+1 ) =k − k (2k + 1 が素数でなく, 1 と自分自身以外に k 個の約数を持つとき)とまとめることができる.

ここは 90 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

K3

K5

K7

図 108: K3 , K5 , K6 の互いに辺素なハミルトン閉路.

NG !

K9

図 109: K9 の互いに辺素なハミルトン閉路. 9 の約数 3 飛びで各点を結んでいくと, ハミルトン閉路ができる前に閉じたグラフが出来上がってしまう.



例題 6.7

(2005 年度情報工学演習 II(B) #1)

ピータースン・グラフが ハミルトン・グラフでない ことを証明せよ.





(解答例)
図 110 のようにピーターソン・グラフの各点に名前をつける. まず着目するのは, u1 , u2 , · · · , u5 の 5 点からなる内部の部分グラフ (g1 と名づける) は「星型の一筆書き」としてハミルトン閉路が存在することである. 従って, 外周 (部分グラフ g2 と名づける) の 1 点 (v1 として一般性を失わない) から出発し, 星型部
分グラフ g1 の一部を経由し, 点 v1 に戻るという, g1 と g2 が 2 つの辺で結ばれる場合 (ケース A と呼ぼう)と, v1 から出発し, g1 の一部を経由, g2 に至り, さらに g1 の一部を経由して v1 に戻るという, g1 と g2 が 4本の辺で結合される場合 (ケース B と呼ぶ) のいずれかである. 従って, 以下ではこの各々のケースに対し,ハミルトン閉路が存在しないことを示していく.

• (ケース A)
g1 と g2 を結ぶ辺を v1 u1 と任意の e とする. このとき, v1 u1 , e を含む道としては次の 2 つが考えられる.
(1) e = u4 v4 のとき, その道は v1 u1 u3 u5 u2 u4 v4 . このとき, 残る点は v2 , v3 , v5 .

ここは 91 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

v1

u1

v5

u2

u5

u4

v2

u3

v4

v3

図 110: ピータースン・グラフの各点に名前をつける.

(2) e = u3 v3 のとき, その道は v1 u1 u4 u2 u5 u3 v3 . このとき, 残る点は v2 , v4 , v5 .
である. 以上 (1)(2) のいずれの場合も残る 3 つの点を通って v1 に戻れないことは明らか. よって,(ケース A) でハミルトン閉路が存在することはない.
• (ケース B)
g1 と g2 とを結ぶ 4 つの辺を {v1 u1 , v2 u2 , v3 u3 , v4 u4 } としても一般性を失わない. このとき, v5 u5 は含まれないことになる. そこで, この場合にハミルトン閉路 C が存在したと仮定しょう. すると, ピー
タースン・グラフの各点は必ず 2 つの辺と接続していなければならないことになるので, これを考慮に入れると, C には v1 v5 , v5 v4 が含まれることになる. 従って, このときに点 u4 に着目すると, u4 u1という辺は C には含まれないことになる. なぜならば, u4 u1 が存在するとなると, 点 u1 では (既に v1と結ばれているので) さらなる辺を結ぶことはできず, ハミルトン閉路を作ることはできない. 従って, v4 は u2 と結ばれるべきであるが, u2 は v2 と既に結ばれているので, u2 u5 は C に含まれないことになる. しかし, こうなると点 u5 には 1 辺 u5 u3 のみが接続されることになり, これでは明らかにC が存在することと矛盾する. 従って, (ケース B) の場合にもハミルトン閉路が存在することはできない.
以上の考察により, ピータースン・グラフにはハミルトン閉路が無い, つまり, ピータースン・グラフはハ
ミルトン・グラフではないと結論付けられる.



例題 6.8(2006 年度情報工学演習 II(B) #1)

点数 n が偶数, 辺数 m が奇数のオイラー・グラフは存在するか否か. 理由とともに述べよ.





(解答例)
いずれも全ての点の次数が偶数 (= 2) である点数 3(三角形) と 4(四角形) のグラフを図 111 のように 1 点(以後, 共有点と呼ぶ) で接続させると, 点数は 3 + 4 − 1(共有点分を差し引く) = 6, 辺数 3 + 4 = 7 となる
ので, 辺数が奇数, 点数が偶数となり題意を満たす. このグラフは共有点の次数が 4, それ以外が 2 なので全て偶数である. 従って, オイラーの定理より, このグラフはオイラー・グラフである. よって, 辺数が奇数,
点数が偶数であるようなオイラー・グラフは存在する.

ここは 92 ページ目

グラフ理論 2007 #5

北海道大学 大学院情報科学研究科 井上純一

図 111: ここで考えるグラフ. これはオイラー・グラフである.

演習問題 51. 数列: D = (d1 , d2 , · · · , dn ), d1 ≥ d2 ≥ · · · ≥ dn が与えられた際, この数列 D がグラフ的であるか否かの判定条件として次が知られている. すなわち
n
『数列 D がグラフ的であるのは, この数列の総和:
i=1 di が偶数であり, k = 1, 2, · · · , n に対し
k


di

≤

i=1

k(k − 1) +nmin(k, di )

(134)

i=k+1

が成立するとき, かつ, このときに限る.』
ここで, 記号: min(a, b) は a, b のうちで小さい方を意味するものとする.
この判定条件を用いて次の数列:• D1 = (3, 2, 2, 1)• D2 = (4, 3, 3, 3, 3)• D3 = (7, 6, 6, 6, 5, 5, 2, 1)のそれぞれがグラフ的か否かを判定せよ.

(※ 上記判定条件の証明は余裕のある者は考えてみると良い. レポートに書いてくれた場合には, その分加点する. 証明例は次回 (5/28) 配布の講義ノートで解説する.)
2. 完全グラフ Km の点と Kn−2m の点を全て結び, Km の点と K m の点を全て結ぶことによってできる
グラフを Cm,n と名づけよう. (n > 2m であり, Km は Km の補グラフである.)
このとき• Cm,n の辺数 ε(Cm,n ) を m, n で表せ.
• ε(Cm,n ) を最小とする m の値を n を用いて表し, その最小値を n の関数として求めよ.

ここは 93 ページ目