コトバンクはYahoo!辞書と技術提携しています。

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

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

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

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

出典 ブリタニカ国際大百科事典 小項目事典ブリタニカ国際大百科事典 小項目事典について 情報

百科事典マイペディアの解説

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

ケーニヒスベルク(カリーニングラード)の七つの橋を,同じ橋を2度渡ることなく次々に全部渡ることができるかどうかという問題。18世紀ごろ市民間で話題になり,オイラーが経路を変形して一筆書きの問題とし,奇数個の線の集まる点がA,B,C,Dと4個あることから,不可能なことを証明した。

出典 株式会社日立ソリューションズ・クリエイト百科事典マイペディアについて 情報

ケーニヒスベルクの橋の問題の関連キーワード武田真元

今日のキーワード

だまし面接

企業が面談や懇談会と称して就職活動中の学生を呼び出し、実質的には学生を選考する偽装面接のこと。2016年卒業の大学生に対する選考活動の開始時期を、従来の4月1日から8月1日以降へと後ろ倒しする主旨の「...

続きを読む

コトバンク for iPhone

コトバンク for Android