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

どうも最近は鉄道ブログのような記事しか書いておりませんでした(ん?)。【以前に記事にした「切り欠いたチェス盤にドミノを並べる問題」】を書いているうちに思い付いた問題です。

前回の問題とは分野が違うのですが(前回は「組み合わせ問題」、今回は「平面埋め込み問題」)、似たような問題は関連付けて考えたり覚えた方が知識が繋がって記憶に定着しやすいものです。珍しく真面目な発言です。

チェス盤にドミノを並べた状態を考えます。

ドミノを並べたチェス盤
(クリックすると、大きい画像を開きます)

この並べたドミノについて、隣り合うドミノ同士が同じ色にならないように塗り分ける事を考えます。

隣り合うドミノが同じ色にならないように塗り分けた例
(クリックすると、大きい画像を開きます)

適当に塗り分けてみましたが、黄色・ピンク・水色・紫色の四色で塗り分ける事ができました。

さて、ここで問題です。同じように日本の都道府県の白地図、アメリカ合衆国の州の白地図、世界地図…など、色々な平面地図を考えた時に、 少なくとも 何色があれば塗り分けられるでしょうか?今回の例は簡単でしたが、もっと複雑な地図ならば五色、六色、ヘタするともっと多数の色が必要かもしれません。

実はこの一見簡単に見える問題ですが、数学的証明はメチャクチャ難しい問題です。従ってエイヤで答えていただければと思います。

正解はこちら】。
スポンサーサイト

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

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