グラフ理論 配布資料 #5 (教科書 pp. 42 〜 59 の内容)
担当 : 井上 純一 (情報科学研究科棟 8-13)
平成 17 年 5 月 16 日

目次
66.149オイラー・グラフ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.2

ハミルトン・グラフ

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

演習問題 4 の解答例
1. 完全グラフ及び, 辺が 1 本断線したグラフ (3 種類), 辺が 2 本断線したグラフ (3 種類), 辺が全て断線したグラフ (1 種類) のそれぞれのグラフを図 64 に示す. ここで注意すべきなのは, 各点はネットワーabcaaacbbcabacbcbacbcabc

図 64: ここで考えられるネットワークの状態. 上から, 断線ゼロ, 1 本断線, 2 本断線, 全部断線のグラフ. ネットワークとして正常であるのは, 断線ゼロ, 及び, 1 本断線の場合のみ.
クのサーバに対応するので, このような問題においては, グラフはラベル付きのものを考えるべきである. 従って, この図からネットワークが正常に動作するのは完全グラフの場合, 及び, 辺が 1 本だけ断線する場合に限り, それぞれの確率は (1 − q)3 , 3q(1 − q)2 で与えられるので, ネットワークの信頼度

R はこれら両者の和で与えられる. 従って, q の関数としての R はR(q)= (1 − q)3 + 3q(1 − q)2となる. これを図 65 に描く.

47(41)

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

1R0.8

0.6

0.4

0.2

000.2

0.4

0.60.81q

図 65: ネットワークの信頼度 R の各辺の断線確率 q 依存性.

L1eL2L3

図 66: 辺 e を含む閉路としては, L1 , L2 があるが, e を含まない閉路として, いつでも L1 , L2 の和から e を削除したものを第 3 の閉路 L3 としてとることができる.

2. (1)(2) に該当するケースをそれぞれ図 66, 及び, 図 67 に描く. 図 66 に示したように, 辺 e を含む閉路として L1 , L2 を選ぶと, e を含まない閉路として, いつでも L1 , L2 の和から e を削除したものを第 3の閉路 L3 としてとることができる.
図 67 のように辺 e1 , e2 が三角形をなしている場合には, カットセット {e, e1 } によって, グラフ G は部
分グラフ G1 , 及び, G2 + G3 に分離し, カットセット {e, e2 } によって部分グラフ G1 + G2 , 及び, G3に分離するが, e を含まないカットセットとして {e1 , e2 } をいつでもとることができて, この場合にはグラフ G が部分グラフ G1 + G3 , 及び, G2 に分離する.

レポート #3 に関する補足コメント
2. の n = 5 の場合に自己補対グラフを求める問題で, 次数 1, 2, 3 の点の個数を L, M, N としたとき
L + 2M + N= 10(42)

ここは 48 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

G2C1C3e1G1e2G3eC2

図 67: 図のように辺 e, 及び, 辺 e1 , e2 が三角形をなしている場合には, カットセット {e, e1 }, {e, e2 } 以外に必ず, {e1 , e2 } を選ぶことができる.

L+M +N= 5(43)として, 可能な次数列を L, M, N ≥ 1 の範囲内で探しましたが, L, M, N はゼロも取りうるので, この範囲内で探せば, M = 5, L = N = 0 も上記方程式を満たします. このときの次数列は (2, 2, 2, 2, 2) となり, 可能な自己補対グラフとして図 68 のようなものも存在することになります.

図 68: n = 5 の場合の自己補対グラフのもう一つの可能性. 図の実線と破線がぞれぞれ互いに同形となっている.

6

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

6.1

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

ここは 49 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

Eulerian graphSemi-Eulerian graph

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

(証明)⇒ (必要性)G のオイラー小道 P がある一点を通過する毎に 2 を加えていくと, 全ての辺はちょうど 1 回ずつ含まれるので, 各点でこの和はその点の次数に等しく, しかも, それは偶数である.

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

図 70: 考える連結グラフ G は閉路 C とそれぞれオイラー小道を含む成分 H からなる. C 自身はオイラー・グラフであるから, 奇数次の点を含まない. 従って, H も奇数次の点を含まない.

ここは 50 ページ目グラフ理論 2005

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

✬✩

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

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

(解答例)
(1) 完全グラフ Kn の任意の 1 点の次数は n − 1 であるから, n − 1 = 偶数 の場合に限り, Kn はオイラー・グラフとなる. 従って, 例えば, K5 はオイラー・グラフであるが, K4 はオイラー・グラフではない.
(2) 図 71 のように, 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,512a345b図 71: 完全二部グラフ K2,5 . オイラー小道が存在し, オイラー・グラフである.

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

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

ここは 51 ページ目

グラフ理論 2005

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

道数4444442

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

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

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

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

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

6.2

ハミルトン・グラフ

ハミルトン・グラフ (Hamiltonian graph) : ハミルトン閉路によりなるグラフ.
ハミルトン閉路 (Hamiltonian cycle) : グラフ G の各点をちょうど一度だけ通る閉じた小道.
半ハミルトン・グラフ (semi-Hamiltonian graph) : 全ての点を通る道があるグラフ (閉じてはいない).

与えられたグラフがハミルトン・グラフであるかどうかに関しての判定には次の Ore (オーレ) の定理が役立つ場合が多い.

ここは 52 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

定理 7.1 (Ore の定理)
単純グラフ G には n(≥ 3) 個の点があるとする. 隣接していない任意の 2 点 v, w に関してdeg(v) + deg(w)≥ n(44)が成立するとき, G はハミルトン・グラフである.

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

