Loading article…
ケーニヒスベルクの七つの橋は、ケーニヒスベルク（現在のカリーニングラード）の橋を巡るウォーキングツアーで、出発点に戻るルートを要求される歴史的なパズルです。 1736年にレオンハルト・オイラーによって数学的に定式化され、不可能性が証明されたことで[ 1 ] 、グラフ理論の基礎が築かれ、トポロジーの概念が予見されました。[ 2 ]
プロイセンの都市ケーニヒスベルク（現在のロシア、カリーニングラード）はプレゲル川の両岸に位置し、クナイプホーフ島とロムゼ島という2つの大きな島があり、これらは7つの橋で互いに、そして都市の本土の2つの部分（旧市街と旧市街）と繋がっていた。問題は、これらの橋をそれぞれ1回ずつ渡るだけの市内散策ルートを考案することだった。
論理タスクを明確に指定する方法として、以下のいずれかを含むソリューション
明らかに容認できない。
オイラーは、この問題には解がないことを証明した。彼が直面した困難は、適切な解析手法の開発と、この主張を数学的に厳密に立証するその後の検証方法の開発であった。
オイラーは、各陸地内部の経路の選択は重要ではなく、経路の唯一の重要な特徴は渡る橋の順序であると最初に指摘しました。これにより、彼は問題を抽象的な用語で再定式化することができ（グラフ理論の基礎を築きました）、陸地のリストとそれらを結ぶ橋以外のすべての特徴を排除しました。現代の用語では、各陸地を抽象的な「頂点」またはノードに、各橋を抽象的な接続である「辺」に置き換えます。辺は、どの頂点（陸地）のペアがその橋で接続されているかを記録するだけの役割を果たします。結果として得られる数学的構造はグラフです。
→ 
→ 
接続情報のみが重要であるため、グラフの図解表現の形状は、グラフ自体を変更することなく、どのような形で歪められても構いません。重要なのは、各ノード間のエッジの数（ゼロの場合もある）のみです。例えば、描かれたエッジが直線か曲線か、あるいは一方のノードが他方のノードの左側にあるか右側にあるかは問題になりません。
次に、オイラーは、（歩行の終点を除いて）橋で頂点に入ると、必ず橋で頂点から出るということに気づいた。言い換えれば、グラフ内のどの歩行においても、終点以外の頂点に入る回数と、そこから出る回数は等しい。さて、すべての橋がちょうど一度渡られたとすれば、（開始と終了のために選ばれたものを除く）各陸塊について、その陸塊に接する橋の数は偶数でなければならない（特定の横断では、橋の半分は陸塊に向かって渡られ、残りの半分は陸塊から「離れる」方向に渡られる）。しかし、元の問題の4つの陸塊はすべて奇数個の橋に接している（1つは5つの橋に接し、他の3つはそれぞれ3つの橋に接している）。最大で2つの陸地が散歩の終点となり得るため、各橋を一度ずつ渡る散歩という提案は矛盾を生じさせる。
現代の言葉で言えば、オイラーは、グラフ上の各辺をちょうど一度ずつ通る経路が存在するかどうかは、ノードの次数に依存することを示した。ノードの次数とは、そのノードに接する辺の数である。オイラーの議論によれば、目的の経路が存在するための必要条件は、グラフが連結であり、奇数次数のノードがちょうど0個または2個存在することである。この条件は十分条件でもあることが判明した。これはオイラーが述べ、後にカール・ヒアホルツァーが証明した結果である。このような経路は、オイラーにちなんでオイラー路またはオイラーウォークと呼ばれるようになった。さらに、奇数次数のノードが存在する場合、オイラー経路は必ずそのうちの1つから始まり、もう1つで終わる。歴史的なケーニヒスベルクに対応するグラフには奇数次数のノードが4つあるため、オイラー経路は存在しない。
この問題の別の形式では、すべての橋を通り、かつ始点と終点が同じ経路を求めることが求められます。このような経路はオイラー回路またはオイラー巡回と呼ばれます。このような回路が存在するのは、グラフが連結であり、すべてのノードの次数が偶数である場合のみです。すべてのオイラー回路はオイラー経路でもありますが、すべてのオイラー経路がオイラー回路であるとは限りません。
オイラーの研究は1735年8月26日にサンクトペテルブルク科学アカデミーに提出され、1741年に雑誌『Commentarii academiae scientiarum Petropolitanae 』に『Solutio problematis ad geometriam situs pertinentis 』（位置の幾何学に関する問題の解）として掲載された。 [ 3 ]ジェームズ・R・ニューマン著『The World of Mathematics』に英語訳が掲載されている。
数学の歴史において、オイラーによるケーニヒスベルク橋問題の解は、グラフ理論の最初の定理であり、ネットワーク理論における最初の真の証明であると考えられている[ 4 ] 。ネットワーク理論は現在、一般的に組み合わせ論の一分野とみなされている。順列や組み合わせの列挙など、他のタイプの組み合わせ問題は古代から検討されてきた。
オイラーが、重要な情報は橋の数とその終点のリスト（正確な位置ではなく）であると認識したことは、トポロジーの発展を予見させるものでした。実際の配置とグラフの概略図との違いは、トポロジーが物体の固定的な形状に関心を持たないという考え方の良い例です。
したがって、オイラーが認識したように、「位置の幾何学」は「測定と計算」に関するものではなく、より一般的な何かに関するものである。これは、数学は「量の科学」であるという伝統的なアリストテレスの見解に疑問を投げかけるものであった。その見解は算術とユークリッド幾何学には当てはまるが、トポロジーや現代数学で研究されているより抽象的な構造的特徴には当てはまらなかった。[ 5 ]
哲学者たちは、オイラーの証明は抽象概念や現実のモデルに関するものではなく、橋の実際の配置に関するものであると指摘している。したがって、数学的証明の確実性は現実に直接適用できる。[ 6 ]また、この証明は説明的であり、結果が真でなければならない理由についての洞察を与えてくれる。[ 7 ]
元々の 7 つの橋のうち 2 つは第二次世界大戦中のケーニヒスベルクの爆撃で破壊されました。他の 2 つは後に取り壊され、高速道路に置き換えられました。残りの 3 つの橋は残っていますが、そのうちオイラーの時代のものは 2 つだけです (1 つは 1935 年に再建されました)。[ 8 ]これらの変更により、オイラーの問題に関係していた同じ場所に 5 つの橋が残っています。グラフ理論の観点から、現在では 2 つのノードの次数は 2 であり、他の 2 つのノードの次数は 3 です。したがって、オイラー経路は可能になりましたが、それは一方の島から始まり、もう一方の島で終わらなければなりません。[ 9 ]
クライストチャーチのカンタベリー大学は、旧物理科学図書館と数学、統計学、コンピュータ科学の学科が入っているアースキンビルの間の芝生エリアに橋の模型を組み込んでいる。[ 10 ]川は低い低木に置き換えられ、中央の島には石のトーローがある。ロチェスター工科大学は、 2014年にオープンしたアイスホッケーアリーナであるジーン・ポリッセニ・センター前の舗装にパズルを組み込んでおり、[ 11 ]ジョージア工科大学も2018年に7つの橋の景観アート模型を設置した。 [ 12 ]
このパズルの人気バリエーションは、ブリストル橋ウォークです。[ 13 ]歴史的なケーニヒスベルクと同様に、ブリストルは2つの川岸と2つの川の中州にまたがっています。[ 14 ]しかし、ブリストルにある45の主要な橋の配置は、オイラーの周回コースが存在するような形になっています。[ 15 ]このコースは、書籍[ 15 ]やニュース報道[ 16 ] [ 17 ]によって広く知られるようになり、さまざまなチャリティーイベントでも取り上げられています。[ 18 ]
