電子書籍の厳選無料作品が豊富!

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

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

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

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

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

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

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

A 回答 (1件)

ソリティアの「必勝法」ってなんだろ....


さておき, 「5色で塗れる」という証明は構成的なので, この証明に従えばできるはずです. 5点からなる部分グラフを塗っておいて, 1点ずつ追加するんだったかなぁ?
「4色で塗れる」も構成的だったような気はしますが, 証明をチェックしていないので不明.
    • good
    • 0
この回答へのお礼

ありがとうございました

お礼日時:2008/01/18 00:29

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!