G は (ぎりぎり) ハミルトン・グラフではないとすると, G には全ての点を含む道 :v1 → v2 → v3 → · · · → vnがある. しかし, ここで, v1 と vn が隣接しているとしてしまうと, グラフ G がハミルトン・グラフになってしまうので, v1 と vn は隣接していないものとする.
従って, v1 , vn に関しても不等式 (44) が成立し (背理法の仮定),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 が存在する (図 72 参照). このとき, 単純v1vnv2v i-1viv n-1

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

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

✗例題 12✔

グラフ G には n 個の点があり, (n − 1)(n − 2)/2 + 2 本の辺があるとする. このとき, Ore の定理を用いて, このグラフ G はハミルトン・グラフであることを示せ.
✖

✕

1 この定理はハミルトン・グラフであるための十分条件を与えていることに注意. 従って, 条件式 (44) を満たさないようなハミルトン・グラフも存在する ⇒ 例題 13.

ここは 53 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一(解答例)
辺の数が n − 1 本の完全グラフ Kn−1 の辺の本数は (n − 1)(n − 2)/2 本であり, ハミルトン・グラフが多重辺等を含まない単純グラフであることを考慮すると, G は Kn−1 と 1 点 v の合計 n 点からなり, v は Kn−1を構成する任意の 2 点 w, x と図 73 のように結びついていると考えてよい. 従って, この場合の辺の数はxK n-1wv

図 73: 完全グラフ Kn−1 と点 v が 2 点 w, x で繋がっているグラフ G. 点の個数は n, 辺の本数は (n − 1)(n − 2)/2 + 2 である.

(n − 1)(n − 2)/2 + 2 本であり, 問題文に条件として与えられた辺の本数となる.
さて, Kn を構成する任意の 2 点は必ず隣接するので, 考えられる可能性としては, 任意の隣接しない 2 点が Kn−1 を構成する任意の 1 点 u1 (= w, x) と点 v の場合であるが, このときにはdeg(u1 ) + deg(v)= n−2+2=n(45)となり, Ore の定理を等式ぎりぎりで満たすことがわかる.
また, 上記以外にも例えば Kn−1 を構成する任意の一辺を削除し, この辺で点 v と Kn−1 の任意の一点を結ぶ場合もありうるが, この場合には deg(v) = 3, 辺を削除した点 z の次数 deg(z) = n − 3 であるから, 結局deg(v) + deg(z) = n となり, やはり Ore の定理を満たす. このような変換を繰り返しても, Ore の定理が破れることがないことは明らかなので結局, 題意, 即ち「n 個の点および (n − 1)(n − 2)/2 + 2 本の辺からなるグラフ G はハミルトン・グラフである」ことが示された.

✬例題 13✩

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

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

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

517v
264839

図 74: ここで任意周回可能であることを示すグラフ.

図 75: Groetzsch グラフ.

(解答例)
1. 会場配置を連結グラフで表し, Fleury のアルゴリズムを用いることにより, 実際にオイラー小道を求めてみよう.
(1) 問題に与えられた表に従って a〜g の会場を配置すると図 76 のようになる.
(2) Fleury のアルゴリズムを用いることにより, 望むべき巡回路が得られる. 図 77 に描いた経路がオイラー小道を与える.

2.
(1) 図 78 において, 点 v = 4 から出発したとして, 第一歩で v → 1, v → 3, v → 5, v → 7, v → 8, v → 9の異なる 6 通りのいずれを選ぶか・・・・等々により, ことなる経路が得られる. 少々面倒であるが, 全ての可能な経路を書き下してみると (例えば, 一番目の下線が引かれた番号に対応する経路を図示すると図 79 のようになる)

4123456748694,

4123456749684

4123456847694,

4123456849674

4123456947684,

4123456948674

ここは 55 ページ目グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

abgcfde

図 76: 各会場間の関係を表すグラフ.
a10b1116g

13
1257c
94f

38d2e

図 77: 求めるオイラー小道.

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

ここは 56 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

517v
264839

図 78: ここで任意周回可能性について考察するグラフ.

526187931041211

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

4321486547694,

4123486549674

4321486745694,

4123486749654

4321486945674,

4123486947654

4321496547684,

4123496548674

4321496745684,

4123496748674

4321496845674,

4123496847654

4567486941234,

4567486943214

4567496841234,

4567496843124

4567412348694,

4567412349684

4567432148694,

4567432149684

4568476941234,

4987476943214

4568496741234,

4568496743214

4568412347694,

4568412349674

4568432147694,

4568432149674

4569476841234,

4569476841234

4569486741234,

4569486743214

4569412347684,

4569412348674

4569432147684,

4569432148674
ここは 57 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

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,

49654321486744967456841234,4967456843214

4967486541234,

4967486543214

4967412345684,

4967412348654

4967432145684,

4967432148654

4968456741234,

4968456741234

4968476541234,

4968476543214

4968412345674,

4968412347654

4968432145674,

4968432147654
ここは 58 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

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

(2) 図 80 にその一例を与える. 図 80 のグラフは各点の次数が偶数であり, 定理 6.2 より, このグラフは67954810113v
21

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

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

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

ここは 59 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

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

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

演習問題 51. 二部グラフ G に奇数個の点がある場合, G はハミルトン・グラフでないことを示せ.
2. 図 83 にあげたグラフはハミルトン・グラフでないことを示せ.

図 83: ここでそのハミルトン性を考えるグラフ.

ここは 60 ページ目