📂グラフ理論

ケーニヒスベルクの橋の問題とその解決

問題 ¹

ケーニヒスベルクの橋の問題は、この都市にかかっている7つの橋を一度だけ渡って、最初の位置に戻ることができるのかということだった。解法を知らない場合、すぐには場合の数を全て試してみなければならない途方もない問題に見える。一見すると数学の問題にも見えず、全てのケースを試せば解けそうだが、実際には試すのも容易ではない。

偉大なる数学者オイラーは、この問題をグラフ問題に変えて見事に解決した。驚くべきは、グラフ理論が当時、学問の注目を浴びておらず、空間を位相的に見るという発想自体がなかった時の解法であることだ。言い換えれば、オイラーは未来の概念を持ち込んで未来の方法で問題を解決したのである。それでは、その解法を見てみよう。

解答

上の画像を簡単に図式化すると、次のようになる。

ここで、川で分けられた地域をそれぞれの頂点とし、地域をつなぐ橋をエッジとして表すグラフを考えると、次のようになる。

さて、ケーニヒスベルクの橋の問題は、上のグラフで全てのエッジを含み（全ての橋を渡りつつ）、閉じた（最初の位置に戻る）トレイル（方法）があるか否かを判断するグラフ問題に変わった。このように、すべてのエッジを含む閉じたトレイルが存在するグラフをオイラー・グラフという。

オイラーの定理: $G$ が 連結グラフであるとする。$G$ がオイラー・グラフであることと、$G$ の全ての頂点の次数が偶数であることは等価である。

一方、オイラー・グラフの等価条件によれば、奇数の次数を持つ頂点がたとえ一つでも存在すれば、オイラー・グラフではない。上のグラフは、全ての頂点の次数が奇数であるため、オイラー・グラフではない。これは、ケーニヒスベルクの橋を全て渡って、最初の位置に戻る方法が存在しないことを意味する。

■