情報考学　Passion For The Future

四色問題

・四色問題

四色問題

「四色あれば、どんな地図でも隣り合う国々が違う色になるように、塗り分けられることができるのか。」

証明がなくても経験的に、どんな地図でも四色で塗り分けられることはわかっていた。しかし、いざ証明しようとすると、「どんな地図でも」が問題になる。地図のパターンは無限に見えるからだ。証明に至るには150年の歳月がかかった。膨大な計算が必要であり、現代のコンピュータの力を借りる必要があった。

最終証明は100ページの概要と100ページの詳説、700ページの予備的成果、印刷すると高さ1.2メートルに及ぶ1万点の図。その計算をするためのコンピュータの稼働時間は1000時間に及んだ。

四色問題を解くには、塗り分けに五色以上を必要とする地図を仮定し（ないのだが）、そこに描かれている国の数が最も小さいケース＝最小反例が存在できないことを証明しなければならない。

この本の本論を読む前に、30分ほどペンと紙を持って考えてみるとよい。私もものすごく考えてみた。まず国の数が４以下では当然四色で塗り分けられるから、国の数は５以上が問題になる。国同士が隣接する方法に有限のパターンがあるはずと直観する。しかし、国の数が増えると、考えられる隣接の組み合わせ量が爆発して直観では、すべて塗りわけられると言い切れなくなっていく。

中心になる国を考え、周囲を異なる二色の国の鎖でつないでいくと、その内部は少なくとも塗りわけられると考えていいのではないか、と思いつく。この本にも鎖のアイデアが実際にでてたので、いい思いつきだったのだと嬉しくなった。国の数は無限に増やせる以上、対象を単純化しなければ、この問題は解けそうにないと思ったところで自力検証はギブアップ。

150年間の数学者たちの試行錯誤が語られている。無限と戦うにはまず単純化である。図形としての要素は、国の数、境界線の数、交点というパラメータに還元できることが示される。実は簡単な図形操作で判明するのだが、四色塗りわけを証明するには、すべての交点で３つの国と交わる地図（三枝地図）だけを考えればよいことが最初にわかる。幾何学の公式が使える問題になってきた。

読み進めていくと、以下のような概念が証明に密接に関わっていることを知る。

・可約配置
　「最小反例には含まれないような国々の配置。これを除いた残りの地図が四色で塗り分けられるなら、必要に応じて塗り直しをすることで、四色の塗わけを地図全体に拡張できる部分。」

・不可避集合
　「その中の少なくとも一つがすべての地図に現れるような配置の集合。」

・放電法
　「ある配置の集合が不可避集合であることを証明する方法。k本の辺を持つ国に6-kの「電荷」を割り当て、総電荷が変わらないように地図中で電荷を移動させる。」

無数にありえる地図のつながり具合を、四色問題の証明に必要な要素だけに単純化し、複雑な国や境界線の隣接方法を抽象化し、塗りわけの可否を検証するための数学的道具を用意したわけだ。異なるように見えても、数学的操作で、実質的に同じ構造の地図であることがわかれば可能性の数が減る。それでも、最小反例の候補群は複雑なものばかり数千件もあるのだが、これらをコンピュータを使って検証にかけた。四色で塗り分けられないものがないことがわかった。QED。

フェルマーの最終定理とはちがって、とてもエレガントとは言いがたい証明方法である。この証明はコンピュータの手を借りなければ証明することができなかった。数名の審査員が一応、機械計算にミスがなかったか、出力をチェックしたようだが、誰か人間が頭で検算できたわけでもない。150年間をかけた四色問題の証明は、数学界にそれまでになかった問題を提起する結果になってしまった。

人間が全部考えることができなくても証明したことになるのか？。

この手の数学問題が好きな人にはおすすめの本である。なぜか訳者はクオリア論で有名な脳科学者で哲学者の茂木健一郎氏。

・フェルマーの最終定理―ピュタゴラスに始まり、ワイルズが証明するまで
http://www.ringolab.com/note/daiya/archives/004192.html

・暗号解読―ロゼッタストーンから量子暗号まで
http://www.ringolab.com/note/daiya/archives/004028.html

・ヴォイニッチ写本の謎
http://www.ringolab.com/note/daiya/archives/004123.html

Posted by daiya at 2006年02月02日 23:59 | TrackBack