組合せとグラフの理論(塩田)第1回 (2) グラフ理論の始まり

ケーニヒスベルクの7つの橋渡り

 グラフ理論で扱う「グラフ」とはどんなものか、を理解してもらうために、グラフ理論が生まれたエピソードを紹介します。

 18世紀初め、ロシア、ケーニヒスベルクの町で「7つの橋渡り」という遊びが流行りました。 プルーゲル川の両岸と2つの中洲に架かる7つの橋を丁度1回ずつ渡って散歩できるか、というクイズです。

ちょっと試してみてください。うまくいかないはずです。

オイラー先生 HELP!

 もし不可能なら不可能であることを証明してもらいたい、ということでオイラー先生に HELP が掛かりました。
 オイラー先生は1707年生まれの大数学者。1771年頃に失明するもなお1783年に76歳で没するまで研究を続け、書いた論文は合計5万ページを超えます。
 オイラー先生は
  • 岸や中洲を頂点
  • 橋を辺
として地図を抽象化することを思い付きました。(である岸や中洲をにしてしまうというこの大胆な発想 !!) 頂点は、それらが表す岸や中洲が橋でつながっているときに、辺で結ぶことにします。 するとこんな絵が得られます:
赤い部分を抜き出すとこんな図形です:

 このようにモノのつながりを表現した図形(と言うか構造)を「グラフ」と呼びます。

一筆描きの定理

 さて、橋渡りのクイズは、このグラフで一筆描きができるか、という問題に言い換えることができます。 そしてオイラー先生は「一筆描きの定理」を証明することによって、橋渡りが不可能であることを証明しました:
定理 連結なグラフでは、出発点に戻る一筆描きができることと、全ての頂点の次数が偶数であることが同値である。 ( ひとつの頂点に接続している辺の本数を専門用語で次数と言います。)
橋渡りのグラフでは4つの頂点の次数が 5, 3, 3, 3 ですので一筆描きができないことがわかります。