グラフ理論の覚え書き

最近読んだネットワークについての本に影響を受けて、それに関連した数学分野であるグラフ理論の本を読み始めた。以下はその覚え書き。

グラフ理論といえば

・ケーニヒスベルクの問題
・巡回セールスマン問題
・4色問題

などが有名。それぞれどのような問題化というと、
・ケーニヒスベルクの問題―ケーニヒスベルクにある7つの橋を、どの橋も2度渡ることなく全て渡って元の場所に戻ることができるかどうか。

Wikipedia:ケーニヒスベルクの問題

・巡回セールスマン問題―セールスマンがいくつかの都市を訪ね、出発点に戻るのだが、その際、各都市を正確に1回だけ訪ね、旅行の総距離をできるだけ短くするにはどうすればよいか。

Wikipedia:巡回セールスマン問題

・四色問題(現在は証明されて四色定理と呼ばれる)―いかなる地図も隣接領域が異なる色で塗り分けるには4色でできるかどうか。

Wikipedia:四色定理

このうち巡回セールスマン問題と4色問題は簡単な問題ではないらしい。特に4色問題は普通に塗り絵すればなんとなく4色あれば塗り分けられるってのは分かるのに、その証明となると全く歯が立たなかったそうな。ちなみに現在はコンピュータを使って証明され、それがコンピュータによる数学証明の第1号となっている。

ケーニヒスベルクの問題については問題なく解くことができる。まず上の画像の青い点をノードとし、ノードを結ぶ線をリンクと呼ぶ(グラフ理論ではノードを点や頂点、リンクを辺やエッジと呼ぶ)。証明は「奇数の数のリンクを持つノードは、出発点であるか、もしくは終着点でなければならない」というもの。全ての橋を1度だけ渡る経路には、出発点と終着点がそれぞれ1つしかないはず。したがって、奇数のリンクを持つノードを3つ以上持つグラフでは、条件を満たす経路は存在しない。ケーニヒスベルクのグラフには、奇数のリンクを持つノードが4つあるから、条件を満たす経路は存在しない。

上の証明は天才数学者オイラーによるもの。もともとのケーニヒスベルクの地図

をグラフで表して考えたのはおそらく彼が初めて。その意味でオイラーはグラフ理論の創始者といえるのだろうね。

もっと数学的な証明についてはまたいずれ書く予定。まあまだまだ先のことになりそう。外がまた暑くなってやる気が起きないし(現在引きこもり3日目。家でぐだぐだしたいでござるよ)。早く涼しくならないかと思う今日この頃。

参考文献

新ネットワーク思考―世界のしくみを読み解く