四色定理
四色定理（よんしょくていり/ししょくていり）とは、いかなる地図も、隣接する領域が異なる色になるように塗るには4色あれば十分だという定理である。
概説
この定理はグラフ理論において
- 平面グラフは4彩色可能である
ということと同値である。
ただし飛び地は本国と同じ色でなくてもよいものとする（飛び地を本国と常に同じ色にしなければならない場合、理論上何色あっても足りない）。
解決前は四色問題と呼ばれており、未解決の期間が長かったため現在でも四色問題と呼ばれることがある。
4つの領域が互いに接しているような地図が存在するので、3色では不可能である。この問題は球面上のグラフで考えても同値である。（右参考図：外周の緑色領域の上下左右を閉じた閉曲面でも成立する）
問題を双対グラフに置き換えることによって、頂点を彩色することに帰着される。
四色定理の示すように領域の塗り分けが有限の色数で必ず可能となるのは平面（二次元）以下の次元までであり、三次元以上では領域の取り方次第でいくらでも色数が必要となってしまうようになる。
歴史
地図を製作する際には国境線を接する国を別の色で塗らなくてはならないので、地図制作業者の間では数百年前から経験的に知られていたテンプレート:要出典。1852年に法科学生のフランシス・ガスリーが数学専攻である弟のフレデリック・ガスリーに質問したのを発端に問題として定式化され、19世紀後半になって数学者がその話を聞いて証明を試みたが、多くの数学者の挑戦をはねのけ続けていた。
1879年、アルフレッド・ブレイ・ケンプによる証明が『アメリカ数学ジャーナル』誌上で発表された。この証明は妥当と見なされていたが、1890年になってパーシー・ヒーウッドにより不備が指摘された。しかし、ケンプの証明で使われた論理に沿って、地図を塗り分けるには5色で十分であることが証明された。そして、この問題は、グラフ理論における最も有名な未解決問題となった。
1976年にケネス・アッペル (Kenneth Appel) とヴォルフガング・ハーケン (Wolfgang Haken) は、「放電」と呼ばれる手続きを考案し、1405個の不可避集合に対してコンピュータを利用した演算を行った結果、四色定理を証明するに至った[1][2][3]。当初は、あまりに複雑なプログラムのため他人による検証が困難であることや、ハードウェアおよびプログラムのバグの可能性を考慮して、この証明を疑問視する声があった。その後、1996年にニール・ロバートソン (Neil Robertson) らによりアルゴリズムやプログラムの改良が行われ、より簡易な手法（従来の放電手続きよりシンプルな放電手続きを考案し、不可避集合の数を1405個から633個に抑えた）による再証明が行われた[4]。更に、2004年にはジョルジュ・ゴンティエ (Georges Gonthier) が定理証明支援系言語であるCoqを用いて、よりシンプルな証明を行った[5]。その結果、現在では四色問題の解決を否定する専門家はいなくなっている。
四色定理は実用的には地図作製だけでなく、携帯電話の基地局配置にも応用されている。周波数の同じ電波同士で混信してしまうFDMA・TDMA方式の携帯電話システムでは、隣接する基地局同士に同じ周波数を割り当てないように、配慮している。
証明
四色定理の証明法は次の2段階に分けられる。
- どんな平面グラフをとってきても、その集合に属するグラフのどれか一つがサブグラフとして含まれるグラフの集合を考える。このような性質をもつグラフの集合を不可避集合という。
- うまい不可避集合をとると、それに属するどのグラフも次の意味で可約にできる。すなわち、そのサブグラフを含むグラフがあったとき、そのサブグラフを除いたものが4色塗り分け可能なら、グラフ全体も4色塗り分けできる。
実際、もし四色問題の反例となる、塗り分けに5色以上必要なグラフがあったとしたなら、その中でノードの個数が最小のものを考える。すると、1.よりこのグラフは不可避集合に属するサブグラフを含む。2.により、このサブグラフを除いた、より小さなグラフが既に四色問題の反例を与える。しかし、それは最小反例をとってきたという仮定に反する。
アッペルとハーケンはコンピュータによる実験を繰り返し、プログラムを何度も書き換えながら、可約なグラフから成る約2,000個のグラフからなる不可避集合を求めた。当時の最高速のスーパーコンピュータを1,200時間以上使用したといわれている。
複雑に思える問題に対して斬新な観点から見るなどして得られた比較的短い証明（解答）を、エレガントな証明（解答）と言うことがある。四色定理の証明は、これと対極にあるものとして若干揶揄を込めて「エレファント（象）」な証明とも言われた。5色による塗り分けが可能であることの証明が簡潔なものであるのと対照的である。
その後アルゴリズムは改良されたが、現在でもコンピュータを使用しない証明は得られていない。それどころか完全に自然言語を離れて、プログラムにバグがないことも含めた四色定理の証明全体をコンピュータに打ち込んで証明検査器Coqにチェックさせた仕事がある。またコンピュータを使うこと以上に、証明の構成法自体が四色定理の解決に特化されており、他の問題との関係性に乏しいことも数学者の間で人気がない理由となっている。
一般化
一般に種数 g ≥ 0 の閉曲面（わかりやすく言えば、穴が g 個あるドーナッツ）を塗り分けるのに最低限必要な色の数は、1890年にヒーウッドによって
- <math>\left[ \frac{7+\sqrt{1+ 48g}}{2} \right]</math>（［］はガウス記号）
と予想された。g ≥ 1 に対してこの予測が正しいことは、リンゲルとヤングスにより1968年に証明された[6]。
トーラス（円環、いわゆるドーナッツの形）上のグラフは、7色で彩色可能である。 300px 400px
3彩色問題
「与えられた地図Gに対し、Gを3色で塗り分けできるかどうかを決定せよ」という問題を3彩色問題という。四色問題のときと同じく、隣り合う土地を同じ色で塗ってはならない。
3彩色問題はNP完全問題の一つであることが知られている。
四色問題とジョーク
まだ四色問題が未解決だった1975年4月、一つのハプニングが起こった。パズル作家のマーチン・ガードナーが『Scientific American』の「Mathematical Games」欄に、四色問題の反例が見付かった、という記事を載せた[7]のである。
「なぜか世間の注意をひかなかった6つの衝撃の発見」と題するこの記事は、ガードナーがエイプリルフールの冗談として載せたもので、反例として載っていた図は実はマクレガーがパズルの問題として載せたものだったのだが、この記事に騙された読者が続出して大騒ぎになった。
関連項目
参考資料
脚注
- ↑ K. APPEL , W. HAKEN "EVERY PLANAR MAP IS FOUR COLORABLE 1" (BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY Volume 82, Number 5, September 1976)
- ↑ "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.)
- ↑ CONTEMPORARY MATHEMATICS 98 "Every Planar Map is Four Colorable" by Kenneth Appel and Wolfgang Haken
- ↑ "A NEW PROOF OF THE FOUR-COLOUR THEOREM" by NEIL ROBERTSON, DANIEL P. SANDERS, PAUL SEYMOUR, AND ROBIN THOMAS (ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 2, Number 1, August 1996)
- ↑ "A computer-checked proof of the Four Colour Theorem" by Georges Gonthier (Microsoft Research Cambridge)
- ↑ テンプレート:MathWorld
- ↑ テンプレート:Cite bookこれによると、日本版『サイエンス』誌6月号に掲載、と見える。
外部リンク
- 改良されたアルゴリズム（英語サイト）
- Four-Color Theorem -- From MathWorld（四色定理）（英語）
- Map Coloring -- From MathWorld（地図の塗り分け）（英語）
- Torus Coloring -- From MathWorld（トーラスの塗り分け）（英語）
