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