アニヲタWiki(仮)
アニヲタWiki(仮)

四色問題(数学)

登録日：2024/09/26 Thu 01:46:27
更新日：2024/09/29 Sun 10:54:08
所要時間：約 8 分で読めます




あのやり方は人間が手作業で調べるには膨大すぎる。
だからこそコンピュータを使ったんだろうが、おかげでその証明が正しいのかを完璧に判断する手段がない。
確認にもコンピュータを使わなければならないなんてのは、本当の数学じゃない。

―――「容疑者Xの献身」


「四色問題」とは、図面の彩色に関する数学の問題である。
上記の通り、「容疑者Xの献身」で引用されているため、そこから知った人も少なくないだろう。
この問題の主張は正しい事が証明されているため、今日では「四色定理」という名前で呼ばれることもある。



【概要】

問題の内容（命題）を大雑把に表現すると以下の通りになる。

“隣り合う領域が同色にならない様に平面上の地図を彩色する場合、どんな地図でも高々4色で塗り分けることが出来るか”

この「4」という数については、彩色に必要な色の数を小さい順に調べていった結果。
1色/2色/3色では塗り分けられない*1ような地図の例を作る事が出来たため、「4色の場合は彩色が可能なのか？」という観点から設定された数値になる。

問題提起がなされたのは1852年。
とある学生の疑問に数学の教授ド・モルガン*2が調べたところ、証明などが立てられず苦戦し、難問として世に知られる様になっていった。

その後数学的に定式化されたうえでの学術誌掲載を経て、1976年に問題に対する解答が提示され、「平面上の任意の地図は高々4つの色で隣同士が同じ色にならないように彩色が出来る。」という結論が出ている。


…が、この解答の提示方法、即ち「証明」の内容が色々と物議を醸すものであったため、ある意味この問題の1つの特徴になっている。
(詳細は後述。)


【前提】

四色問題についてだが、彩色に用いられる条件として以下の内容を前提として考える必要がある。

①：平面上の領域は飛び地を持たない。

大雑把な表現で言うと、「飛び地」とは主となる領域からは分離しているが同じカテゴリに分類される領域のこと。

日本の地理で例えると和歌山県の北山村が該当する。
北山村は、北・西側は奈良県、南・東側は三重県の市町村に囲まれており、他の和歌山県のどの市町村とも隣接していない。
だが、都道府県分類上は和歌山県に属しているため、和歌山県の飛び地の条件に該当する。

この様な飛び地に対して「同じ領域に属する部分をすべて同じ色で塗る」という条件の下で塗り分けを行うと4色では塗り分けを行う事が出来ず、(飛び地の数や隣接する領域の条件で使用する色の種類が大きく変わってしまう関係で)色の種類がいくつあっても足りなくなってしまう。
同じ理由で通常飛び地とされないが「島国は領域の島を同じ色で塗る」というルールと、「水域は必ず青く塗る」というルールもここでは使用できない。*3

北山村の例では都道府県単位の話だったが、これを国単位の話に置き換えた場合でも飛び地を持つ国*4が存在しているため、世界地図には四色問題の主張をそのまま適用することは出来ない。


②：1点のみで接している領域は同じ色での彩色が出来るものとする。

これも同じ理由からで1点のみでの配色の一致を許容しない場合、4色では塗り分けきれなくなってしまうため、4色以内で配色を解決するに設定された条件になる。
どういう意味か分からない人はルーレットやダーツの的のような形状を考えてみれば、「中心の点で隣接する別のエリア」が扇状部分を細かくすればいくらでも作れると分かるはず。

実際の地図では所謂「質点」の様な幅を持たない点というものは存在せず、物理的な点には幅が存在し、遠目からでは1点でしか接していない様に見えてもクローズアップすれば小さな幅の線で接している状態になる。
そのため、このような状況が成立するようなこと自体が稀で、アメリカの4州(ユタ州・コロラド州・ニューメキシコ州・アリゾナ州)の境界地点として人為的に設置された「フォー・コーナーズ」の様な地点でなどにしか当てはまらない。

因みに四色問題については平面の他にも球面などについても同じ様に4色での塗分けを考えることができるため、地図の他に地球儀上での塗分けというのも考えることが出来る。

