四色定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』

四色に塗り分けられている

四色定理（ししょくていりまたはよんしょくていり）とは、いかなる地図も、隣接する領域が異なる色になるように塗るには4色あれば十分だという定理である。但し飛び地のような領域は考えない。実際の行政区分で飛び地があったとしても飛び地とその飛び地の所属する本国は関連せず、別の色であってもよいとする。解決前は四色問題と呼ばれており、未解決の期間が長かったため現在でも四色問題と呼ばれることがある。

これは、グラフ理論において

平面グラフは4彩色可能である

ということと同値である。

四つの領域が互いに接しているような地図が存在するので、3色では不可能である。この問題は球面上のグラフで考えても同値である。問題を双対グラフに置き換えることによって、頂点を彩色することに帰着される。

読み方は、「ししょく」、「よんしょく」のどちらかが正しいというのはない。

[編集] 歴史

色分けした世界地図。海と南極を含めて6色で塗り分けられている。

地図を製作する際には国境線を接する国は別の色で塗らなくてはならないので、地図制作業者の間では何百年も昔から経験的に知られていた。1852年に法科学生のフランシス・ガスリーが数学専攻である弟のフレデリック・ガスリーに質問したのを発端に問題として定式化され、19世紀後半になって数学者がその話を聞いて証明を試みたが、簡単そうに見える割に難しく、多くの数学者の挑戦をはねのけ続けていた。

1879年、アルフレッド・ブレイ・ケンプによる証明が『アメリカ数学ジャーナル』誌上で発表された。この証明は妥当と見なされていたが、1890年になってパーシー・ヘイウッドにより不備が指摘された。しかし、ケンプの証明で使われた論理に沿って、地図を塗り分けるには5色で十分であることが証明された。

そして、この問題は、グラフ理論における最も有名な未解決問題となったのであるが、1976年にケネス・アッペル (Kenneth Appel) とウルフガング・ハーケン (Wolfgang Haken) によってコンピュータを駆使して証明された。しかし、あまりに複雑なプログラムのため他人による検証が困難であることや、コンピュータの誤りの可能性を考慮して、この証明に疑問視する声があった。その後、プログラムの改良が進められており、現在、四色問題の解決を否定する専門家はいない。

四色定理は実用的には地図作製だけでなく、携帯電話の基地局配置にも応用されている。周波数の同じ電波同士で混信してしまうFDMA・TDMA方式の携帯電話システムでは、隣接する基地局同士に同じ周波数を割り当てないような塗り分けを必要とするのだ。

[編集] 証明

四色定理の証明法は次の2段階に分けられる

グラフの集合であり、どんな平面グラフをとってきてもその集合に属するグラフのどれか一つがサブグラフとして含まれるようなものをとってくる。このような性質をもつグラフの集合を不可避集合という。
うまい不可避集合をとると、それに属するどのグラフも次の意味で可約にできる。すなわち、そのサブグラフを含むグラフがあったとき、そのサブグラフを除いたものが4色塗り分け可能なら、グラフ全体も4色塗り分けできる。

実際、もし4色問題の反例となる、塗り分けに5色以上必要なグラフがあったとしたなら、その中でノードの個数が最小のものを考える。すると、1.よりこのグラフは不可避集合に属するサブグラフを含む。2.により、このサブグラフを除いた、より小さなグラフが既に4色問題の反例を与える。しかし、それは最小反例をとってきたという仮定に反する。

アッペルとハーケンはコンピュータによる実験を繰返し、プログラムを何度も書き換えながら、可約なグラフから成る約2000個のグラフからなる不可避集合を求めた。当時の最高速のスーパーコンピュータを1200時間以上使用したといわれている。

複雑に思える問題に対して斬新な観点から見るなどして得られた比較的短い証明（解答）を、エレガントな証明（解答）と言うことがある。四色定理の証明は、これと対極にあるものとして若干揶揄を込めて「エレファント（象）」な証明とも言われた。5色による塗り分けが可能であることの証明が簡潔なものであるのと対照的である。

その後アルゴリズムは改良されたが、現在でもコンピュータを使用しない証明は得られていない。

なお、ハーケンは四色問題以前にはポアンカレ予想に挑戦していた時期があり、ハーケン多様体という３次元トポロジーの用語に名をとどめている。

トーラス（円環、いわゆるドーナッツの形）上のグラフは、7色で彩色可能である。一般に種数 g≧0 の閉曲面（解かりやすく言えば、孔がg個あるドーナッツ）を塗り分けるのに最低限必要な色の数は、1890年にヒ－ウッドによって