Ｐ１６ ケーニヒスベルクの橋
前回「大統領の握手数は？」という問題の解答をやりました。解答の際、人物を円で表しました。そして握手することを、円と円を線で結ぶという形で表しました。
実はその解答法、【グラフ理論】で用いられる手法なのです。
簡単に【グラフ理論】というものを紹介しますとですね……
頂点と辺で構成される【グラフ】を扱う数学の一分野
です。いや、ホント簡単に紹介してますが。笑
高校数学で学ぶ、【２次関数のグラフ】とか【三角関数のグラフ】とは違う意味の【グラフ】を扱う事になります。【頂点】とはなんぞ、【辺】とは何ぞと説明するより、具体的な例で理解してもらう事にします。
例えばこの図形も【グラフ理論】における【グラフ】になりますが……
６つの【頂点】と
１０本の【辺】を持つ【グラフ】となります。これで【頂点】と【辺】というものがおわかりになったでしょう。
突然ですが……
みなさんは、この図形を一筆書きで描く事が出来ますか？
同じ頂点を何度通っても構いませんが、同じ辺は２度通る事は出来ません。
頂点につけた数字で説明すると、例えば
３→６→５→１→２→６→４→５→２→３→４
といけば、一筆書き出来る事が確認出来るハズ。では次。
この図形は一筆書き出来るでしょうか？
その答は後半で。
☆★
冒頭で出てきた【グラフ理論】。その発端は、かの有名な数学者【レオンハルト・オイラー】。彼については語りたいことが山ほどありますが、今回は【グラフ理論】の話だけに集中します。
時は１８世紀。当時プロイセン王国の首都はケーニヒスベルク（現ロシア領）という町でして、そこには
このような地形の場所がありました。水色の部分は川が流れていて、白色部分は陸地と陸地を結ぶ橋となります。橋は７つありますが、わかりやすいように番号をふっておきます。
さて。当時の町の人々の間で
７つの橋を全て渡り、元の場所へ戻るにはどのように行けばよいか？
ただし，同じ橋を２度わたってはいけない （※出発地点はどこでもよい）
という問題が話題になっていました。いっけん簡単そうな問題ですが、答に辿り着く者はいつまでたっても現れない。
たまたまこの地を訪れていた大数学者【レオンハルト・オイラー】。町の人が彼にその問題を質問したところ彼はこう言いました。
どんなに知恵をしぼっても、出来ない
これを聞いた町の人は
すごい数学者と名高い、オイラー先生でも出来ない？
と思いましたが、オイラーはこう言うのです。
誰がどんな方法をとろうと、それは出来ないという意味だ
オイラーは
そもそも条件に合うような橋の渡り方自体が存在しない
として、町の人々に向けて説明を始めました。
★☆
オイラーの説明に対し、町の人々は首をかしげたそうです。いわゆる
イマイチ理解出来ない
状況で、オイラーはさらにくわしい説明をしたとか。
オイラーがどのように説明したかはともかく……
今回はみなさんに、一筆書きが可能かどうかの判定法をお教えします。いわゆる【一筆書きの定理】と呼ばれるものです。
まず、ケーニヒスベルクの橋の問題を、【頂点】と【辺】を扱う【グラフ理論】の問題に置き換えます。
この図について、陸地になってる部分に【頂点】を配置。
こんな感じで、４つの頂点が配置されます。
わかりやすいように、【頂点Ａ】～【頂点Ｄ】と名前をつけておきます。
橋以外の境界線を消して
橋の部分を図のように【グラフ理論】における【辺】で表します。これで４つの【頂点】と７つの【辺】からなる、立派な【グラフ】が完成しました。
少しだけ【グラフ】の【頂点】における【次数】の説明を。
頂点に接続してる辺の本数をその頂点の【次数】と言います。
この【グラフ】の場合、頂点Ａには①,②，⑤の３本の辺が接続しているので
頂点Ａの次数は３
となります。頂点Ｂには①，②，③，④，⑦の５本の辺が接続しているので
頂点Ｂの次数は５
となります。以下、同様に
頂点Ｃの次数は３ 頂点Ｄの次数は３
となるのを確認して下さい。
では。証明とか抜きに、【オイラーの一筆書きの定理】を紹介しましょう。この定理によれば、グラフが一筆書き出来るパターンは２つ。
ｃａｓｅ１ 全ての頂点の次数が偶数である
ｃａｓｅ２ 次数が奇数となる頂点が２つで、残りの頂点の次数が全て偶数である
（次数が奇数となる頂点が２つのみで、他に頂点がなくてもよい）
この２パターンが
一筆書き出来るための必要十分条件
なのです。逆に言えばこのパターンに当てはまらないグラフは、一筆書きが不可能であるとオイラーが証明したんですね。
ちなみに「ｃａｓｅ１」のグラフは、どこからスタートしても（辺の途中でもＯＫ）うまく進めば、一筆書きで元の場所に戻って来られます。「ｃａｓｅ２」のグラフは、スタートは必ず次数が奇数の点で、ゴールはもう１つの次数が奇数の点になるよううまく進めば、一筆書きが可能です。
とまぁ、この【一筆書きの定理】を頭に入れると
ケーニヒスベルクの橋のグラフは、４つの頂点全ての次数が奇数であるため、一筆書きは不可能。すなわち
７つの橋を１回ずつ渡って、元の場所に戻ることは出来ない
という事になります。
★☆
オイラーの示した【一筆書きの定理】は、【グラフ理論】の起源と言われ、数学の世界では広く知られた定理です。
初心者にとってもこの定理は理解しやすいため、アマチュア数学愛好家にも有名な定理となっております。この記事を読んだ方も是非【一筆書きの定理】を覚えて、何か図形を見たら
あ、これは一筆書き出来るや いや、できねー！
なんて判定するのもいいでしょう。
と、いうわけで……
この図形。一筆書きは出来ますか？
★☆
実は以前紹介した４色問題もグラフ理論の問題として捉える事が出来たりするんです。
グラフ理論は、パイプラインの配置や集積回路の設計、さらにはコンピュータプログラムのアルゴリズムなど、現実世界でも多くの領域で応用されている分野です。
【ケーニヒスベルクの橋】についてオイラーは「出来ない事を証明」したわけですが、数学の世界ではこの「出来ない事を証明する」ってとても難しい事なんですね～。
５次以上の方程式には、解の公式が存在しない
という事を示した悲運の天才数学者ガロアやアーベルの話もいつかしたいと思います。
それでは今日はこの辺で。
【問題の解答】
みなさん、答は解っていると思いますが答合わせをしておきます。
この図形、各頂点の次数を調べると
次数が奇数となる頂点が４つあるのがわかりますね。
てなわけでこの図は……
一筆書きできない！
が正解でした。
