四色問題の書評・感想

2713views黒夜行黒夜行

このエントリーをはてなブックマークに追加
四色問題

まずこの四色問題を解くにあたり、非常に重要な定理があるのでまずそれを書こう。この定理は次のように説明される。

どんな地図にも、五個以下の隣国しか持たない国が少なくとも一つ含まれている

ちょっと分かり難い文章である。以下、二つの辺を持つ国を二辺国、という形で表現をすることにしよう。そうすると、この「隣国は五つだけ」定理というのはこのように表現される。

どんな地図にも、二辺国・三辺国・四辺国・五辺国のうち少なくとも一つは含む

さらに四色問題の証明にはもう一つ重要な概念が存在する。それが、「最小反例」である。
もし四色問題が間違っていると仮定してみる。即ち、五色以上の色を使わなくては塗り分け出来ない地図が存在すると仮定するのだ。その際、その五色以上の色を使わなくてはいけない地図の内、最小の国を有する地図を「最小反例」と呼ぶのである。この時、最小反例は四色では塗り分けることが出来ないが、最小反例より少ない国を持つすべての地図は四色で塗り分けることが出来る、という点が重要である。
さてここで、ケンプという数学者が登場する。このケンプという数学者は、ある時期四色問題を解いたと考えられた数学者である。11年後に致命的な欠陥が見つかり、証明が不完全であったことが分かるのだが、しかしこのケンプが生み出した方法は後の四色問題の攻略に大きな進展を見せたのである。
さてではケンプはどんな考え方をしたのか。ケンプは、最小反例を用いて証明をしたのである。
基本的な考えはこうである。
まず四色で塗り分けることの出来ない最小反例が存在すると仮定する。この最小反例は四色では塗り分けることは出来ないが、この最小反例より少ない国を持つすべての地図は四色で塗り分けることが出来る。
さて次に、「隣国は五つだけ」定理を用いる。この定理は、どんな地図であっても、二辺国から五辺国のうち少なくとも一つはあることを保証しているわけで、つまり最小反例にも二辺国から五辺国のうちどれか一つは必ずあるはずである。
ケンプが取った方法は、最小反例に二辺国から五辺国それぞれがあった場合の四種類のパターンを考え、それぞれについて緻密に検証を進めていくことで、最終的にどのパターンも四色で塗り分けられることを示す、というものであった。つまりどういうことかと言えば、初めの前提で最小反例が存在すると仮定した。最小反例が存在すると仮定して論証を進めたのに、最終的にその最終反例が四色で塗り分けられることが示された。これは矛盾である。この矛盾はどこから来たかと言えば、初めの前提、つまり最小反例が存在したという前提がおかしかったのである。つまり最小反例は存在しないのであり、最小反例が存在しないということは五色でしか塗り分けられない地図が存在しないということであり、よって四色問題は証明された、という論証である。
ケンプのこの証明は「ケンプ鎖」というアイデアを使った独創的なもので、誰もがこれで証明が出来たと考えたのだが、しかし11年後に間違いが指摘された。
さてその後も様々なアプローチが試みられたが、どうもうまくいかない。しかし19世紀末事態は大きく動き、新しく提唱された二つの概念を導入することで解決が見込まれるのではないか、と期待された。
その概念というのが、「不可避集合」と「可約配置」である。
「不可避集合」というのは、少しだけ「隣国は五つだけ」定理に似ている。「不可避集合」というのはつまり、地図を書く上でどうしてもさけることが出来ない形の集合のことである。「隣国は五つだけ」定理により、二辺国から五辺国までのどれか一つは必ず入るということは示されたわけだが、それ以外にも、地図を書く上で避けることが出来ないパターンというものがいくつも発見された。
もう一つの「可約集合」はというと、最小反例には含まれない国々の配置のことである。二辺国から四辺国まではすべて可約配置であり、こちらも他に様々なパターンが見つかっている。
四色問題の最終的なアプローチは、「可約配置の不可避集合」を見つける、ということに焦点が絞られた。この「可約配置の不可避集合」が一つでも見つかれば四色問題は証明されたことになるのだが、その理屈が分かるだろうか。
「可約配置の不可避集合」は不可避集合であるので、この世の中に存在するすべての地図にその配置が存在するということである。さらに一方で、「可約配置の不可避集合」は可約であるので、最小反例には含まれない。つまり「可約配置の不可避集合」というのは、この世の中のすべての地図に含まれ、かつ最小反例には含まれない配置であり、これが見つかるということは即ち、最小反例が存在しないということなのである。最小反例が存在しなければ四色問題は示されたことになる。
問題はいかにしてこの「可約配置の不可避集合」を探すか、ということである。

四色問題

四色問題

  • ロビン・ウィルソン

関連まとめ

本のまとめカテゴリー


コメントを書く