Part 1

2004/7/8
数学１資料ーグラフ理論入門
１．ケーニヒスベルグの問題
問題
（１）．各橋をちょうど１度ずつ通るような歩き方はあるか？（Leonard Euler）
（２）．橋を一つ減らして以下のようにするとどうなるか？
（３）．他の橋を減らすとどうか？また橋を増やすとどうか？
２．グラフとは？
ケーニヒスベルグの問題を考えるために，橋の様子を表す方法を考える．
岸や島を点●，橋を線で表すと
定義． グラフとは点の集合 V と辺の集合 E の組 G=(V,E) のことをいう．
（例）
１．以下のグラフは
V={A,B,C,D}, E={{A,B},{A,C},{A,D},{B,C}}
で表される．
２．V={A,B,C,D,E}, E={{A,B},{A,C},{A,E},{B,C},{B,D},{C,D},{D,E}} で表されるグラフ
を図示すると以下のようになる．
３．オイラーの解法
まずグラフを使ってオイラーの問題１を言い換えてみると，
問題１
すべての辺をちょうど１回ずつ通るような道が存在するか？
【解】
ケーニヒスベルグのグラフのすべての頂点には奇数本の辺がつながっていることに注意．
ある頂点を訪れる時には，１つの辺を通ってやってきて別の辺から出て行くことになる．
再びこの点を訪れるときには残りの一つの辺を通ってやってこなければならないので，こ
こから再び出て行くことはない（この頂点につながっているすべての辺は既に通ってし
まっている）．よって
辺が奇数個つながっている頂点は出発点か終着点のいずれかである．
ことがわかる．ところでケーニヒスベルグのグラフには４つの頂点があるが，出発点と終
着点は合わせて２つなので，すべての辺をちょうど１回ずつ通るような道は存在しない．
４．オイラーの問題を一般化する
定義．あるグラフにおいてすべての辺をちょうど１度ずつとおるような道をオイラー路
(Euler path)という．
例．
定義．グラフの頂点が奇（偶）であるとは，その頂点につながっている辺の数が奇
（偶）数である時をいう．
オイラーの解を一般化すると
オイラーの定理．
グラフの奇頂点の数が２個以下なら，そのグラフにはオイラー路が存在する．逆にグラフ
にオイラー路が存在するなら，そのグラフの奇頂点の数は２個以下である．
５．パーティ着席問題
問題．あるn人のグループにアンケートをとり，誰と誰が友人同士かを調べた．その後，
このn人がパーティで一つの円卓を囲むことになった．
この時n人の各々が両隣に友人がいるように席を決めることは可能か？
状況をグラフで表す．⇒ n人のそれぞれを頂点で表し，友人同士の頂点を辺でつ
なぐ．
(a) ５人の例 (b) １６人の例
座り方があるということをグラフの性質で表す．
定義．グラフの各頂点をちょうど１度だけ通って最初の頂点に戻る通り方をハミルトン
閉路という．
と定義すると，
パーティ着席問題の条件を満たす座り方がある
⇔ 友人関係を表したグラフにハミルトン閉路が存在する．
ことが成り立つ．
６．グラフ理論における他の問題
（１）．ラムゼイの定理
駅に６人の人がいる時，そのうちの３人がお互いに知り合いか，３人はお互いを全
く知らないかのいずれかが必ず成り立っている．
（２）．４色問題
隣り合う国同士が同じ色にならないように地図を塗り分けるには４色の色があればよい．
演習問題．
１．以下のグラフをG=(V,E)で表す時，VとEを示しなさい．
２．V=|A,B,C,D,E}, E={{A,B},{A,D},{B,C},{B,E},{C,D},{D,E}}で表されるグラフを図示し
なさい．
３．オイラーの定理を用いて以下のグラフにオイラー路が存在するかどうかを判別し，そ
の理由を簡単に説明しなさい．
(a)
(c)
(b)
Paul Erdos(1913-1996)
A Mathematician is a machine for turning coffee into theorems.
Why are numbers beautiful? It's like asking why is Beethoven's Ninth
Symphony beautiful. If you don't see why, someone can't tell you. I
know numbers are beautiful. If they aren't beautiful, nothing is.
数論、組合せ論、グラフ理論において大きな業績を残した。良く知られたものに、素数定
理の初等的な証明の発表がある。
彼は他人と共著で論文を発表することを好んだ。彼と共同研究をした数学者達は、エルデ
シュへの敬意と、軽いユーモアを込めてエルデシュ数をつくった。それによれば、彼と直
接共同研究した研究者はエルデシュ数が 1 になり、エルデシュ数が n の研究者と共同研究
した研究者は n+1 のエルデシュ数を持つ。
（http://ja.wikipedia.org/wiki/ポール・エルデシュ による．）