地図の塗り分け必勝法って？ 四色定理

質問

一人で攻略するパズルを考えます。
迷路、一筆書き、あみだくじ（目的の並べ方になるように横線を引く。隣接互換でソートする。など。）、ルービックキューブなどには、必ず解ける方法というのが知られています。
ただしそれらは、最短手順もしくは最良とは限らなかったりします。

ところで、地図の塗り分けを一人で攻略するパズルと考えます。
地図があり、一人で色を上手に塗り分けていくのです。

http://ja.wikipedia.org/wiki/四色定理

によると、四色定理の証明はされているが他人による立証は困難。
しかし、ケンプの証明で使われた論理に沿って、地図を塗り分けるには5色で十分であることが証明された。

５色（もしくはそれ以上）で塗り分ける方法でもいいので、一人で攻略するパズルと考えたときの、必勝法といったものはあるのでしょうか？

一般に、解法には、たんなる存在証明と、具体的な解を導く方法（アルゴリズム）に大別されると思います。
たとえば、n次方程式にはn個の解が存在するという証明と、n個の解をニュートン法などの近似値計算で求める方法とがあると思います。

今回は、地図の塗り分けに関して、その後者の方法（アルゴリズム）を教えていただけたらと思います。

回答No.1

Tacosan · ベストアンサー

ソリティアの「必勝法」ってなんだろ....
さておき, 「5色で塗れる」という証明は構成的なので, この証明に従えばできるはずです. 5点からなる部分グラフを塗っておいて, 1点ずつ追加するんだったかなぁ?
「4色で塗れる」も構成的だったような気はしますが, 証明をチェックしていないので不明.

お礼

ありがとうございました