ケーニヒスベルクの7つの橋

オイラー解析

まず、オイラーは、各陸塊内部のルートの選択は重要でないことを指摘した。ルートの唯一の重要な特性は、橋を渡る順序である。そこで、彼は問題を抽象的な言葉に変えた。これが、グラフ理論の基礎となった。陸地とそれを結ぶ橋のリスト以外の特徴をすべて取り除いたのだ。グラフ理論で言えば、陸塊の1つ1つを抽象的な「頂点」、つまりノードに置き換えたのである。そして、橋は「辺」と呼ばれる抽象的なつながりに置き換えた。エッジ（道路）には、2つの頂点（陸塊）がどのようにつながっているかが記録されている。こうして、グラフができあがる。

→ →

描かれたグラフは、問題を抽象化したものである。だから、辺のつなぎ方は自由である。2点がつながっているかどうかだけが重要である。グラフの絵を変えても、グラフそのものは変わりません。

次にオイラーは、（歩行の終点を除いて）橋によって頂点に入るときは必ず、橋によってその頂点を離れることを観察した。グラフの歩き方において，ある頂点に入った回数と出た回数は等しい．すべての橋が一度だけ渡ったのであれば，それぞれの土地（スタートとゴールに選ばれたものは除く）に対して，その土地に接している橋の数は偶数でなければならないことになる．橋がn本あれば、ちょうど2n回渡れるからである。しかし，元の問題の4つの陸塊はすべて奇数の橋がかかっている（1つは5本，他の3つはそれぞれ3本）．散歩の終点になりうる陸塊はせいぜい2つである．従って，橋を1回ずつ渡るという命題は矛盾を引き起こす．

現代の言葉で言うと、オイラーは、グラフを歩いて各辺を一回ずつ横切ることが可能かどうかは、ノードの度合いに依存することを示した。ノードの次数とは、それに接する辺の数である。オイラーは、グラフがつながっていて、奇数次数のノードがちょうど0個か2個あることが、歩行の必要条件であることを示した。このオイラーが述べた結果は、後にカール・ヒアホルツァーによって証明された。このような歩みは、現在ではオイラー歩と呼ばれている。奇数次数のノードがあれば、オイラー経路はそのうちの1つから始まり、もう1つのノードで終わることになる。歴史的なケーニヒスベルクを表すグラフには、奇数次のノードが4つあるので、オイラー経路を持つことができない。

オイラーの作品は、1735年8月26日、サンクトペテルブルグ・アカデミーに提出された。1741年に雑誌Commentarii academiae scientiarum PetropolitanaeにSolutio problematis ad geometriam situs pertinentis（位置の幾何学に関する問題の解）として発表された。英語版はThe World of Mathematicsに掲載されている。

数学史における重要性

数学の歴史では、オイラーのケーニヒスベルクの橋の問題の解答が、グラフ理論の最初の定理とされている。グラフ理論は、現在では一般に組合せ論の一分野とみなされている科目である。

橋梁の現況

当初7本あった橋のうち2本は、第二次世界大戦中のケーニヒスベルク空襲で破壊された。他の2つの橋は後に取り壊されました。その代わり、近代的な高速道路が建設されました。他の3つの橋は残っているが、そのうちの2つだけがオイラー時代のものである（1つは1935年に再建された）。このように、2000年現在、カリーニングラードには5つの橋がある。

グラフ理論的には、2つのノードが次数2、残りの2つが次数3となり、オイラー型経路が可能となるが、一方の島から出発し、もう一方の島で終了しなければならないため、観光客にとっては現実的でなくなる。

関連ページ

• イコジゲーム
• ハミルトンパス
• 水道・ガス・電気
• じゅんかいセールスマンのもんだい