前へ / 戻る / 次へ

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

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

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

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

オイラー先生 HELP!

　もし不可能なら不可能であることを証明してもらいたい、ということでオイラー先生に HELP が掛かりました。 　オイラー先生は

• 岸や中洲を頂点
• 橋を辺

として地図を抽象化することを思い付きました。（面である岸や中洲を点にしてしまうというこの大胆な発想 !!）　 するとこんな絵が得られます：
上下の頂点が岸、左右の頂点が中州を表しています。ここのところ、よく理解してください。

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

一筆描きの定理

　さて、橋渡りのクイズは、このグラフで一筆描きができるか、という問題に言い換えることができます。 そしてオイラー先生は「一筆描きの定理」を証明することによって、橋渡りが不可能であることを証明しました： 橋渡りのグラフでは４つの頂点の次数が 5, 3, 3, 3 ですので一筆描きができないことがわかります。

前へ / 戻る / 次へ