ケーニヒスベルクの橋

デジタル大辞泉

ケーニヒスベルク‐の‐はし【ケーニヒスベルクの橋】

読み方：けーにひすべるくのはし

グラフ理論の端緒となった一筆書きの問題。ケーニヒスベルク（現カリーニングラード）に架かる七つの橋を1回ずつ渡って出発点に戻る道筋があるかどうかを問うもの。1736年、レオンハルト＝オイラーは道筋を頂点と辺からなる単純なグラフに置き換えたとき、すべての頂点からつながる辺の数が偶数の場合、または奇数である頂点が二つで、残りのすべての頂点は偶数の場合に限り、一筆書きが可能であることを証明した。これにより、ケーニヒスベルクの橋を一筆書きで巡ることはできないことを示した。ケーニヒスベルクの問題。

ウィキペディア小見出し辞書

ケーニヒスベルクの橋 （第18話 『凍てつく鉄槌』）

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/18 15:17 UTC 版)

「Q.E.D. 証明終了」の記事における「ケーニヒスベルクの橋 （第18話 『凍てつく鉄槌』）」の解説

ケーニヒスベルクを流れる川ある7つの橋を、「1度だけ通ることで、元の場所に戻ってくることが可能か」という問題。つまり、一筆書きが可能かを示した問題である。