ケーニヒスベルクの 7 つの橋の問題は、ケーニヒスベルク (現在のカリーニングラード) の街を有名にした歴史的な数学の問題です。その解決策は18世紀を通じて住民によって模索されました。
問題は次のとおりです。
- この都市が 6 つの橋で大陸に接続され、島と島の間が 1 つの橋でつながっている 2 つの島の上に建設されているとすると、選択した出発点から各橋を 1 回だけ通過し、元の場所に戻ることができる道を見つけてください。その出発点では、橋を通ることによってのみ水を渡ることができると理解されています。
トラブルシューティング
この問題は解決できず、この問題をグラフ理論の問題に還元することによって、この問題に最初の正式な数学的解決を与えたのはレオンハルト オイラーでした。彼のアプローチは次のように図式化できます。
次に、問題はオイラー サイクル(グラフのすべてのエッジを 1 回だけ通過し、開始点に戻るチェーン) の検索に帰着します。これは、問題に関連付けられたグラフに奇数次の頂点がない場合にのみ可能です。 。ケーニヒスベルク市には 4 つの橋があり (各岸は 3 つまたは 5 つの橋の始点です)、したがって、この問題には解決策がありません。
問題が開始点に戻らずに橋を 1 回だけ通過することで構成されていた場合、これはオイラー連鎖(グラフのすべてのエッジを 1 回だけ通過する連鎖) を検索することになります。これは、次の場合にのみ可能です。問題に関連するグラフには、奇数次数の頂点が 0 つまたは 2 つあります。 2 番目のケースでは、パスは奇数次数の頂点の 1 つから開始し、奇数次数のもう一方の頂点で終了する必要があります。
