-----------------------------------------------------------------------------
どんな地図でも、4色あれば、隣接する領域の色が
異なるように塗り分けることができる。
-----------------------------------------------------------------------------


というのを、四色定理と言います。


この定理の主張自体は、古くから地図製作業者の間で経験的に知られていたそうです。

ところが証明しようとするとなかなかうまく行かず、この主張は長い間、四色問題と呼ばれる未解決問題でした。


3色では足りないということは、簡単にわかります。

たとえば以下の図を見てください。

yonshoku1














これはアフリカ大陸にあるサンビア共和国タンザニア連合共和国モザンビーク共和国マラウイ共和国の位置関係を簡略化して描いたものです。

いま、サンビア共和国で塗り、サンビア共和国に隣接するタンザニア共和国で塗るとします。すると以下のようになります。

yonshoku2














すると、モザンビーク共和国には、の色は使えません。なぜならモザンビーク共和国サンビア共和国ともタンザニア連合共和国とも隣接しているからです。よってモザンビーク共和国は、黄色で塗ることにしましょう。すると以下の図のようになります。

yonshoku3














すると、マラウイ共和国は、でもでも黄色でも塗れないことがわかります。なぜならどの色の国とも接しているからです。

よって、マラウイ共和国には、黄色以外の色を割り当てねばなりません。


以上の例から、3色では塗りわけ不可能な地図は存在します



19世紀終わりになって、塗りわけるためには5色あれば十分だということが証明されました。

そして1976年ハーケンアッペルが、コンピュータ技術を駆使して、4色で十分だという証明を完成させました

「どんな地図でも」十分だというのを証明したのは素晴らしいですね。疑う方は思いつく限りの地図を描いて検証してみてください。

長らく未解決だった問題がコンピュータによって解決される、というのは、数学の新たな可能性を感じさせます。



ところでふと思ったのですが、三次元の地図は何色あれば塗り分けられるんでしょうか?現在三次元地図の研究が進められているようなので、こういう問題がそのうち生じてくると思うのですが。

もしかしたら一般の次元の場合も解明されたりしちゃってるのでしょうか?私も考えてみようと思いますが、詳しい方は教えていただければ嬉しいです。



よろしければワンクリックお願いします^^↓

人気ブログランキング