ケーニヒスベルクの橋

1,ケーニヒスベルクの橋

18世紀の初め，プロシアのケーニヒスベルクで提示された数学の問題。


ケーニヒスベルクを流れるプレーゲル川には，図のように七つの橋がかかっていた。

問題は「プレーゲル川にかかる七つの橋を 2度通らずに，

すべて渡る経路が存在するか」というものである。



1735年にスイスの数学者レオンハルト・オイラーは，

このような経路は存在しないことを証明して，問題を解決した。


図の四つの土地の領域に点を対応させ，

これらの土地を結ぶ七つの橋に対応して，四つの点を線で結ぶ。


このようにいくつかの点（頂点）とそれらを結ぶ線（辺）でできた図形をグラフという。


ケーニヒスベルクの橋の問題はこのようにしてできるグラフを1筆書きできるか，





つまりペンを紙から離さず，同じ辺を 2度通らずに，

すべての辺をたどることができるかという問題と同等である。




一般に，連結したグラフが1筆書きできるためには

次の条件のいずれかが満たされていなければならない。

(1) すべての頂点について，集まる辺の本数が偶数である。

(2) 集まる辺の本数が奇数であるような頂点が二つ存在し，

ほかの頂点について，集まる辺の本数が偶数である。



(1)の場合は閉じた経路になり，

(2)の場合は始点と終点が異なる経路になる。


ケーニヒスベルクの橋の問題は，

対応するグラフがこれらの条件を満たさないことから解決される。

オイラーの研究は，

その後の位相幾何学（→トポロジー）とグラフ理論の発展の嚆矢となった。