7 本の橋
ケーニヒスベルクは、バルト海に近いプロイセンの港町だった。いまはロシア領のカリーニングラードである。まちの真ん中をプレーゲル川が流れ、中の島クナイプホーフを囲んで二手に分かれる。島の東には、2 本の流れにはさまれたもう 1 つの土地がある。
北の岸・南の岸・中の島・東の土地。この 4 か所を、18 世紀の初めには 7 本の橋がつないでいた。中の島から北の岸へ 2 本、南の岸へ 2 本、東の土地へ 1 本。東の土地から北と南の岸へ 1 本ずつ。
7 本の橋を、どれもちょうど 1 度ずつ渡ってまちを歩けるか。これがケーニヒスベルクの橋の問題である。
問題を解いたレオンハルト・オイラーは、論文の第 2 節でこう書いている。この問いについて、できないと言う人もいれば、疑っている人もいたが、できると言い切る人は誰もいなかったと聞いた。まちの人が日曜の散歩で試していた、という話もよく語られる。ただし、そこまで細かい場面を書いた当時の記録は見つかっていない。
問題は手紙でオイラーのもとに届いた。橋の問題に触れた手紙で残っているのは、のちにダンツィヒ(いまのポーランドのグダニスク)の市長になるカール・エーラーとの 1736 年のやり取りである。エーラーは同じまちの数学者ハインリッヒ・キューンとともに、プロイセンの数学を盛り立てようとしていた。3 月の手紙でエーラーは、解き方を証明つきで知りたい、これは「位置の計算」の見事な例になる、と書いた。
4 月の返事で、オイラーはそっけない。この種の解き方は数学とはほとんど関係が無く、理屈だけで片づく、と書いている。一方、同じ年の 3 月 13 日にイタリアの数学者ジョヴァンニ・マリノーニに宛てた手紙では、少し違う顔を見せた。この問いはありふれているが、幾何学でも代数でも数え上げの技でも解けないので、目を向ける値打ちがあると思った、と。
ありふれた散歩の問いが、長さも角度も使わない新しい数学の入口になった。
起源
オイラーの論文の題は「位置の幾何学に関わる問題の解」(Solutio problematis ad geometriam situs pertinentis)である。サンクトペテルブルクの科学アカデミーで 1735 年 8 月 26 日に発表された記録があり、紀要の 1736 年の巻(第 8 巻)に載った。実際に印刷されたのは 1741 年である。橋の問題に触れた手紙で残っているのは、発表より後の 1736 年のものである。問題がいつ最初にオイラーへ伝わったのかは、はっきりしない。
「位置の幾何学」は、ライプニッツが望んだ学問の名前だった。長さや角度を測らずに、ものの並び方だけを扱う幾何学である。オイラーは第 1 節で、橋の問題はまさにその種類のものだと書いた。橋の長さも川の幅も答えに関係しない。どの土地とどの土地が、何本の橋でつながっているか。決めるのはそれだけである。
オイラーは 4 つの土地に A・B・C・D の文字を付け、歩く道を、通る土地の文字の並びで書いた。橋を 1 本渡るごとに文字が 1 つ増えるので、7 本を渡る道は 8 文字になる。この数え方から次の規則を導いた(第 20 節)。奇数本の橋がかかる土地が 3 つ以上あれば、道は無い。ちょうど 2 つなら、道はその一方から始まり、もう一方で終わる。1 つも無ければ、どこから始めてもよい。
いま教科書に載っている「土地を点、橋を線で描いた図」は、オイラーの論文には 1 枚も出てこない。この描き方は、のちの時代に広まったものである。
オイラーがきちんと示したのは、奇数の土地が多すぎれば道は無い、という向きだけだった。条件を満たせば道が必ずある、という逆向きを最初に完全に証明したのは、ドイツのカール・ヒールホルツァーである。ヒールホルツァーは 1871 年に亡くなり、論文は 1873 年に『数学年報』(Mathematische Annalen)第 6 巻に載った。点と線のつながりだけを扱うこの考え方は、20 世紀にグラフ理論と位相幾何学(トポロジー)という 2 つの分野に育つ。
橋はその後、戦争で姿を変えた。第二次世界大戦の空襲で 7 本のうち 2 本が失われ、さらに 2 本がのちに取り壊されて幹線道路の橋に置き換えられた。同じ 4 つの土地をつなぐ橋は、いま 5 本ある。北と南の岸には 2 本ずつ、中の島と東の土地には 3 本ずつかかる。奇数の土地が 2 つになったので、中の島と東の土地の一方から始めて、もう一方で終わる一筆書きの散歩が、いまはできる。
証明
土地を点(頂点)、橋を線(辺)とみなす。点の集まりを 、線の集まりを 、点 に集まる線の本数を の次数 と書く。同じ 2 点を結ぶ線が何本あってもよい。オイラーにならって、中の島を 、東の土地を 、2 つの岸を ・ と呼ぶ。
-
線は 1 本につき両端が 2 つある。それぞれの端は、どこかの点の次数に 1 ずつ数えられる。よって
-
右辺は偶数である。偶数の次数を左辺から引いても偶数が残るので、奇数の次数だけを足した和も偶数になる。奇数をいくつか足して偶数になるのは、足した個数が偶数のときだけである。よって次数が奇数の点は偶数個ある。
-
すべての線を 1 度ずつ通る道があるとする。途中で通り過ぎる点では、入る線と出る線が 1 本ずつ組になって使われる。その点を 回通り過ぎるなら
-
したがって次数が奇数になりうるのは、道の始まりの点と終わりの点だけである。始まりと終わりが同じ点なら、そこも入りと出が組になって偶数になる。よって、奇数の点は 0 個か 2 個でなければならない。
-
ケーニヒスベルクの次数は、中の島が 5、ほかの 3 か所がどれも 3 である。
-
奇数の点が 4 つあるので、7 本の橋を 1 度ずつ渡る道は無い。オイラー自身の数え方でも同じになる。橋が 本(奇数)の土地の文字は、道の並びに 回現れなければならない。その合計は で、8 文字の並びに収まらない。
逆向きは、ヒールホルツァーの方法で示せる。すべての点が偶数で、線でひと続きにつながっているとする。どこかの点から、まだ使っていない線を選んで歩き続ける。どの点も偶数なので、入った点からは必ず出られ、行き止まるのは始めの点に戻ったときだけである。使っていない線が残っていれば、それは歩いた道のどこかの点から出ている(ひと続きだから)。そこから同じように歩いて輪を作り、元の道に差し込む。これを繰り返せば、すべての線を使い切る。奇数の点が 2 つのときは、その 2 点を仮の線で結んで同じことをし、最後に仮の線を外せばよい。
応用
一筆書きの図。 正方形に 2 本の対角線を引き、上に三角の屋根を載せた「家」の図は、一筆書きの定番である。次数は、下の 2 つの角が 3、上の 2 つの角と対角線の交わりが 4、屋根の頂点が 2 になる。奇数の点が下の 2 つの角だけなので、一筆書きはできる。ただし、下の角の一方から始めて、もう一方で終わる道しかない。
何筆で描けるか。 ひと続きの図で奇数の点が 個あれば、ちょうど 筆で描ける( のとき)。ケーニヒスベルクの 7 本の橋は奇数の点が 4 つなので 2 筆である。言い換えると、橋を 1 本だけ 2 度渡ることにすれば、8 回の横断で全部の橋を渡れる。中の島と東の土地を結ぶ橋を 2 度渡ると、次数は になり、奇数は北と南の岸だけになる。北の岸から歩き始めれば、南の岸で歩き終わる。
郵便配達の道順。 すべての道を少なくとも 1 度通って出発点に戻る、いちばん短い道順を探す問題を「郵便配達問題」という。中国の数学者、管梅谷の論文(英訳は 1962 年)で広く知られた。奇数の点どうしを組にして、間の道をもう 1 度通ることにすれば、すべての点が偶数になって一筆書きに戻せる。どう組むと足す道が最も短いかが、問題の中心になる。ごみの収集車、除雪車、道路の点検車の道順づくりに使われている。
描く機械の動き。 刃やペンを紙から上げずに動ける時間が長いほど、切り抜きやペン描きの機械は速く終わる。図を何筆に分けるかは、奇数の点の数で決まる。
図示
シミュレーション
地図の橋をたたくと、その橋が消えたり戻ったりする。点線の四角は、新しく橋をかけられる場所である。右の図の丸の数字が次数で、奇数の点は塗りつぶされる。奇数の点が 0 個か 2 個になると、歩く点がすべての橋を 1 度ずつ渡ってみせる。奇数の点が 4 つのままだと、歩く点はどこかで行き止まる。
広がる学問
- 数学 点と線のつながりだけを扱うグラフ理論は、この論文を出発点とする。オイラーはのちに、多面体の頂点・辺・面の数の関係 も見つけた(オイラーの多面体定理)。長さを忘れて形のつながりだけを見る見方は、位相幾何学へ育った。
- 情報科学 道路網や通信網、ウェブのリンクはグラフとして表され、最短の道や経路の探索が計算される。すべての辺を 1 度ずつ通る道を探す計算は、線の本数に比例する手間で済む。すべての点を 1 度ずつ通る道(ハミルトン路)を探す問題は、効率の良い解き方が知られていない。似た問いでも難しさが大きく違う。
- 生物学 DNA の配列を読む機械は、長い配列を短い断片に切って読む。断片をさらに長さ の短い文字列に切り、その 1 つ 1 つを辺、前後で重なる長さ の部分を点とするグラフを作る。すると元の配列を組み立てる問題が、すべての辺を通るオイラー路を探す問題になる。2001 年にペヴズナーらが示し、短い断片から組み立てる道具の多くが、この考え方を使う。
- 工学 ごみ収集・除雪・道路点検の車の道順は、郵便配達問題として計算される。ペンや刃を紙から上げずに動かす時間を長くしたい描画機や切断機の道順でも、同じ数え方が使われる。
参考文献
- L. Euler, "Solutio problematis ad geometriam situs pertinentis", Commentarii academiae scientiarum Petropolitanae 8 (1736, 印刷 1741), 128-140.(Eneström 番号 E53)
- N. L. Biggs, E. K. Lloyd, R. J. Wilson, Graph Theory 1736-1936, Oxford University Press, 1976.(オイラーの論文の英訳を収める)
- B. Hopkins, R. J. Wilson, "The Truth about Königsberg", The College Mathematics Journal 35 (2004), 198-207.
- C. Hierholzer, "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren", Mathematische Annalen 6 (1873), 30-32.
- 管梅谷 (Kwan Mei-Ko), "Graphic programming using odd or even points", Chinese Mathematics 1 (1962), 273-277.
- P. A. Pevzner, H. Tang, M. S. Waterman, "An Eulerian path approach to DNA fragment assembly", PNAS 98 (2001), 9748-9753.