ケーニヒスベルクの橋の問題（読み）ケーニヒスベルクのはしのもんだい（英語表記）Königsberg bridge problem

ブリタニカ国際大百科事典 小項目事典

ケーニヒスベルクの橋の問題
ケーニヒスベルクのはしのもんだい
Königsberg bridge problem

18世紀の初め，プロシアのケーニヒスベルクで提示された数学の問題。ケーニヒスベルクを流れるプレーゲル川には，図のように七つの橋がかかっていた。問題は「プレーゲル川にかかる七つの橋を 2度通らずに，すべて渡る経路が存在するか」というものである。1735年にスイスの数学者レオンハルト・オイラーは，このような経路は存在しないことを証明して，問題を解決した。図の四つの土地の領域に点を対応させ，これらの土地を結ぶ七つの橋に対応して，四つの点を線で結ぶ。このようにいくつかの点（頂点）とそれらを結ぶ線（辺）でできた図形をグラフという。ケーニヒスベルクの橋の問題はこのようにしてできるグラフを一筆書きできるか，つまりペンを紙から離さず，同じ辺を 2度通らずに，すべての辺をたどることができるかという問題と同等である。一般に，連結したグラフが一筆書きできるためには次の条件のいずれかが満たされていなければならない。(1) すべての頂点について，集まる辺の本数が偶数である。(2) 集まる辺の本数が奇数であるような頂点が二つ存在し，ほかの頂点について，集まる辺の本数が偶数である。(1)の場合は閉じた経路になり，(2)の場合は始点と終点が異なる経路になる。ケーニヒスベルクの橋の問題は，対応するグラフがこれらの条件を満たさないことから解決される。オイラーの研究は，その後の位相幾何学（→トポロジー）とグラフ理論の発展の嚆矢となった。

出典　ブリタニカ国際大百科事典 小項目事典