>>901
バルト海に面するケーニヒスベルク(かつてはプロシア王国領土)は水運の
街としても有名であり、分岐と合流を繰り返すプレーゲル川がその主役となっていた。
この川の支流に挟まれたクナイプホープ島には大聖堂があり、周辺には7本の橋がかかっていた。
そこで暮らす住民のひとりがある疑問を抱いた。
「7つの橋を1回しか通らずにすべて渡りきることはできるのか?」
このときから7つの橋めぐりへの挑戦が住民の間で始まったが、誰も成功しなかった。
18世紀最大の数学者とされるスイス出身のレオンハルト・オイラーがこの問いに目をとめた。
彼は問題を単純化し、橋を線で、橋がつなぐ各区域を点で表した。
(具体的に言うと、橋とそれらがつなぐ岸を簡略化した図を書き、奇頂点(線の数が奇数の点)を
数えた。)
そして、この図は「一筆書きできるか」と問うた。
オイラーは、橋を1回ずつ通るためには、奇頂点が0か2の場合のみ可能であると示した。
一筆書きが可能な図の条件は下記の二つである。↓
頂点に接続してる辺の本数をその頂点の「次数」とした場合、
�@全ての頂点の次数が偶数である。
�A次数が奇数となる頂点が2つで、残りの頂点の次数が全て偶数である。
(次数が奇数となる頂点が2つのみで、他に頂点がなくてもよい)

ケーニヒスベルクの橋の模式図を見ると、5本の線がつながっている点がひとつで、残りの点は線が
3本つながっている。つまり、上記二つの条件にあてはまらないため、一筆書きができない=7つの橋を1回ずつ
渡ることは不可能であることを示した。

ちなみにオイラーはこのルールをさらに一般化し、点と線で描かれる図では、点と面を足した数が、線の数より1だけ多いことを示した。
これをオイラーの関係式という。(点(V)+面(R)-線(L)=1)※これはどんなに複雑な図でも成り立つという。
図に線を1本書き加えると点もしくは面がひとつ増え、元の関係性が保たれるためである。

ケーニヒスベルクの7つの橋は後世のトポロジーの起源であり、最も効率のよい道筋を探す
ネットワーク問題の基本でもあると言われている。

面白いよね?