ケーニヒスベルクの橋とグラフ理論の誕生

要約

中世の都市ケーニヒスベルクには、二つの大きな島が七つの橋で互いにつながり、川岸ともつながっていました。数学者のカール・ゴットリーブ・エレは、七つの橋を一度だけ渡り、重複しないように渡る方法を見つけることに夢中になりました。当時最も有名な数学者の一人であるレオンハルト・オイラーは、グラフ理論という新しい数学分野を発明することでこの問題を解決しました。ケーニヒスベルクの地図を点と辺のグラフに単純化することで、オイラーは七つの橋を一度だけ渡ることは不可能であることを証明しました。これは、二つ以上のノードを持つすべてのグラフに適用される一般的な理論の発展につながりました。

七つの橋の問題

中世の都市ケーニヒスベルクには、二つの大きな島が七つの橋で互いにつながり、川岸ともつながっていました。数学者のカール・ゴットリーブ・エレは、七つの橋を一度だけ渡り、重複しないように渡る方法を見つけることに夢中になりました。彼はレオンハルト・オイラーに手紙を書き、問題の解決を助けてくれるように頼みました。

最初はオイラーは、この問題が数学とは何の関係もないと考えていました。しかし、彼が考えれば考えるほど、何かがあるかもしれないと気づき始めました。オイラーの問題への解決策は、グラフ理論という新しい数学分野を発明することにつながりました。

グラフ理論の誕生

オイラーの最初の洞察は、島や川岸に入ると出るときに通るルートは実際には重要ではないということでした。したがって、地図は簡略化され、それぞれの四つの陸地がノードと呼ばれる単一の点で表され、橋を表す線または辺でつながっていると考えることができます。この簡略化されたグラフにより、各ノードの次数（陸地が接する橋の数）を簡単に数えることができます。

なぜ次数が重要なのでしょうか？この挑戦のルールによれば、旅行者が一つの橋で陸地に到着すると、異なる橋を通って陸地から出る必要があります。つまり、任意のルートの各ノードについて、それに接続する橋は異なるペアで出現しなければなりません。つまり、訪れたすべての陸地に接する橋の数は偶数でなければなりません。唯一の例外は、散歩の開始地点と終了地点の場所です。

グラフを見ると、すべての四つのノードが奇数次数を持っていることが明らかになります。したがって、どの経路を選んでも、ある時点で橋を二度渡らなければならなくなります。オイラーはこの証明を使って、二つ以上のノードを持つすべてのグラフに適用される一般的な理論を形成しました。

オイラー路とサーキット

エッジを一度だけ訪れるオイラー路は、二つのシナリオのいずれかでしか可能ではありません。一つ目は、奇数次数のノードがちょうど二つある場合で、その他のノードはすべて偶数であることを意味します。その場合、出発点は奇数のノードの一つであり、終点はもう一つの奇数のノードです。二つ目は、すべてのノードが偶数次数である場合です。その場合、オイラー路は同じ場所で始まり終わるため、それはオイラー・サーキットと呼ばれるものになります。

ケーニヒスベルクでのオイラー路の作成

では、ケーニヒスベルクでオイラー路を作成するにはどうすればよいでしょうか？簡単です。どの橋でも一つ取り除きます。そして、歴史は自分自身でオイラー路を作成しました。第一次世界大戦中、ソビエト空軍は市内の二つの橋を破壊し、オイラー路を簡単に作成することができました。ただし、公平を期すために言えば、それは彼らの意図ではなかったでしょう。これらの爆撃はケーニヒスベルクを壊滅させ、後にロシアのカリーニングラードとして再建されました。