四色定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
4色に塗り分けられている(常にさらに外側の領域を想定することで、地図の外縁部は3色で塗り分け可能で、球面においても四色定理が成立することがわかる)

四色定理(よんしょくていり/ししょくていり、: Four color theorem)とは、厳密ではないが日常的な直感で説明すると「平面上のいかなる地図も、隣接する領域が異なる色になるように塗り分けるには4色あれば十分だ」という定理である。

概説[編集]

これを「地図の塗り分け」とすると、例えば飛び地を所属地と常に同じ色にしなければならない、とした場合、何色あっても足りない、といった問題などがあるので、まず、日常的な直感から離れた表現で記述し直すと「境界線によって囲まれたいくつかの領域からなる平面図形があり、境界線の一部を共有する(隣り合った)領域は異なった色で塗らなければならない、としたとき、4色あれば十分である」となる。

グラフ理論でとらえると、

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

ということになる。

なお、境界線ではなく、点のみを共有する領域は隣り合っているものとはみなされず、互いに同色で塗ってもよい(飛び地と同様に、これもやはり何色あっても足りなくなる。現実の地図では稀だが、有名なものでは米国に、1点に4州が接する「フォー・コーナーズ」という地点がある)。また平面だけでなく、球面の場合も同様である(平面の地図に、全周囲となる領域を加え、それを反対側の1点に集めるようにして球にすればよい。逆も同様)。しかし、ドーナツや「繋がったドーナツ」のような、穴がある形状の表面については同様とはいかない(後述)。

証明される前は四色問題と呼ばれることもあり、1975年に証明されたのだが、未証明の期間が長かったため現在でも四色問題と呼ばれることがある。

3つの境界線が1点に集まっている場所があるため、3色必要であることはただちに明らかである。続いて、ある領域の周囲にいくつかの領域がある場合(日本地図では長野県のような場合)を考える。周囲の領域の個数が偶数であれば3色で塗り分けできるが(長野県の場合はそうなる[1])、奇数個の領域で囲まれている場合は3色での塗り分けは不可能で、どうしても4色が必要である。そして、4色あればどんな場合でも塗り分けかのうなのか? ということが問題である。

グラフでは、問題を双対グラフに置き換えると、頂点の彩色となる。

Four Colour Planar Graph.svg

また、このような領域の塗り分けが有限の色数で必ず可能となるのは平面(二次元)以下の次元までであり、三次元以上では領域の取り方次第でいくらでも色数が必要な例が作れる。

歴史[編集]

(海や他国領土の色を除いて)4色に塗り分けられたアメリカ合衆国の州

1852年に法科学生のフランシス・ガスリーが数学専攻である弟のフレデリック・ガスリーに質問したのを発端に問題として定式化され、19世紀後半になって数学者がその話を聞いて証明を試みたが、多くの数学者の挑戦をはねのけ続けていた。

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

1976年ケネス・アッペル (Kenneth Appel) とヴォルフガング・ハーケン (Wolfgang Haken) は、ヘーシュ(Heinrich Heesch)により考案された「放電」と呼ばれる手続きを改良し、コンピュータを利用して約2000個の(後に1400個あまりに整理された)可約な配置からなる不可避集合を見出し、四色定理を「証明」するに至った[2][3][4]

これは一応は認められたが、人手による実行が(事実上)不可能なほどの複雑なプログラムの実行によるものであることから、ハードウェアやソフトウェア(コンピュータやそのプログラム)のバグの可能性などの懸念から、その確実さについて疑問視する向きもあった。

しかしその後、1996年にニール・ロバートソン (Neil Robertson) らによりアルゴリズムやプログラムの改良が行われ、より簡易な手法(従来の放電手続きよりシンプルな放電手続きを考案し、不可避集合の数を1405個から633個に抑えた)による再証明が行われる[5]など、第三者による複数の改良された証明が行われ、証明は確実視されるようになっていった。2004年にはジョルジュ・ゴンティエ (Georges Gonthier) が定理証明系Coqを用いて、よりシンプルな証明を行うなど[6]、コンピュータの応用手法の洗練により、より確かな手続きで証明が行われるなどしているため、現在では四色問題は解決していると捉えられている。

証明[編集]

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

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

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

アッペルとハーケンはコンピュータによる実験を繰り返し、プログラムを何度も書き換えながら、可約なグラフから成る約2,000個のグラフからなる不可避集合を求めた。当時の大型汎用コンピュータであるIBM System/370[7]を1,200時間以上使用したといわれている。

