身近な問題を解決する

問題を発見する

国ごとに色分けされた地図や、市町村ごとに色分けされた地図を作るとき、いくつの色が必要か、白地図を色分けする時に考えたことはなかったろうか。

白地図

一般的なルールは隣り合う領域は違う色に塗るというだけ。(頂点が接する所は同じ色でもかまわない)

塗り分け地図

実際の地図によって必要な数は異なるし、塗りかたによっても必要な数は変わってくるのだが、数学者がこれを考えていく過程で「四色問題」として知られるようになった。

四色問題

「いかなる地図も、隣接する領域が異なる色になるように塗るには4色あれば十分である」ことが正しいか正しくないかが解明されていない。これが四色問題である。(ただし飛び地のような領域を考えない)

3色で済む地図もあるが、どうしても4色必要な図を作れるので、3色では不足であるとわかっている。

19世紀後半からこの問題は未解決の問題として知られていた

4色で十分なことを証明するか、5色必要な地図を考え出せばこの問題は解決する。特に5色必要な地図を考え出す方は数学者でなくてもわかりそうであることから有名になった。

外堀

平面上でなく球面でもおなじである(地球儀)

3次元以上では必要な色数は無数

5色あれば塗り分けられることは証明された。

ドーナツ型の立体の表面の地図を塗り分けるには7色必要なことが証明された。

しかし、「平面や球面は4色あれば十分」はなかなか解決できなかった。

問題の解決

1976年に ケネス・アッペル (Kenneth Appel) とヴォルフガング・ハーケン (Wolfgang Haken) がコンピュータを利用して、4色で十分なことを証明した。発表当初は他人による検証が難しく疑問視されたが、現在では、この証明は信用されている。

現在でもコンピュータを使用しない証明はない。

応用

携帯電話の基地局に応用される。隣り合う基地局で同じ周波数の電波をつかうと混信する。「異なる周波数の電波を使わなければならない」を「異なる色にする」と考えれば基地局の電波を決めるのに応用できる。

参考: フリー百科事典『ウィキペディア(Wikipedia)』

聖愛中学高等学校
http://www.seiai.ed.jp/
Jun. 2010