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

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

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

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

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

百科事典マイペディア

ケーニヒスベルクの橋の問題【ケーニヒスベルクのはしのもんだい】

ケーニヒスベルク（カリーニングラード）の七つの橋を，同じ橋を２度渡ることなく次々に全部渡ることができるかどうかという問題。18世紀ごろ市民間で話題になり，オイラーが経路を変形して一筆書きの問題とし，奇数個の線の集まる点がA，B，C，Dと４個あることから，不可能なことを証明した。位相幾何学の初歩的な例として有名。

出典　株式会社平凡社