複雑に思える問題に対して簡潔にまとまった比較的短い証明(解答)を、エレガントな証明(解答)と言うことがある。四色定理のある種「力業な証明」は、これと対極にあるものとして揶揄を込めて「エレファント()」な証明とも言われた。5色による塗り分けが可能であることの証明が簡潔なものであるのと対照的である。

その後アルゴリズムは改良されたが、現在でもコンピュータを使用しない証明は得られていない。それどころか完全に自然言語を離れて、プログラムにバグがないことも含めた四色定理の証明全体をコンピュータに打ち込んで証明検査器Coqにチェックさせた仕事がある。またコンピュータを使うこと以上に、証明の構成法自体が四色定理の解決に特化されており、他の問題との関係性に乏しいことも数学者の間で人気がない理由となっている。

一般化[編集]

一般に種数 g ≥ 0 の閉曲面(わかりやすく言えば、穴が g 個あるドーナッツ)を塗り分けるのに最低限必要な色の数は、1890年にヒーウッドによって

([]はガウス記号

と予想された。g ≥ 1 に対してこの予測が正しいことは、リンゲルとヤングスにより1968年に証明された[8]

トーラス(円環、いわゆるドーナッツの形)上のグラフは、7色で彩色可能である。 Torus with seven colours.svg Projection color torus.png

3彩色問題[編集]

「与えられた地図Gに対し、Gを3色で塗り分けできるかどうかを決定せよ」という問題を3彩色問題という。四色問題のときと同じく隣り合う土地を同じ色で塗ってはならない。

3彩色問題はNP完全問題の一つであることが知られている。

四色問題とジョーク[編集]

まだ四色問題が未解決だった1975年4月、一つのハプニングが起こった。パズル作家のマーティン・ガードナーが『Scientific American』の「Mathematical Games」欄に、四色問題の反例が見付かった、という記事を載せた[9][10][11]のである。

「なぜか世間の注意をひかなかった6つの衝撃の発見」と題するこの記事は、ガードナーがエイプリルフールの冗談として載せたもので、他にはラマヌジャンの定数(ほとんど整数#ラマヌジャンの定数を参照)などでも知られているエイプリルフールジョークである。四色問題の反例として載っていた図は、実はマクレガーによる数学パズルen:Recreational mathematics)問題である。この問題は一見して四色での塗り分けが不可能に見えるが実際に塗り分けを試みると意外に簡単にできるため、塗り分けできたぞというメールが千通以上も寄せられることになった[11]

脚注[編集]

[ヘルプ]
  1. ^ 新潟県・群馬県・埼玉県・山梨県・静岡県・愛知県・岐阜県・富山県 の8県
  2. ^ K. Appel, W. Haken, "Every planar map is four colorable 1" (Bulletin of the American Mathematical Society Volume 82, Number 5, September 1976)
  3. ^ "Every planar map is four colorable. Part II: Reducibility" by K. Appel, W. Haken, and J. Koch (Illinois J. Math. Volume 21, Issue 3 (1977), 491–567.)
  4. ^ Contemporary mathematics 98 "Every Planar Map is Four Colorable" by Kenneth Appel and Wolfgang Haken
  5. ^ "A new proof of the four-colour theorem" by Neil Robertson, Damiel P. Sanders, Paul Seymour, and Robin Thomas (Electronic Research Announcements of the American Mathematical Society Volume 2, Number 1, August 1996)
  6. ^ "A computer-checked proof of the Four Colour Theorem" by Georges Gonthier (Microsoft Research Cambridge)
  7. ^ 「最高速のスーパコンピュータ」などと書かれていることもあるが、同機はいわゆる(クレイなどの)「スーパコンピュータ」ではない。1975年当時のIBMの主力機でコンピュータ全体から見ればハイエンドのレンジには相当するが、いわゆるシリーズ構成をとっていたため同じ「System/370」でもモデルによって性能には幅がある。
  8. ^ Weisstein, Eric W. "Map Coloring". MathWorld(英語). 
  9. ^ ガードナー & 一松 (1977)
  10. ^ 高木 (1976, XIV 最近の話題/パズルの最前線)によると、日本版『サイエンス』誌6月号に掲載、と見える。
  11. ^ a b 一松 (1978, pp. 197–204)

参考文献[編集]

関連項目[編集]

外部リンク[編集]