4色問題の解法

4色問題とは、全ての図形は、4色で塗り分けられるかと言う問題です。皆さんの考えを教えてください。5色要するとは、全ての5面が他の4面と接すること。それは、4本足の蛸に似ている。頭に4本の足が生えており、全ての4足が他の3足と接触出来るのか。両サイドの足を接触させると間の足は囲まれる為、向かいの足には接触出来ない。球面上でも同じです。4本足蛸が、ボールを抱いた形です。ボール上で4本足が接触出来るか。平面の時と結果は同じ。5色必要な図形は作れない。4色必要とは、4面が他の3面に接触しているので、3本足の蛸だ。3本の足は接触出来る。単純化すると120度で3分割したドーナッツ形になる。図の外の面が頭。球面上では、三本足蛸がボールを抱えた形を単純化すると三角柱となる。底面が蛸の頭で、3側面が足です。球面中の一面が無限に広がると平面になる。平面上絵の周囲の面は、収縮すると球面上の1面になる。絵は同じです。平面上の無限に広い1面と、球面上の1面は共に1色が必要で同じこと。三角柱底面を無限に広げると、平面の120度で三分割したドーナッツとなる。この三角柱の上面と底面を接触出来るでしょうか。3側面が筒状ならそれぞれ接触しています。3側面上で上面と底面を接触すると、3側面は紐状になり接触が切られます。三角柱の中外で接触するしかありません。それはドーナッツになります。中接触の時、横置ドーナッツを水平に3面に分け、内1面を垂直に3分割した形となる。外接触の時、横置ドーナッツを垂直に3面に分け、内1面を水平に3分割した形となる。若しくは、クラインの壷状となる。よって球面上5色を必要とする図形は描けない。三角柱底面を広げると、平面の120度三分割ドーナッツになる。中の穴を外の空間に接触させると、ドーナッツは切られ紐状になり3面の接触が切れる。平面上でも、5色を必要とする図形は描けない。4面に接触する面は4角形以上です。3角形は3面にしか接しない。5つの四角形をそれぞれ接する様に置けるでしょうか。四角形の4辺は接触する（2本が一本になる）ので、出来た図の線は10本です。10本の線で5つの四角形が作れるでしょうか。立法体の辺は12本です。2辺を消すと面は4面となり5面は描けない。ドーナッツなら描ける。従って、平面及び球面に描かれたどの様な図形も、4色で塗り分けられると言えます。

No.4 回答者： alice_38 回答日時： 2010/01/02 01:22

この質問者、またやっているんですね…

例のコンピュータを使った証明は、確か、

(1) あまり国数の多くないいくつかの地図
からなる集合 S を設定し、どんな平面地図も
S の元を少なくともひとつ、部分グラフとして
含むことを示す。(S を「不可避集合」という。)

(2) S の各元 M について、その地図の中に
ひとつの国 F をとり、M を含む平面地図が
F を除いて 4 色塗り分け可能なら、
A No.2 の方法で、F を含めて 4 色塗り分け可能
になることを示す。

…というステップを踏んで、
n-1 国地図が 4 色塗り分け可能なら
n 国地図も 4 色塗り分け可能である
という帰納法に持ち込んでいたハズです。

S の元数が膨大なので、(2) を検証するのに
コンピュータを使っていたと思います。
網羅性に関する部分は (1) ですが、
これは人手でやっていたような。

No.3 回答者： Tacosan 回答日時： 2010/01/01 15:54

ですね＞#1. 最初の「5色要するとは、全ての5面が他の4面と接すること。

」がすでに正しくないので, それを基礎に置く限り正しい議論ができるとは思いがたいです.
5色じゃなくて 4色で考えれば簡単にわかる (この場合上の「5」と「4」がそれぞれ「4」と「3」に変わる) んだけどなぁ.
あと, 「コンピュータを使った」のは「パターンが多すぎて, すべての場合を網羅しているかどうかを判定するため」だったかも＞#2.

No.2 回答者： nag0720 回答日時： 2010/01/01 08:22

＃１です。

追記。

だいぶ前に読んだ本の記憶ですが、４色問題の最初の証明は帰納法を使ったようです。


n+1個の面からなる図形があったとき、1つの面（Fとします）を除いて残りのn面を４色で塗り分ける。
面Fに接する面の色が３色しかない場合は、残りの色で塗ればＯＫ。
問題となるのは、周りの面が４色使っている場合です。

面Fが４面と接している場合は、周りの４面が別々の色を使っていることになる。
周りの４面を左回りにA,B,C,Dとし、その色をa,b,c,dとする。
面Aに接するcの色の面を探す。さらにそのcの色に接するaの面を探す。
そのようにして、a-c-a-c-a-c-・・・というacの面の鎖を全部調べる。

(1)acの鎖に面Cが含まれない場合。
その鎖に含まれるaとcの色を交換する。
面Fに接する面の色はb,c,dの３色になるので、面Fにはaを塗ることができる。

(2)acの鎖に面Cが含まれる場合。
面Bから始めてbdの鎖を探す。
acの鎖には面A,Cが含まれているので、bdの鎖に面Dが含まれることはない。
その鎖に含まれるbとdの色を交換する。
面Fに接する面の色はa,c,dの３色になるので、面Fにはbを塗ることができる。

面Fが５面と接している場合は、・・・・・


というようにして、すべてのパターンを調べて証明したようです。
パターンの数が多すぎて、コンピュータを使わないと証明できなかったらしいです。
（もし記憶違いならすみません）

No.1 回答者： nag0720 回答日時： 2010/01/01 07:19

言いたいことは、

「５つ面が相互に接触するような図は描けない」
ということでしょうか。

それはその通りですが、それが４色で十分だという証明にはなりません。

４色問題の難しいところは、局所的には４色で塗り分けられたとしても、広域的に４色で十分かどうかは別問題だということです。


例えば、ある図形があって、それを境界線に沿って２つに切り分けたとします。
そして、それぞれの図形が４色で塗り分けられたとします。

その後、その２つの図形を合わせて元の１つの図形に戻したときも、４色で塗り分けられていると言えるでしょうか？
２つの図形の境界線では、必ずしも違う色が合わさるとは限らないので、同じ色が合わさった場合は２つの図形の塗り分けかたが正しくなかったということです。
それでは、２つの図形の境界線で必ず異なる色になるような、２つの図形の塗り分けかたが存在するでしょうか？
（４色問題は上記のような問題と捉えることもできます）


このように、局所的に４色塗り分け可能でも、それを合わせたときにもきちんと塗り分けられているようにできるかどうかは、さらに考察する必要があります。