« I 'm sorry | メイン | Incredible ! »
2010年06月24日
簡単に「出来る」のに証明が難しいこともある
地図の領域を（隣と同じ色にならないように）塗り分けるには、「４色」あればできる。 昔から「出来ない例はない」というのは周知だったが、証明はできていなかった。 Appel & Haken(1976) は、コンピュータを使って「どんな地図でも塗り分けられること」を示した。
プログラムの完全性には疑義もあるが、一応「証明できた」というのが定説である。 しかし、数学の証明としては、全然エレガントではない。 もっとエレガントな証明が出来るなら、それは評価されるはずだけど、そういう挑戦は最近流行らないみたいである。
地図の色分けアルゴリズムは「グリーディ」で十分なので、昔から「できるなら、証明はどうでもいい」という人も居る。 それで「色分けられた地図」が作成できるから。
＊＊＊＊＊＊＊＊＊＊
グラフ理論的にいうと、３色で色分けできる特別な地図もある。 これは「直並列グラフ」というやつで、すべてネストした構造である。 この証明は、演習問題レベルなので、時折学生さんにやってもらったこともある。
ところが、ブリッジ構造になると「４色」必要になる。 こんな簡単なグラフなのに、と思うが、これがブリッジのいいところ。 1970年代はこの手の論文が花盛りだった。 （じつは、いくつか論文も書いたことがある。）
投稿者 tadashi : 2010年06月24日 14:47