なおこの問題は「グラフ理論」という幾何学分野の考えによって彩色対称の面を1点、「2つの面が隣り合っている」という状態を「点と点が線分で結ばれている」という状態に置き換えると「平面グラフ」というものに概念を置き換えることが出来る。
(ここで言う「グラフ」とは小学校で習うような所謂「数と数の関係の図表化」ではなく「辺」と「点」の組み合わせで出来る図形のような物を指す。)

この状態で言い換えると、四色問題は「グラフ上に含まれる辺をどのように選んでも、両端の点の色が違う色になる様にグラフを作るには最大でも4色あれば実行できる」という内容になる。

1879年にこの問題の証明についてアルフレッド・ケンプが「どんな地図にも2辺国～5辺国*5のうちいずれかが必ず含まれる」という事実を元に証明を提示した。
だが、この証明には誤りが含まれており、「2辺国」～「4辺国」の場合には4色問題の適用が可能である事が分かったが、5辺国の場合は4色で塗り分けられるかが完全には検証できていないという欠陥があった。

その後、5辺国を含む場合の図は分類が非常に多い事が分かり、調べるのが非常に困難であるという事実が分かり、証明は難航していたが……。



【エレファントな証明】

上述した通り1976年にケネス・アッペルとヴォルフガング・ハーケンの2名によってこの問題に関する証明が提示されたのだが、その内容が「美しくない方法である」とされている。


詳細を割愛してアイデアを物凄く大雑把に言うと、

①：平面上の任意の地図は(5辺国があるパターンを含めて)1500弱のカテゴリーに分類した。
②：コンピューターの計算で①の配色パターン全てが4色で塗り分けられることを示した。

という旨になっている。

この証明プロセス……特に②の工程について多くの人から「(数学的には正しいかもしれないが)美しくない」という評価を受けている。


理由は簡単。
上記の証明法を多少の誤解を恐れずに言い換えると

「コンピューターを使って平面の塗分け方をパターン化して、コンピュータで各パターンを調べて塗分け可能な事を示した」
≒
「取り得るパターンを全部確認して調べる」

という所謂「総当たり」や「虱潰し法」に該当する方法*6で強引に調べる内容だったからである。


また、これらが「コンピューター」の機械処理によってなされ、証明の内容がプログラムの構文、内容の妥当性を確認するのにもプログラムの検証が必要になるというある種の機械任せに解かれたという側面も「この問題の証明が美しくない」とされていた一因。
1976年当時はコンピューターを用いた証明というものはあまり一般に認知されておらず、その証明の妥当性を手で調べられないことも問題の1つとして挙がり、この証明が美しくないとされる理由の1つになっていた。


現在ではプログラムの改良により、当時よりも効率化された四色問題の検証が出来る様になってはいる。
ただ、今でもコンピューターでの検証に頼らない証明方法及び証明の妥当性の確認方法は見つかっていないのが現状である。


数学の問題を短く、かつシンプルにまとめられた論理展開で解く事は、一般に「エレガントな証明」と呼ばれる。
これは証明方法として好ましいものとして扱われる。
だが、四色問題の解き方はそれとは大きくかけ離れたものであった事から「エレファントな証明」と揶揄されてしまう結果になってしまった。

現状人の手だけで完結する証明法は見つかっていないが、興味のある人は挑戦してみるといいかもしれない。



【関連する問題】

  • 五色問題
四色問題の系(定理から導かれる派生命題)で、5色を使って隣り合う面が同じ色にならないように配色を行う問題。
四色問題が真である以上、こちらも真になるのだが証明は四色問題よりずっと易しく、誤りを指摘されたケンプの証明を改良することでまとまった論理展開で解ける。


  • 三彩色問題
「与えられた面が隣り合う色が同じ色にならないよう、3色で塗り分けられるか」を確認する問題。
NP完全問題という特殊なカテゴリの数学の問題に位置づけられており、「既に解かれた問題の正誤検証が多項式時間で可能(NP問題である)」「他の任意のNP問題に対して問題の適切な変形などを行う事で三彩色問題に帰結させられる(NP困難問題である)」の2条件を満たしているという特徴がある。
(大雑把に言うなら「NP問題の中では難しい部類の問題だが、NP困難の問題の中では易しい部類の問題になる」という事である。)


