« 初めての大型連休 | メイン | ８月に振り替えるほうが、、、 »
2006年04月29日
4色問題
地図の領域を色分けするのに必要な色数が「４色でいい」ことは昔から経験的に知られていたが、証明にはけっこう日時がかかった。 しかも、その証明（たしか1980年代だったかな）はコンピュータを使うものでエレガントでなかったため、より簡潔な証明を試みる人も居たけれど、最近はあまり聞かれない。 もっとも、その手の会合にトントご無沙汰してもいるが、、、
昔、その手の会合に出ていたころ、Ｎ先生（当時東大教養学部）が「日本地図の県別色分けは、、、」という話をしてられたような記憶はある。
ヒョンなことから、県別色分けをやってみた。 「もしかしたら３色ではできないか？」という妙な期待（？）もあったが、それは無理なことはすぐわかった。 そこで、できるだけ３色でやって「４色目の色を使う県を最小にする」という試みに変えたところ、「ただ１県のみ４色目が必要」という答えが得られた。 A4版の地図を使ったので、隣接数最大の長野県が埼玉県とは点では接触しているように見えるが、接触していない、という前提である。
アルゴリズムはグリーディーで、ていねいにやっても（人手で）３分以内で終了するだろう。
領域を「ノード」に隣接関係を「辺」で表現したグラフにおいて、「直並列グラフなら３色」でいい。 昔から、証明は「組合せ数学の本」の練習問題であるが、これは現実的な条件ではない。 中国５県でも、広島県は鳥取県とも接しているため、直並列グラフではなくなってしまうが、３色で色分けできる。 つまり、直並列でなくても「３色で色分け可能という地図のクラス」が存在する。 このクラスの特徴をエレガントに表現するという問題は、未解決だろうと思う。
「なんでこんな話を持ち出したか？」というと一つは大学生向け、来年から「離散数学」を担当するため。 もう一つは小学生向け。 地域貢献（？）のために、こういうボランティアもしないといけないのです。 私が直接やるかどうかは別にして、ネタづくりをしておく必要があるので、この連休の課題の１つになりました。
「はなわのIQ都道府県」でも参考にしようかな、、、、
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
「３色問題」という本が、４色問題の証明ができる以前に出版されていた。 もちろん、海外のもので、ハードカバーだけれど論文集だったような気がする。 つまり、そのくらい様々な見方ができるわけで、スッキリ簡潔に記述できるものではない。 「未解決」というのはそういう意味で、「我が表現」というのはまだまだ可能と思う。
この本は広大西図書館に返却したが、オリジナルの仕事をするには、こんなものは見なくていい。 自分でやってみたあと必要なら見ればいい。
投稿者 tadashi : 2006年04月29日 03:04