ケーニヒスベルクの七つの橋：オイラーの問題とグラフ理論の起源（定義）

ケーニヒスベルクの七つの橋問題とオイラーの証明が生んだグラフ理論とトポロジーの起源を分かりやすく解説。

著者: Leandro Alegsa

19-09-2025 00:26

ケーニヒスベルクの7つの橋は、数学の歴史的に有名な問題である。レオンハルト・オイラーがこの問題を1736年に扱い（当時の解答は1736年の論文として知られる）、これをきっかけにグラフ理論が始まった。そして、これがトポロジーの発展にも影響を与えた。

プロイセンのケーニヒスベルク市（現ロシアのカリーニングラード市）は、プレゲル川の両岸に位置していた。市内には2つの島があり、それらは合計7つの橋で本土とおよび島同士を結んでいた。

問題の設定

この古典的な問題は単純に言えば次の通りである：街の中を歩いて、それぞれの橋をちょうど一度だけ渡るような経路（連続した道）を見つけることができるか、という問いである。橋以外に島へ行く手段はなく、橋を部分的に渡ることは認められない。出発点と到着点が同じである必要はない（閉路である必要はない）。オイラーはこの問題に対して、解は存在しないことを証明した。

グラフへの抽象化

オイラーの重要な着想は、実際の地図上で考えるのではなく、島や陸地の塊を点（頂点）で、橋を点と点を結ぶ線（辺）で表すという抽象化である。こうして得られる図を「グラフ」と呼ぶ。ケーニヒスベルクのケースでは陸地は4つの領域（2つの陸岸と2つの島）に対応し、それらを結ぶ7本の橋が7本の辺に対応する。

このグラフにおける各頂点の次数（頂点に接続している辺の本数）を見ると、ケーニヒスベルクの場合は4つの頂点の次数がそれぞれ 3, 3, 3, 5 となり、いずれも奇数である（総和は14で辺の本数は14/2=7）。このことが解の不存在を示す直接の手がかりとなる。

オイラーの証明（概略）

オイラーの議論の核心は「入る回数と出る回数」の考え方にある。ある頂点を経由して経路が通るたびに、通常はその頂点へ「入る」1回と「出る」1回がセットで生じる。そのため、経路で使われるその頂点に接続する辺の本数（使われる回数）は原則として偶数でなければならない。例外は経路の始点あるいは終点で、どちらかは入る回数と出る回数が一致しないため次数が奇数になりうる。

したがって、もしあるグラフが「各辺をちょうど一度ずつ通るような連続路（オイラー路）」を持つならば、そのグラフは少なくとも連結（辺をたどって全ての辺に到達できること）であり、奇次数の頂点は0個または2個でなければならない。奇次数の頂点が0個であれば始点と終点が同じ閉路（オイラー閉路）を持ち、ちょうど2個であれば始点と終点が異なるオイラー路が存在する。ケーニヒスベルクのグラフでは奇次数の頂点が4個存在するため（0でも2でもないため）条件を満たさず、よって解は存在しない、という結論になる。

定義（用語）

オイラー路（Eulerian trail / Eulerian path）：グラフの各辺をちょうど一度だけ通るような道。始点と終点が異なってもよい。
オイラー閉路（Eulerian circuit / Eulerian cycle）：始点と終点が同じで、全ての辺をちょうど一度ずつ通る閉じた道。
次数（degree）：頂点に接続している辺の本数。自己ループは次数を2増やすと数えるのが通常。
必要・十分条件（簡潔に）：グラフが連結で、奇次数の頂点が0個または2個であることは、それぞれオイラー閉路あるいはオイラー路の存在に対する必要かつ十分条件である（孤立頂点だけがある場合などの細部条件を除く）。

歴史的意義と現代での応用

ケーニヒスベルクの問題は一見単純な遊びだが、問題を抽象化して論理的に扱うという数学的なアプローチの好例であり、これが後のグラフ理論の始まりとなった。グラフ理論はネットワーク解析、ルーティング、回路設計、組合せ最適化、生物情報学（例えばゲノム配列再構成でのオイラー路の利用）など多くの分野で重要な役割を果たしている。また、位相幾何学（トポロジー）や平面グラフ、橋の可視化問題などにもつながっている。

まとめると、ケーニヒスベルクの七つの橋の問題は、実際の地図の問題をグラフという抽象的な記号体系に置き換えることで、単純かつ強力な一般理論（オイラー路・オイラー閉路の条件）を生み出した点で重要である。これによって「なぜ解がないのか」を単なる経験的観察でなく数学的に説明できるようになった。

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となり、オイラー型経路が可能となるが、一方の島から出発し、もう一方の島で終了しなければならないため、観光客にとっては現実的でなくなる。

質問と回答

Q: ケーニヒスベルクの7つの橋問題とは何ですか?

A: 「ケーニヒスベルクの7つの橋」は有名な数学の問題で、7つの橋を一度だけ渡って街を歩く方法を見つけるというものです。

Q: 「ケーニヒスベルクの7つの橋」問題を解いたのは誰ですか?

A: レオンハルト・オイラーは1735年にケーニヒスベルクの7つの橋の問題を解きました。

Q: 「ケーニヒスベルクの7つの橋」問題の解決は何をもたらしましたか?

A: 「ケーニヒスベルクの7つの橋」問題の解決は、グラフ理論の始まりにつながり、それが位相幾何学の発展につながりました。

Q:ケーニヒスベルクはどこにあるのですか?

A:ケーニヒスベルクはプロイセンにあり、現在はロシアのカリーニングラードに属しています。

Q: ケーニヒスベルクの地形は?

A: ケーニヒスベルクはプレゲル川の両岸にあり、2つの大きな島が7つの橋で本土とつながっていました。

Q: ケーニヒスベルクの7つの橋の問題を解くための条件は何でしたか?

A: この問題では、各橋を一度だけ渡り、すべての橋を毎回完全に渡って街を歩く方法を見つける必要がありました。島々には橋以外のルートでは行けませんし、歩き始めと終わりは同じ場所である必要はありません。

Q: オイラーはケーニヒスベルクの7つの橋の問題に解があることを証明したのですか?

A: いいえ、オイラーはケーニヒスベルクの7つの橋問題には解がないことを証明しました。

百科事典を検索する