【余談】

  • 球面以外でも……
四色問題が平面の他に球面でも適用できると書いたが、これらは穴の開いていない立体(多様体)でも隣り合う面が4色で塗り分け出来ることが知られている。
一方で穴の開いている立体の場合は話は別でドーナツ状の立体(トーラス)で隣り合う面が同じ色にならないようにするには最大で7色が必要になる事が分かっている。
また、必要な色の数も立体上に存在する穴の数によって変化することが知られている。


  • 「エレファントな証明」の是非
部外者、特に本項目を読むような層からは「エレファントな証明」「美しくない解決方法」として有名であり、冒頭のように文学作品などでもたびたび「強引な解決方法」「非直感的な証明」の例として非常に好まれるのだが、
数学者側は現在ではむしろコンピューターを用いた証明というのは「手段のひとつ」として認める動きが強まっている*7。
現在では「計算機援用証明」という証明の手段として、コンピューターは立派に活用されている。
無論「しらみつぶしでやるしかないぞ」という結論が出て、さらにそのプログラムに問題や穴がないかというのをかなり綿密にチェックしていかなければならないため、こっちの方がはるかにめんどくさい。ゲームにおいてチートコードを使うような印象とは正反対の、まさに最後の手段。
四色問題はその最初の例であり、やっていることが「数学は本来知恵の輪のようなもののはずなのに、それを強引に引きちぎっている」ようにしか見えなかったことから悪名が高くなってしまったのがこの問題なのである。あと問題が小学生でも理解できるほど単純というのも、知名度に貢献しているかもしれない。
アニヲタにもわかりやすいイメージをすれば、メルエム戦でネテロ会長が戦略兵器「貧者の薔薇」を使おうと考えるくらいに手ごわい証明ってところ。
最初から核兵器を使うつもりなら怒られるけど、問題が手ごわすぎるなら使わざるを得ない。そしてあの展開や決着が「やっぱ納得いかねぇ」と思う人もいるだろう。本当にそういう印象的な問題。

比較的単純な計算で済む問題、たとえば「この条件を満たす数は存在しない」という問題に対しては、計算機は非常に強く、計算機によってその反例が見つかる形で否定的に解決された問題は数多い。
無論現代でもエレガントな証明が求められるのは事実だが、今や円周率の計算をはじめ、コンピューターは数学の世界にはなくてはならないものになっているのだ。




追記・修正は隣り合うwiki篭りを同じ趣味に染めないようにしながらお願いいたします。

この項目が面白かったなら……＼ポチッと/

▷ コメント欄

タグ：

数学 幾何学 エレファント 証明 容疑者Xの献身 ガリレオ 四色問題 幾何学 地図 グラフ グラフ理論 コンピューター 四色定理 彩色 × エレガント ○ エレファント
+ タグ編集
  • タグ：
  • 数学
  • 幾何学
  • エレファント
  • 証明
  • 容疑者Xの献身
  • ガリレオ
  • 四色問題
  • 幾何学
  • 地図
  • グラフ
  • グラフ理論
  • コンピューター
  • 四色定理
  • 彩色
  • × エレガント ○ エレファント
タグの更新に失敗しました
エラーが発生しました。ページを更新してください。
ページを更新
「四色問題(数学)」をウィキ内検索
最終更新：2024年09月29日 10:54

*1 1色は言うまでもないが、2色は円を扇状に三等分するとすべて他の2エリアに接する以上、どうやっても2色では同色隣接ができてしまう。この円の周囲を含むエリアも塗るようにすると4エリアすべてが他の3エリアと接するので3色でも不可能…とここまでは速攻反論ができた。

*2 高校で習う「ド・モルガンの法則」などで名を残している。

*3 地球の場合、海は全部つながっているので飛び地と無問題だが、湖も青く塗るルールでやるとカスピ海など大きな湖が同色飛び地になってしまう。

*4 アラスカ地方を飛び地として持っているアメリカなどが例として挙がる。

*5 隣り合っている面の数が2つなら2辺国、3つなら3辺国、という風にn個の面と隣り合っている面を「n辺国」と呼ぶ。

*6 数学的な論理展開を伴ったスマートさのある内容ではない

*7 ブルーバックスの「四色問題 どう解かれ何をもたらしたのか」などに詳しい。