４色問題 目次へ戻ります。 国の色分けの４色問題(色分けの上限数)はコンピュータで解決されました。 このため後追いになりますが、４色問題についての私の考えを書いてみます。 国々の接触のし方は点か線で接触する場合しかありません。 国々が１点で接触している場合 ＿＿＿ ＿＿＿ ＿＿＿＿＿ ＿＿＿＿＿ ｜Ａ｜Ｃ｜｜Ａ｜Ｃ｜｜＼Ｅ ｜Ｃ｜｜＼Ｅ ｜Ｃ｜ ｜＿｜ ｜｜＿｜＿｜｜Ａ＼ ｜ ｜｜Ａ＼ ｜ ｜ ｜Ｂ｜ ｜｜Ｂ｜Ｄ｜｜＿＿＼｜＿｜｜＿＿＼｜＿｜ ｜＿｜＿｜｜＿｜＿｜｜Ｂ ｜Ｄ｜｜Ｂ ／｜Ｄ｜ ｜＿＿＿｜＿｜｜ ／Ｆ｜ ｜ Ａ―Ｂ―Ｃ ｜／＿＿｜＿｜ ＼＿／ Ａ―Ｂ―Ｄ―Ｃ ＼＿＿＿／ Ａ―Ｂ―Ｄ―Ｃ―Ｅ ＼＿＿＿＿＿／ Ａ―Ｂ―Ｆ―Ｄ―Ｃ―Ｅ 国々はこの様に接触してます。 ＼＿＿＿＿＿＿＿／ 国々の総数が偶数の場合は２色で色分けできます。 ＿＿＿ ＿＿＿＿＿ ｜１｜２｜｜＼２ ｜１｜ １、２は互いに異なる色を表します。 ｜＿｜＿｜｜１＼ ｜ ｜ この場合は２色使われています。 ｜２｜１｜｜＿＿＼｜＿｜ これは、最後に色を決める国に隣接する２国の ｜＿｜＿｜｜２ ／｜２｜ 色が同色であるためです。 ｜ ／１｜ ｜ こうなるのは、ある国Ｅに隣接する２国(ＡＣ) ｜／＿＿｜＿｜ が、互いに孤立しているからです。 国々の総数が奇数の場合は３色で色分けできます。 ＿＿＿ ＿＿＿＿＿ ｜１｜３｜｜＼３ ｜２｜ 反時計回りに色を決めていったときに、２色を ｜＿｜ ｜｜１＼ ｜ ｜ 交互に使っていきます。 ｜２｜ ｜｜＿＿＼｜＿｜ 最後の国の色を決めるとき、３色目が必要にな ｜＿｜＿｜｜２ ｜１｜ ります。 ｜＿＿＿｜＿｜ これは、３色目の国(Ｅ)に隣接する２国(ＡＣ) の色が異なるためです。 こうなるのは、ある国(Ｅ)に隣接する２国(ＡＣ)が、互いに孤立し、異な る色を持っているからです。 国々が１国(Ｃ)と線で接触している場合 ＿＿＿ ＿＿＿＿＿ ＿＿＿＿＿＿＿ ＿＿＿＿＿＿＿＿＿ ｜Ａ｜Ｂ｜｜Ａ｜Ｂ｜Ｄ｜｜Ａ｜Ｂ｜Ｄ｜Ｅ｜｜Ａ｜Ｂ｜Ｄ｜Ｅ｜Ｆ｜ ｜＿｜＿｜｜＿｜＿｜＿｜｜＿｜＿｜＿｜＿｜｜＿｜＿｜＿｜＿｜＿｜ ｜Ｃ＿＿｜｜Ｃ＿＿＿＿｜｜Ｃ＿＿＿＿＿＿｜｜Ｃ＿＿＿＿＿＿＿＿｜ Ａ―Ｂ Ａ―Ｂ―Ｄ Ａ―Ｂ―Ｄ―Ｅ Ａ―Ｂ―Ｄ―Ｅ―Ｆ ＼／ ＼ ｜／ ＼ ＼｜／ ＼ ＼｜／ ／ Ｃ Ｃ ―Ｃ ―Ｃ― 国々はこの様に接触しています。 この場合はすべて３色で色分けできます。 ＿＿＿ ＿＿＿＿＿ ＿＿＿＿＿＿＿ ＿＿＿＿＿＿＿＿＿ ｜１｜２｜｜１｜２｜１｜｜１｜２｜１｜２｜｜１｜２｜１｜２｜１｜ ｜＿｜＿｜｜＿｜＿｜＿｜｜＿｜＿｜＿｜＿｜｜＿｜＿｜＿｜＿｜＿｜ ｜３＿＿｜｜３＿＿＿＿｜｜３＿＿＿＿＿＿｜｜３＿＿＿＿＿＿＿＿｜ これは、上の段は２色を交互に使うことができ、下段は３色目を使えば良い からです。 こうなるのは、Ｂ国の隣り合う２国ＡとＤは、互いに孤立しているためです。 ここでは、いずれの場合も３色以下の使用になり、限度数４に達しないこと を確認しておきます。 ―――――――――――――――――――――――――――――――――― 点で互いに接触している場合は、奇数個が最大で、３色使います。 線で接触する場合も、最大で、３色使います。 点接触と線接触の最大色数のもの同士を組み合わせた場合で考えます。 ＿＿＿＿＿＿＿ ｜Ａ ｜Ｃ ｜Ｆ｜ Ａ,Ｂ,Ｄは３国の点接触関係です。 ｜ ｜＿＿｜ ｜ Ｃ,Ｄ,ＥとＦは線接触の関係です。 ｜＿＿｜Ｄ ｜ ｜ ＿＿ ｜Ｂ ｜＿＿｜ ｜ ／＿ ＼ ｜ ｜Ｅ ｜ ｜｜／ ＼ ＼ ｜＿＿｜＿＿｜＿｜Ａ―Ｂ―Ｄ―Ｃ―Ｆ―Ｅ ｜ ｜＼＿／ ／｜ ＼ ＼＿＿／／ ＼＿＿＿／国々はこの様に接触しています。 ＿＿＿＿＿＿＿ ｜１ ｜２ ｜４｜ ＡとＥは互いに孤立しているので同色です。 ｜ ｜＿＿｜ ｜ ＢとＣも互いに孤立しているので同色です。 ｜＿＿｜３ ｜ ｜ (互いに孤立しているグループ内では同色です。) ｜２ ｜＿＿｜ ｜ (この考えは前に書いた点接触の場合と異なります。) ｜ ｜１ ｜ ｜ Ｄはこれら以外の色を使うので３の色です。 ｜＿＿｜＿＿｜＿｜ Ｆは１,２,３以外の４の色を使います。 この場合の色分けは他のやり方でもできます。 点接触は、この段でお分かりのように、線接触として扱えます。これからは 線接触のみで考えることにします。 ＿＿＿＿＿＿＿＿ ｜ ＿＿＿＿｜Ａ国が左図のようになった場合は、上とは色分けを ｜ Ａ ｜Ｃ ｜Ｆ｜変えます。 ｜ ｜＿＿｜ ｜ ＿＿＿＿＿ ｜ ＿＿｜Ｄ ｜ ｜ ／ ＿＿ ＼ ｜｜Ｂ ｜＿＿｜ ｜｜ ／＿ ＼ ＼ ｜｜ ｜Ｅ ｜ ｜ ＼｜／ ＼ ＼ ＼ ｜｜＿＿｜＿＿｜＿｜ Ａ―Ｂ―Ｄ―Ｃ―Ｆ―Ｅ ｜＿＿＿＿＿｜ ｜ ｜ ｜＼＿／ ／｜＼ ＼ ＼ ＼＿＿／／ ／ ＼ ＼＿＿＿／ ／ ＿＿＿＿＿＿＿＿ ＼＿＿＿＿＿／ ｜ ＿＿＿＿｜ 国々はこの様に接触しています。 ｜ １ ｜３ ｜２｜ ｜ ｜＿＿｜ ｜互いに孤立している国は同色を使います。 ｜ ＿＿｜４ ｜ ｜(互いに孤立しているグループ内では同色です。) ｜｜２ ｜＿＿｜ ｜(ＣとＥのグループ、ＢとＦのグループのことです。) ｜｜ ｜３ ｜ ｜このため左図のような４色の色分けになります。 ｜｜＿＿｜＿＿｜＿｜ ｜＿＿＿＿＿｜ ―――――――――――――――――――――――――――――――――― 国々の色分けに必要な色数が４色であるわけを説明します。 ある国(Ａ)に接触している国数が５以上に増加すると、５以上の部分は互い に孤立なグループに入ります。 同じグループ内の孤立した国々同士は、お互いに同じ色を使えます。 互いに孤立なグループは３グループ以上にはなりません。 なぜならある国(Ａ)の周りを取り囲む国は、最高で３グループにしかならな いからです。 Ａ国の周りを奇数個の国々が取り囲んでいたら３グループになります。 Ａ国の周りを偶数個の国々が取り囲んでいたら２グループになります。 最も多い３グループに１色ずつ割り当てると３色必要です。これに自国の １色を加え、必要な色数は４色になります。 ―――――――――――――――――――――――――――――――――― 自国を取り囲む国々が４カ国以上になると、４カ国以上の国は互いに孤立な ３グループ(または２グループ)に入ります。この理由を説明します。 ４カ国目までは、お互いの国々が孤立せずに、すべての国々と互いに接触し あうことがでます。 ２カ国 ＿＿＿＿＿ ｜Ａ ｜Ｂ ｜ ｜＿＿｜＿＿｜２色でこの国々を色分けできます。 Ａ――Ｂ ２カ国はこのように接触しています。 ３カ国 ＿＿＿＿＿ ｜ ｜Ｂ ｜ ｜Ａ ｜＿＿｜ ｜ ｜Ｃ ｜ ｜＿＿｜＿＿｜３色でこの国々を色分けできます。 Ａ―――Ｂ Ａ―Ｂ―Ｃ ＼ ／ ＼＿／ Ｃ ３カ国はこのように接触しています。 ４カ国 ＿＿＿＿＿＿ ｜Ａ ｜Ｂ ｜ ｜ ――｜ ｜ ｜｜Ｄ ｜――｜ ｜｜＿＿｜Ｃ ｜ ｜＿＿＿｜＿＿｜４色でこの国々を色分けできます。 ＿ ＿ ／ ＼ ／ ＼ Ａ―Ｄ―Ｂ Ａ―Ｂ―Ｄ―Ｃ ＼｜／ ｜＼＿／ ／ Ｃ ＼＿＿／ ４カ国はこのように接触しています。 しかし、５カ国では、お互いに孤立せずに、同時に、すべての国々と互いに 接触しあうことができません。 ５カ国の１ ＿ ｜Ｅ｜＿＿＿＿＿＿＿ ｜ ｜Ａ ｜Ｂ ｜｜ ｜ ｜ ――｜ ｜｜ ｜ ｜｜Ｄ ｜――｜｜ ｜ ｜｜＿＿｜Ｃ ｜｜ ｜ ｜＿＿＿｜＿＿｜｜ ｜＿＿＿＿＿＿＿＿＿｜ この場合ＥとＤが互いに孤立しているため、ＥとＤは同色でよいことに なります。つまりこの５カ国は４色で色分けできます。 ＿ ＿＿ ／ ＼ ／＿ ＼ ５カ国はこのように接触してい Ａ―Ｄ―Ｂ ｜／ ＼ ＼ ます。 ｜＼｜／｜ Ａ―Ｂ―Ｄ―Ｃ―Ｅ Ｅ―Ｃ ｜ ／｜＼＿／ ／ ／ ＼＿／ ｜ ＼＿＿／ ／ＤはＢ―Ｃ線、Ｃ―Ａ線、Ａ―Ｂ線 ＼＿＿＿＿＿／ により完全に囲まれています。 このため囲まれた線に交わらずに Ｄ―Ｅ線を引けません。 Ｄ―Ｅ線を引けないことは、ＤとＥが互いに孤立であることを表します。 ＡからみるとＢＣＤＥの４カ国に線が引かれています。Ａ国を含めてＢＣＤ Ｅの５カ国があり５色必要です。しかし、ＤとＥは互いに孤立の関係があり、 同色にできます。したがって、この場合は５色でなく４色で塗り分けられま す。 国数がさらに増えると、増えた国は互いに孤立している国のグループに入り ます。 ＿＿＿＿＿ ／＿＿＿ ＼ ４ ｜／ ＼ ＼ ＼ Ａ――Ｂ――Ｄ――Ｃ――Ｅ――Ｆ――Ｇ――Ｈ――Ｉ ／ /｜＼＿１＿／２ ／３ ／２ ／ ｜ ｜ ＼＿＿＿＿＿／ ／ ／ＦがＢと接していなければ１の ＼ ＼＿＿＿＿＿＿＿＿／ ／ グループに入ります。 ＼＿＿＿＿＿＿＿＿＿＿＿／ ＦがＢと接していれば３のグループ に入ります。 ＧＨＩも同様に決めていきます。 Ｂがない場合は、Ａによって決まるグループ数は２になります。 この場合は３色で塗り分けられます。 Ａ国に接している国は、３グループ以下のいずれかに必ず入ります。 (Ａ国と国境線を接している国々の色分けに必要な色数) ＝(互いに孤立している国のグループ数)＋(孤立していない国数)＋(自国) ＝(塗り分けに必要な色の数) ＝(４以下) になると思います。 (互いに孤立している国のグループ数)＋(孤立していない国数) ＝(３以下) であるはずです。 ただしこの式の妥当性を私は確かめていません。 国と国の間が接触していない場合も、周りの関係から、グループに分ける必 要があります。 まだ試したことはありませんが、すべての国を直線状に並べることができる と思います。この直線上で、色分けのグループを決定できると思います。 これは人力でやると時間がかかるので、コンピュータでやるのかな。でも私 はプログラムが書けないので、できません。 ５カ国の２ ＿＿＿＿ ｜Ｅ ＿ ｜ ＿＿＿ ｜ ｜Ａ｜｜｜Ｂ ｜｜ ｜ ｜ ――｜ ｜｜ ｜ ｜｜Ｄ ｜――｜｜ ｜ ｜｜＿＿｜Ｃ ｜｜ ｜ ｜＿＿＿｜＿＿｜｜ ｜＿＿＿＿＿＿＿＿＿｜ この場合ＥとＤが互いに接触し、孤立しません。しかしＡとＢが互いに 孤立し、ＡとＢは同色でよいことになります。つまりこの５カ国も４色 で色分けできます。 ＿ ＿＿ ／ ＼ ／＿ ＼ ５カ国はこのように接触して ｜ Ａ―Ｄ―Ｂ ｜／ ＼ ＼ います。 ＼｜＼｜／｜ Ｅ―Ｄ―Ａ―Ｃ―Ｂ Ｅ―Ｃ ｜ ／｜＼＿／ ／ ／ ＼＿／ ｜ ＼＿＿／ ／ ＼＿＿＿＿＿／ ＡはＤ―Ｃ線、Ｃ―Ｅ線、Ｅ―Ｄ線により完全に囲まれています。 このため囲まれた線に交わらずにＡ―Ｂ線を引けません。 Ａ―Ｂ線を引けないことは、ＡとＢが互いに孤立であることを表します。 この場合も５カ国ありますがＡとＢが互いに孤立なので、４色で塗り分けら れます。 平面上の５カ国が互いに孤立することなく接触しあうことは不可能です。 なぜなら、平面上で閉じられた線内の国から外に向かって、この線に交わる ことなく線を引き出すことはできないからです。 これは、ＡからＢに向かって、すでに引かれている線に交わることなく線を 引けないという意味です。 このことは、ＡとＢは孤立の関係から接触の関係に移行できないことを意味 します。 つまりＡとＢは同色であり、異色にはなれないことを意味しています。 この制限により国々の色分けが４色でできることになります。 したがって、平面上の国々はすべて４色で色分けできます。 以上です。 ―――――――――――――――――――――――――――――――――― 私のこの説明は、間違っているかもしれません。 間違い探しは楽しいことです。間違いを探してみてください。 もしかしたら、あなたが正解を見つけ出すかもしれません。 平面上では４色で色分けできますが、立体の色分けは何色なのでしょうか。 私はこの問題にも興味はありますが、解けません。これはコンピュータでし か解けない問題かもしれません。(無限の数の色になるのかな。大きさや形 によって異なるのかな。立体パズルが売られています。) 平面上の５カ国の内の１国が、周りを閉じられた線で囲まれています。この 線に交わらずに線の外の国へ線を引くには、平面の上の空間に橋をかければ 解決します。でも、これは平面内で考えるという規則に違反します。 ･･････････ ： ：←空間にかけた橋 ＿：＿＿＿ ： ／＿：＿ ＼ ： ｜／ ： ＼ ＼： Ｅ――Ｄ――Ａ――Ｃ――Ｂ ／｜＼＿＿＿／ ／ ／ ｜ ＼＿＿＿＿＿／ ／ ＼＿＿＿＿＿＿＿＿＿／ これは、立体の色分けを考えるときに役立つかもしれません。 gyo 先頭へ戻ります。