なにかの知識

なにかの知識

5分で学べる無駄知識

四色問題とは?わかりやすく5分で解説

四色問題とは、四色で隣り合う領域同士が同色にならずに地図を塗り分けることができるかという問題のこと

問題提起から120年以上たった1976年、コンピュータを用いてドイツの数学者ハーケンとアメリカの数学者アッペルによって証明された。四色定理ともいう。以降、便宜上領域を国と表記する。

f:id:gmaj7dmaj7gmaj7dmaj7:20190531214657j:plain

背景

1852年、インドの数学者ド・モルガンが学生から、四色あれば隣国同士が同色にならずに地図を塗り分けることができる理由を聞かれた。この四色問題を初めて聞いた彼は、答えを求めてイギリスの数学者ハミルトンに手紙を書いた。

これに対しハミルトンは大きな関心を示さなかったが、四色問題に魅了されたド・モルガンはその後も交友のある学者へ手紙を送り続けた。

四色問題のルール

四色問題には2つのルールがある。まず、互いが1点で接する場合は色を変える必要はない。たとえば、市松模様のように斜め方向が同色でもよい。次に、飛地の色を合わせる必要はない。たとえば、アメリカ本土とアラスカは別の色でもよい。

本格的な研究の開始

1878年、イギリスの数学者ケイリーが学会で四色問題に触れてから、本格的に研究が進むようになった。彼は、四色問題を解くには単純な三枝地図のみを扱えばよいことを示した。三枝地図とは、すべての交点が3つの領域で共有されている地図のこと。

たとえばピザを3等分した状態がこれにあたり、真ん中の交点が3つのピザで共有されている。この時、ピザの外周にも交点が3箇所できるが、それぞれ2つのピザと外の領域という3つの領域で交点が共有される。

オイラーの公式

18世紀、スイスの数学者オイラーが多面体の公式を発見した(オイラーの公式)。オイラーの公式とは、多面体において(面の数)-(辺の数)+(頂点の数)=2が成り立つというもの。たとえば立方体を公式に当てはめると、6-12+8=2となり成り立つことが分かる。

オイラーの公式は平面(地図)でも成り立ち、その際は(国の数)-(境界線の数)+(交点の数)=2となる。この公式からいかなる地図でも2つか、3つか、4つか、5つの隣国を持つ国を最低1つは含むことが導かれる。

五色問題の証明

1879年、イギリスのアマチュア数学者ケンプがアメリカ数学ジャーナル誌に四色問題の証明を発表した。この証明には彼が考案したケンプ鎖の論証が用いられた。ケンプ鎖とは2色が交互に並ぶ配置のことで、一定の条件を満たせば互いの色を入れ替えられる

たとえば、本記事トップ画像にある福岡→大分→宮崎→鹿児島は青→赤→青→赤のケンプ鎖だが、赤→青→赤→青に入れ替えても支障はない。彼はこの手続きによって、四色問題の証明を試みたが1890年、イギリスの数学講師ヘイウッドが証明の不備を指摘した。

ヘイウッドはケンプの証明を正せなかったが、代わりにケンプ鎖の論証で五色問題を証明した。

不可避集合と可約配置

四色問題が正しくない場合、五色以上の地図が存在することになる。この時、五色以上の地図のうち国の数が最小のものを最小反例という。20世紀、オイラーの公式、ケンプ鎖、最小反例等に不可避集合と可約配置という概念が加わり、証明の方針が固まった。

不可避集合とは、最低1つは地図に含む必要のある国々のパターンの集まりこと可約配置とは、必ず四色で塗り分けられる国々のパターンのこと。もし、すべての地図に可約配置が含まれるならば、最小反例にも可約配置が含まれることになる。

そこで最小反例から可約配置を除くと、国数が減り最小反例ではなくなるため四色で塗り分けられる。その地図に可約配置を戻しても、可約配置は四色で塗り分けられる。つまり、すべてが可約配置の不可避集合を見つければ、四色問題が証明される

コンピュータの導入

1967年、ドイツの数学者ハーケンが数学の難問ポアンカレ予想の証明を断念し、四色問題の研究に着手した。1969年、ドイツの数学者ヘーシュが不可避集合を探すための放電法を考案し、これをハーケンが改良し取り入れた。

不可避集合の探索には膨大な計算が必要だったため、このころから研究にコンピュータが活用されていった。1972年、アメリカの数学者でプログラミングに精通しているアッペルが、ハーケンの研究に加わった。

四色問題の証明

1976年、ハーケンとアッペルが1,936個からなる不可避集合を調べ、すべて可約配置だと確認し四色問題を証明をした。しかし従来の証明と違い、そのほとんどがコンピュータで行われていたため、人間が確認できない証明を証明と呼べるのか批判もあがった

四色問題の応用例

四色問題は地図の配色だけでなく、携帯電話通信システムにおいて隣り合う基地局同士の混信を防ぐための周波数配分に応用されている。