解ける? 解けない?
ケーニヒスベルクの7つの橋について、先に点線で示した部分をあらためて実線で書くと、図3のようになります。
図中に示した各点に集まっている線の数を見ると、どの点にも奇数本の線が集まっています。奇数本の線が集まっている点が4個あるので、一筆書きができないことがわかります。
つまり、ケーニヒスベルクの7つの橋の問題は不可能だったのです。
「点と線のつながり」に注目しよう
図1~3の一筆書きの問題では、線の形や長さは関係なく、「どの点が結ばれているか」だけが問題になります。たとえば、図1が一筆で書けるかという問題は、図4などのようになっても変わりません。角度や長さは問題ではなく、各点とそれを結ぶ線の位置関係だけが問題なのです。
このように、点と線のつながりに着目した図形のことを「グラフ」といい、グラフの性質を調べる数学を「グラフ理論」とよびます。
ここでいうグラフは、中学・高校で習ったy=x²のような関数のグラフとは別のものです。そしてグラフの幾何学は、小学から高校までで習う幾何学とはかなり異なります。
実社会で役立っている理論
では、このようなグラフの性質を調べて役に立つかということですが、グラフ理論は応用上、非常に重要な理論です。
たとえば、一筆書きの問題は、輸送経路の問題に関係します。点を家、線を道路と考えると、同じ道を通らずにすべての家を訪問できるかという問題になります。つまり、効率的な訪問をすることに関係します。
一筆書きは途中の点は何度通ってもいいという条件ですが、もっと効率的な問題として、与えられたグラフにおいて、「途中のすべての点を一度だけ通って出発点に戻ってくることができるか」という問題が考えられます。
このような問題を「ハミルトンの問題」といい、一筆書きのような判定条件はまだ見つかっていません。未解決の問題です。
【西来路文朗さん、清水健一さんの著作はこちら】