四色問題(読み)よんしょくもんだい(英語表記)four-color problem

日本大百科全書(ニッポニカ)の解説

四色問題(よんしょくもんだい)
よんしょくもんだい
four-color problem

どのような地図でも4色で塗り分けられるか否かを明らかにする問題。1852年にロンドン大学教授であったド・モルガンに、学生が「線で接する国を違う色で塗るとして、地図を塗るのに必要な色の最大数は4である」ということについての、ある証明が正しいかどうかを尋ねた。ド・モルガンは答えがわからず、当時の有名な数学者であり物理学者でもあったW・R・ハミルトンに問い合わせの手紙を書いた。これが四色問題の発端といわれている。質問した学生はのちに物理学者となったガスリーFrederick Guthrie(1833―1886)で、兄からこの問題の証明を聞き、その真偽をド・モルガンに尋ねたのであった。
 地図では図A―(イ)の点aのように、色分けしたい国々(あるいは州など)の境界線がしばしば1点で交わることがある。しかしこの場合には、図A―(ロ)の灰色部のような架空の国を考え、この国も含めて色分けし、その色分けをそのまま図A―(イ)の点aの周りの国々の色として定めればよいので、国の境界はいつでも線で相隣るものと考えてよい。
 図Bのような地図はどの国も互いに隣り合っているから、4色が必要であることがわかる。したがって、問題はどんな地図でも4色あれば国々を塗り分けることができるか、すなわち、地図塗りには4色で十分であるか否かを明らかにすることであり、それが四色問題である。
 この問題は、1870年代後半にケーリーArthur Cayley(1821―1895)が学会へ難問らしいと提唱してから、しだいに研究が進められるようになった。まず、1879年にケンペAlfred Bray Kempe(1849―1922)は「四色問題に関する地理学的問題」の論文を書き、これを証明した。この証明はその約10年後、ヒーウッドPeray John Heawood(1861―1955)が誤りを発見するまで正しいと思われていた。
 ケンペの考え方は数学的帰納法による。まず国の数が4個以下であればもちろん4色で十分である。国の個数がn個のときに4色で十分であると仮定してn+1個の国の地図の場合、その国の数を減らす還元法を発見し、帰納法の仮定を用いてこの場合の証明をする、というものである。
 この還元法を、たとえば地図に図C―(イ)のように二角形や三角形が現れる場合について考えてみる。これらの場合、二角形、三角形を無視して、たとえば図C―(ロ)のような地図について塗れば、最大3色で塗れるから、残りの1色を二角形、三角形に割り当てることによって4色で塗れる。よって二角形、三角形の国が現れれば、その地図は還元できることがわかる。
 図C―(イ)のように地図が与えられたとき、それを平面グラフとみて、その双対グラフを考える。つまり各国の中に新しく一つの頂点をとり、隣接する国の2頂点をその境界線と交わるような辺で結んでできるグラフを考える。この双対グラフは平面グラフであるが、頂点が国を表しているし、また各国は辺で接しているから二角形、三角形の場合と同様に処理して、双対グラフの面は三角形のみであると考えられる。よって双対グラフのほうが元の地図より四色問題としては扱いやすい。この双対グラフの頂点から辺がn本出ているとき、その頂点をn枝点という。n=1,2の場合は前の二角形、三角形の場合であるから還元して除いてしまう。すると頂点はすべてn≧3に対するn枝点となる。n枝点の総数をVnで示すと、オイラーの多面体の公式から
3V3+2V4+V5-V7-2V8-……=12
となる。この式の右辺は12>0であるから、左辺のV3,V4,V5の少なくとも一つは正である。すなわち、3枝点か4枝点か5枝点のどれか一つは少なくともどの双対グラフにでも現れる。
 よって、3枝点、4枝点、5枝点について還元法を発見すればよい。ケンペはそれを発見したつもりであったが、五枝点の処理が不十分であった。これを修正するのに多くの数学者が約100年間もさまざまな努力をしたのである。
 ヘーシュHeinrich Heeschは1936年ころより40年間、その一生のほとんどをこの問題の解決に尽くし、よい結果を得ていたが、決定的な解決はアメリカのイリノイ大学にいるその弟子のハーケンWolfgang Haken(1928― )とその協力者アッペルKenneth Appelによって1976年に与えられた。5枝点以上の還元は、複雑で、膨大な数の場合に分かれるが、アッペルとハーケンは4年間をかけて三つの別々の計算機を用いて千数百時間の計算時間を費やし、ようやくそのすべての場合について還元可能であることを実証したのである(計算機使用料は正規に払うと10万ドルを超えるといわれる)。[野口 廣]
『一松信著『四色問題』(1978・講談社)』

出典 小学館 日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について 情報 | 凡例

関連語をあわせて調べる

今日のキーワード

iDeCo

個人型確定拠出年金と呼ばれる任意の私的年金制度のひとつ。加入者が毎月決まった金額を積み立てて、金融機関が用意する定期預金・保険・投資信託といった金融商品から運用方法を選び、60歳以降に年金または一時金...

続きを読む

コトバンク for iPhone

コトバンク for Android