ケーニヒスベルクの七つの橋
解決済み、1736年組合せ論と離散数学
問題の内容
ケーニヒスベルク市(現在のカリーニングラード)はプレーゲル川の両岸と二つの島の上に築かれ、七つの橋で結ばれている。市内を歩いて七つの橋をそれぞれちょうど一度ずつ渡り、同じ橋を二度渡らずに済ませることは可能だろうか?
オイラーのもとの議論は偶奇性に関する数論的な議論であり、まだ現代的なグラフの言葉で書かれた証明ではなかった。当時は「グラフ」「頂点」「辺」という概念自体がまだ存在していなかった。
頂点の次数だけが重要であり、幾何学的な配置は関係ないというオイラーの洞察が、グラフ理論の出発点となった。彼が発見した一般的な基準は、今日オイラー閉路定理と呼ばれ、連結グラフがすべての辺をちょうど一度ずつ通る閉じた経路を持つのは、すべての頂点の次数が偶数のときに限る、というものである。また、すべての辺をちょうど一度ずつ通る開いた経路、すなわちオイラー路が存在するのは、奇数次数の頂点がちょうど0個か2個のときに限る。
参考文献
- Leonhard Euler (1741). Solutio problematis ad geometriam situs pertinentis · DOI:10.1090/spec/098/33
- Norman L. Biggs, E. Keith Lloyd, Robin J. Wilson (1976). Graph Theory 1736–1936