地図塗り分け問題(解答編)

平面地図において隣り合う領域は異なる色で塗り分けるようにした時に 少なくとも 何色が必要になるか?【問題の詳細についてはこちら】をご覧ください。



それでは解答です。ご覧になりたい方は下の方にスクロールしてください。






















どれだけ複雑な平面地図(日本地図、世界地図、その他意図的に作った難しい地図…)を用意しても 少なくとも「四色あれば」塗り分けられる が答えです。これは「四色定理」と呼ばれる数学の定理です。

四色定理の証明は物凄く難しいです。考えうる地図が何パターンに分類できるかをコンピュータを活用してリストアップし、それが1,000を超える事が判明しました。これらが四色で塗り分け可能である事を地道に示していき「どのような平面地図も、少なくとも四色あれば塗り分けられる」事を示したのです。

四色定理の証明は、数学史上で初めてコンピュータが活用された例とされています。この説明は私の手に余るので割愛しますが、これだけで終わってしまっては面白くないので「何となく」四色あれば良さそうな気がする…というところまでは理解していただけるように頑張ってみます。

まず、二つの領域が隣り合うようにしてみます。この状況ならば二色が必要になります。

二色で塗り分ける領域の例
(クリックすると、大きい画像を開きます)

三色目が必要になるように新しい領域を追加してみます。

三色目が必要になる領域を追加してみた
(クリックすると、大きい画像を開きます)

さらに外側に四色目が必要になるように新しい領域を追加してみます。

四色目が必要になる領域を追加してみた
(クリックすると、大きい画像を開きます)

このように「新しい領域を追加したら、新しい色が必要になる」…ように思えるのですが

新しく追加した領域は色追加不要でした
(クリックすると、大きい画像を開きます)

次に追加した領域は、三色目に追加した領域とは完全に離れているので三色目と同じ色で塗る事ができます。今回は水色が囲まれるような例ですが、黄色や紫色が囲まれるようにしたとしても同じ事が言える事を確かめてみてください。

このやり方だけでは「どんなやり方をしても、絶対に四色で塗り分けられる!」と主張するには弱いですが、新しい領域が別の領域とは完全に離れているので同じ色で塗る事ができるという考え方は重要です。

実際、少し条件を緩めて 少なくとも五色で塗り分けられると主張した「五色定理」は、この考え方を応用して証明できてしまう のです。コンピュータの助けを借りなくても大丈夫なのです。私も過去に証明のアウトラインを追った事があります。 今は追えるだけの力がなくなってそうです(涙)。 

あらゆる平面地図が四色で塗り分けられるという面白さの紹介と、五色ならば証明できるけれど四色に一色減らすのは大変という事を説明するのが今回の主眼でした。



追記。もう少し意地悪な例を作ってみました。

少し意地悪な例
(クリックすると、大きい画像を開きます)

しかし、このような場合も少し塗り分け方法を変えてやるとやっぱり四色で塗り分けられるのでした。
スポンサーサイト

テーマ : 今日のつぶやき。 - ジャンル : 日記

コメント
コメントの投稿
管理者にだけ表示を許可する