四色定理を解説
1852年、イングランドの州の地図を塗り分けていた若い数学者は、隣り合う州を区別するには4色で足りるらしいことに気づきました。それはありとあらゆる地図について正しいのでしょうか。この問いは数学で最も有名な問題の一つとなり、11年間も正しいと信じられた有名な誤った証明を生み、1976年についに解決されました。その解決の仕方は、数学者が何を証明として認めるかを変えました。
問い
オーガスタス・ド・モルガンの教え子だったフランシス・ガスリーは、境界を共有する国どうしが異なる色になるように、どんな地図でも4色で塗り分けられるかと問いかけました。この問いを厳密にするルールが2つあります。国は連結していて、それぞれが1つのまとまりでなければなりません。また、1点でだけ接する国どうしは隣国とはみなしません。3色では必ずしも足りないことは明らかです。互いに接し合う3つの国が輪になって取り囲む国には、4色目が必要だからです。問題は、5色目が必要になることがあるかどうかです。
グラフとしての地図
各国に1つ点を打ち、2つの国が境界を共有するたびにその2点の間に線を引きます。その結果がグラフです。地図は平らな紙の上にあるので、線は交差させずに引くことができます。つまり、このグラフは平面グラフです。地図を塗り分けることは、すべての辺の両端が異なる色になるようにこのグラフの頂点を塗ることです。それが可能な最小の色数を彩色数といい、四色定理は、彩色数が4を超える平面グラフは存在しないことを述べています。
失敗したケンプの証明
1879年、法廷弁護士で数学者のアルフレッド・ケンプが証明を発表しました。その巧妙なアイデアは現在ケンプ鎖と呼ばれ、つながった国の鎖に沿って2つの色を入れ替え、必要な場所で1色を空けるというものです。この証明は11年間受け入れられていましたが、1890年にパーシー・ヒーウッドが穴を見つけました。ヒーウッドによる修正で証明できたのは、5色あれば必ず足りるという弱い結果でした。ケンプ鎖は生き残り、最終的な証明の道具となりました。
5色が簡単な理由
すべての平面グラフには、隣接する頂点が5つ以下の頂点があります。これはオイラーの公式から導かれ、この公式により n 個の頂点を持つ平面グラフの辺は多くても 3n − 6 本に限られます。そのような頂点を取り除き、同じ議論で地図の残りを塗り、頂点を元に戻します。隣接する頂点が使っている色が5色未満なら、1色が空いています。5色すべてを使っていても、ケンプ鎖の入れ替えで必ず1色を空けられます。4色の場合は同じ入れ替えがうまくいかないことがあり、それこそがケンプの見落とした穴でした。
コンピューターによる証明
1976年、イリノイ大学のケネス・アッペルとヴォルフガング・ハーケンがこの定理を証明しました。彼らは、どの地図にも不可避集合に属する1936個の配置のうち少なくとも1つが含まれること、そして各配置が可約であること、つまり5色を必要とする最小の地図はそれを含みえないことを示しました。可約性の確認にはコンピューターで1000時間以上かかり、手で検証するにはあまりに膨大でした。誰も全体を読み通せない証明に多くの数学者が不安を覚え、コンピューター支援証明をめぐる議論が始まりました。
よりシンプルな証明と完全な検証
1996年、ニール・ロバートソン、ダニエル・サンダース、ポール・シーモア、ロビン・トーマスは、633個の配置を用いたより体系的な証明を発表しました。これもコンピューターで確認されますが、検証はより容易です。2005年にはジョルジュ・ゴンティエとバンジャマン・ヴェルネが証明支援系 Coq で証明全体を形式化し、小さく信頼できるプログラムがすべての論理的ステップを確認するようにしました。今日、四色定理は数学で最も徹底的に検証された結果の一つです。
彩色アルゴリズム
与えられた地図の4色塗り分けを見つけるのは実際には速くできますが、一般のグラフについて最少の色数を求めるのは難しく、3色で足りるかどうかの判定はNP完全です。実用的な方法には、次数の大きい順に塗る貪欲法、最も制約の多い頂点を次に塗る DSATUR、そして選択を探索し行き詰まると取り消すバックトラック探索があります。グラフ彩色は、重なりのない試験日程の作成、隣接する送信所が干渉しないような無線周波数の割り当て、コンパイラーでのレジスタ割り当てに使われています。
試してみよう
四色定理 地図塗り分けツールを開くと、4~120か国の地図を作り、4色で手で塗って、衝突が赤く表示される様子を見られます。貪欲法、DSATUR、バックトラックに地図を一手ずつ解かせ、隣り合う国のグラフを表示し、その地図に本当に必要な最少の色数を確かめましょう。
よくある質問
この定理は地図製作者の役に立ちますか?
ほとんど立ちません。実際の地図はわかりやすさのために普通はもっと多くの色で塗られ、海や湖、いくつかの部分に分かれた国も含まれますが、それらは定理の対象外です。この定理の重要性は数学的なものです。グラフ理論の発展を促し、何が証明とみなされるのかという問いを投げかけました。
ケンプ鎖とは何ですか?
2つの色、たとえば赤と青を選び、赤く塗られた国を1つ取ります。そのケンプ鎖とは、赤と青の隣国だけを通ってその国からたどり着けるすべての赤と青の国の集まりです。鎖全体で赤と青を入れ替えても塗り分けは正しいままで、鎖に隣接する国のために1色を空けられることがあります。
いくつかの部分に分かれた国があると、なぜ定理が成り立たないのですか?
国が離れた複数の領域からなり、それらをすべて同じ色にしなければならないとすると、隣接グラフはもはや平面的ではなくなり、より多くの色が必要な地図を作れます。1国あたり2つの部分の場合は、12色までの任意の色数が必要な地図を作れることを、ヒーウッドが「帝国問題」で研究しました。
このツールはなぜ点から地図を作るのですか?
各国は、正方形のうち、あるランダムな点にほかのどの点よりも近い領域で、これをボロノイ図といいます。こうすると凸な国からなる本物らしい地図ができ、2つの国が隣り合うのは、ちょうど両者の領域が境界の一部を共有するときで、アプリはそれを正確に計算します。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
四色定理 地図塗り分けツールを開く