４色定理と５人の王子様の解について。

質問

数学の素人なのですが、質問させて下さい。

以前から４色定理に興味があって「四色問題」(ロビン・ウィルソン)という本を一冊購入したのですが、途中で、下記のような簡単な問題が出てきます。

「むかしむかし、インドに大きな国がありました。
　この国の王様が亡くなる時に、5人の王子様に言いました。
　『わたしが死んだら、王国は5人で分けなさい。
　　但し、どの領土も他の４人の領土と境界線(点ではいけない)を
　　共有するように分けなければならない。』
　さて、王国はどのように分ければ良いでしょう」

この解として、本では簡単な図を書いて「ほら、４人までは国土の境界線を互いに共有する事はできる(つまり４色で塗り分けられる)が、５人目はどこに置いても境界線を共有するのは無理でしょう？　（５人以上が国土の境界線を互いに共有する事はできず、共有し合えるのは４人までなので、４色の塗り分けで充分なんですよ）」と分かり易く書いています。

しかし、この後の説明で
「四色定理が正しいのであれば、相互に隣り合う５つの領土を含む地図は無い」が導かれるが、
「相互に隣り合う５つの領土を含む地図が実現できなければ、４色定理は正しい」という事はできない
つまり、この5人の王子の領土問題の解が４色定理の説明とはならない
としています。

上記の説明で前者は理解できるのですが、後者が理解できません。
この本の説明で謂わんとしている所、「５つの領土が実現できない」原因は「４色定理」だけじゃなくて、他にもあるかもしれないよ、という理屈は分かるのですが、どう考えても具体的な他の理由が出てきません。既にそういった解があるのかもしれませんが、ネット上では見つける事ができませんでした。

「相互に隣り合う５つの領土を含む地図が実現できなければ、４色定理は正しい」と言ってしまっていいんじゃないかな、と素人考えで思ってしまうのですが、どうしてこれが誤りなのかがよく分かりません。
ただ単に論理的な命題の問題なのでしょうか。

どなたか分かり易く説明して頂ける方がいらっしゃいましたら、ご教授頂きたく宜しくお願いいたします。

回答No.8

Tacosan · ベストアンサー

あれ? なんとなく表現に齟齬を感じる....
「相互に隣り合う５つの領土を含む地図」って, どういう意味で使ってますか? 「相互に隣り合う 5つの領土＊からなる＊地図」という意味ではない (前者だと 6つ以上の領土があってもよい) ですよね?
で, 確かに「4つの国が」相互に隣り合うことがないのであれば 3色ですみますが, もっと国が多いと 4色必要な状況が現れます. 次のような場合を考えてみましょう:
・国a, b, c はこの順にならんでいる (つまり a と b, b と c は隣り合っているが a と c は離れている)
・国d はこの全てと隣り合っている
・国e は a 及び b と, 国f は b 及び c と隣り合う (どちらも d とは隣り合っていない).
実際に色を割り当てていくと, 3色では足りないことがわかるかと思います.
平面的なグラフについては, 多面体に対する Euler の公式: F - E + V = 2 を使うと (辺の本数) ≦ 3(頂点数) - 6 でなければならないことが知られています. そして, 「相互に隣り合う 5つの領土」をグラフにすると 5個の頂点に対して 10本の辺となりますから, 平面的でないことが簡単にわかります.

お礼

！　理解できました。回答が遅れてすみません。
いろいろとゴタゴタになってしまって申し訳ないです。
a.「相互に隣り合う５つの領土を含む地図」
　→領土は６つ以上
b.「相互に隣り合う 5つの領土＊からなる＊地図」
　→領土は５つのみ
で、no.7の回答迄は、まずbを想定していろいろ言っていたのですが、
aを考える必要があるのですね。

例えば、ノードが100個くらいある任意の平面グラフから
任意にグラフを抽出した時に、
a.「相互に隣り合う５つの領土を含む地図」が無い事を証明したとしても、
即、それが４色で充分とする論拠足りえないという事ですね。

件のインドの王様の話に戻すと、インドの王様が結構女遊びに盛んな方で、
子供が100人いたら４色で国が塗り分けられるかどうか分からないぞ、と。

色で遊んだが為に、色が中々塗り分けられない、という事ですね。

回答No.7

Tacosan

よく考えてみたら, インドの国の話は 4色定理とはあまり関係ないですね.
よく知られた定理で
「グラフが平面的 iff K5 と K3,3 を (マイナーとして) 含まない」
というのがあります. 「国を分割する」というのはおそらく球面上の話と思っていいと思うので, 結果的にこの定理が (ほぼそのまま) 使えます. つまり, どう分割しても「互いに接する 5つの領地」にすることは不可能です. これは 4色定理が正しいかどうかには関係なく成り立ちます.
ちなみに #3 では
「相互に隣り合う５つの領土を含む地図が実現できなければ、４色定理は正しい」
というのが単純には成り立たない, ということを指摘したつもりです. 「相互に隣り合う 4つの領土を含む地図が実現できなければ 3色で塗れる」というのであれば上の「」内もなんとなく正しそうな感じがしますが, 実際にはそうでないので素直に「そうだね」とは言えない, というつもりです.
ちなみに平面的なグラフなら「相互に隣り合う５つの領土を含む地図」は実現できませんから, 実際にはこの条件は何も言っていません.

お礼

お礼が遅れてしまい、すみません。
当初返事に書いていたものも含め、返答致します。
> よく考えてみたら, インドの国の話は 4色定理とはあまり関係ないですね.
えっ？　そうなんですか？　

> よく知られた定理で
> 「グラフが平面的 iff K5 と K3,3 を (マイナーとして) 含まない」
> というのがあります. つまり, どう分割しても「互いに接する 5つの領地」にすることは不可能です.
数式では無いですけれども、自分も独自に発見してました。
が、既に定理であったんですね・・・(当然か)。
なんだかどんどん徒労感が・・・。

> これは 4色定理が正しいかどうかには関係なく成り立ちます.
ここが分からないのです。
私の頭の中では、
1)国が2つある。国境線が全ての国に共有される形で存在する。
　→互いの国を区別する必要があるので2色に分ける。

2)国が3つある。国境線が全ての国に共有される形で存在する。
　→互いの国を区別する必要があるので3色に分ける。

3)国が4つある。国境線が全ての国に共有される形で存在する。
　→互いの国を区別する必要があるので4色に分ける。

4)国が5つある。国境線が全ての国に共有される形で存在できない。
　→仮に国5個で国境線が共有できるならば5色に分ける必要があるが、
　　 実際には共有できないので、5色は必要無い。4色で充分。

という形で「互いに接する 5つの領地」の否定こそが
４色で充分だとする「４色定理」の解だと思っていました。

「４色定理」は、

・どんな地図でも塗りわけには４色で充分だ。
・５色は必要無い。

というのが根本の理論だと思うのです。
私なりにこれを拡張すると、

・塗りわけには国が国境線(点ではない)を接している事。
・ｎカ国が互いに同時に国境線を接している場合は、ｎ色に分けなければならない。
・同時に国境線を共有できる最大のケースは４カ国まで→４色でＯＫ。
・５カ国が国境線を共有する事はできない(少なくとも一つの国は共有できない)→４色でＯＫ。

という感じです。

補足

尚、NO.4の方への回答で、「互いに完全に接しない領地」に
5色が必要な地図のパターンがある可能性があるのでは、と書きましたが、
上記を顧みるに、互いに完全に接してもいない領地同士で
5色が必要な筈もないと考えました。

> ちなみに #3 では
> 「相互に隣り合う５つの領土を含む地図が実現できなければ、４色定理は正しい」
> というのが単純には成り立たない, ということを指摘したつもりです.
> 「相互に隣り合う 4つの領土を含む地図が実現できなければ 3色で塗れる」というのであれば上の「」内もなんとなく正しそうな感じがしますが, 実際にはそうでないので素直に「そうだね」とは言えない, というつもりです.
ううむ・・・分かりませんすみません(汗)。
仮に「相互に隣り合う 4つの領土を含む地図が実現できない」場合、
1)国が2つある。国境線が全ての国に共有される形で存在する。
　→互いの国を区別する必要があるので2色に分ける。

2)国が3つある。国境線が全ての国に共有される形で存在する。
　→互いの国を区別する必要があるので3色に分ける。

3)国が4つある。国境線が全ての国に共有される形で存在できない。
　→仮に国4個で国境線が共有できるならば4色に分ける必要があるが、
　　 実際には共有できないので、4色は必要無い。3色で充分。

となり、私の頭の中(penII)では3色ＯＫ！　とソロバンが弾かれています。

回答No.6

nakaizu

発想はすばらしいと思いますが、残念ながら四色問題はこの方法では証明できません。
問題となるのは国境線が3本しかないというところです。国境線が3本あるために内側の国を外部から遮断し、新たに国を加えたとき国境線が3本以下の状態がつづきます。
しかし、国境線は2本のときや1本のときもあります。この場合は内側の国が外部から遮断されないので、それ以降に国を加えたときには国境線が4本以上となる可能性があります。
国を増やす方法で問題となるのは国境線が3本の場合よりもむしろ2本、1本のときです。

お礼

成る程。No.4の方の回答へのお礼に書いた例のやつですね。
ところで・・・
>発想はすばらしいと思いますが、
ありがとうございます。件の「４色問題」という本ではグラフ理論での説明をやっていなかったので、「もしかしてグラフ理論で説明できるんじゃないか？　」と思い出したのがきっかけでした。
完全に自分オリジナルのつもりでいい気になって調子こいていたのですが、調べ始めると、グラフ理論による考え方が既に沢山あって本当にがっかりしている次第なのであります。
http://ja.wikipedia.org/wiki/%E5%9B%9B%E8%89%B2%E5%AE%9A%E7%90%86
http://www.nii.ac.jp/openhouse/h18/archive/pdf/114.pdf
http://ocw.hokudai.ac.jp/Course/Faculty/Engineering/GraphTheory/2005/page/materials/GraphTheory-2005-Slide-10.pdf

ひとまず肩を落としながら、
(1).できるだけ多く全てのノードにエッジをつけたグラフは４色彩色でＯＫである。
(2).(1)以外の不完全平面グラフ(というのでしょうか？)は４色彩色できるか未確定。
と切り分けして考えてみますね。

回答ありがとうございました。

補足

No.7の方の回答も見ましたが、考え込んで深みにはまってます。
暫く考えさせて下さい。

回答No.5

nakaizu

既に四色に塗られた地図があり、国を追加するときには5色目が必要になることがあります。つまり、国を追加したときに四色で塗るにはそれ以前の国の色も塗り替えないといけないことがあります。
これは色の決めかたが不適切であるからではなく、どの様に色を決めていっても不都合が生じます。
四色を赤、青、黄、緑とします。
A B Cの三ヵ国が互いに接していたとします。たとえばＡの色を赤、Bの色を青、Cの色を黄とします。BとCに接する国Dを追加します。Dが第４の色緑だとすると、ABCDを全て中に含むような環状の国を作ると五番目の色が必要になります。
よってDの色を赤とします。
次にＡ B Ｃ に接する国Eを考えます。実際にはAの国はBCEで囲まれた形になります。
Eは緑にするしかありません。
BCDEに接するような環状の国Fを追加すると、第５の色が必要になります。
これを回避するにはDの色を赤から緑に変更しFを赤にする必要があります。
この様にどのような国の追加にも対応できるように追加する国の色を決めて行くのは不可能です。
参考までに
地球が球なので地図の塗り分けは四色で済んでいますが、もしもドーナツのような形だったら7色必要な場合があります。参考URLで実例が見えます。

参考URL：

http://hp.vector.co.jp/authors/VA010341/donut.html

お礼

丁寧な回答ありがとうございました。
１．
回答に記載して頂いた例についてですが、簡単にＨＰを作成しましたので、
こちらをご覧頂けますでしょうか。
http://sky.geocities.jp/booter_4colors/index.html
↑この平面グラフで説明つくのではないかと思っているのですが・・・。

２．
>地球が球なので地図の塗り分けは四色で済んでいますが、もしもドーナツのような形だったら7色必要な場合があります。参考URLで実例が見えます。
すみません、こちらは知ってました・・・。
ｈ個の穴が開いたトーラス上のオイラーの公式：
（国の数）－（境界線の数）＋（交点の数）＝２－２ｈ
F-E+V=2-2h
や、ヘイウッド予想でしたっけ？
塗りわけに必要な色数＝[1/2(7(1+48h)^-2)]
とかですよね。

なんか、こんな数式を持ち出さなくても４色問題は、自分みたいな人間でも平面グラフで簡単に説明できそうな気がするんですよね。
と甘い事を言ってみたりします。

回答No.4

looker1986

>領土を追加する観点から観測すると、国境線を同時に接する事ができるのは３カ国。

ここが違いますね。追加する観点から考えても、同時に接触できる国は最大で３カ国ではありません。

簡単な例では、すでに４色で塗り分けてある地図の周囲を取り囲むように、国を追加してみればよいです。特に数が多ければ分かりやすいと思います。

もし、あなたの考えが正しいなら、どんな地図でもたちどころに４色で塗り分けることができると思うのですが、実際にやってあみると簡単にはできませんよね？

お礼

！　成程！　分かりました。
パターンがNO.1の方へのお礼に書いたような１パターンのみだけだったからいけないんですね、と解釈しました。

>簡単な例では、すでに４色で塗り分けてある地図の周囲を取り囲むように、国を追加してみればよいです。特に数が多ければ分かりやすいと思います。
・・・これはNo.2の方から紹介して頂いたページでは確かに４色の塗り分けは困難でした。
ただ、No.1の方への回答の様に、理論上は、平面グラフに一つずつノードを一つ追加するごとに『全て』のノードにエッジを追加する事を試みる事を考えた場合、５個目のノード以降は、一つのノードから３本しかエッジが出ない＝４色で充分。という事を書いたつもりでした。

しかし、上記で『全て』と記載しましたが、下記の様なパターンがこの方式には漏れています。
┏━┳━┳━┳━┓
┃あ┃い┃う┃え┃
┣━┻━┻━┻━┫
┃おおおおおおお┃
┗━━━━━━━┛
あ→い→う→え→おの順で領土を追加して行った時、「お」の領土追加時に以前の領土（あ～え）が『全て互いに領土を接していない時』に、４カ国に国境線を接する事ができますね。

このパターンで考える必要がありますか。成る程。
漏れていた事そのものを指摘して頂きました。

回答ありがとうございます！

回答No.3

Tacosan

「相互に隣り合う 4つの領土を含むことがないにもかかわらず, 3色では塗れない」例が作れるので, 「相互に隣り合う 5つの領土を含む地図が実現できなければ 4色定理は正しい」とは, 直ちにはいえませんね.

お礼

？　すみません、ちょっと飛躍されたようで分かりませんでした。
数学が専門じゃないので、話に追いつけないのです。すみません。
１．
>「相互に隣り合う 4つの領土を含むことがないにもかかわらず, 3色では塗れない」例
この例は４色定理で言えば、３色で塗り分けられなくても何にも問題はないんじゃないかな、と素人考え(また・・・)で思ってしまいます。
４色定理に必要な基本理論なのでしょうか。ひとまずは、自分の中で考えたり調べたりして見ます。

２．
率直な感想なのですが、前者例から後者例が捻り出せません。こちらももうちょっと考えてみますね。本題の方は大体解決の方向へ向かっているので、この捻り出し方法が分からない場合は、再度質問を切り直します。

回答ありがとうございました！

回答No.2

nakaizu

四色で塗分けようとすると、隣接していない領土の色も間接的に影響して来るので、隣接する5つの領土がなくても四色で塗れるかは保証できないのです。
参考URLのパズルは四色で塗り分け可能ですが、実際に四色で塗るのは難しいことを体験してみて下さい。

参考URL：

http://www.nikoli.com/ja/take_a_break/four_color_problem/

お礼

成る程、回答ありがとうございます。

No1.での回答のお礼に書いたように、国土を追加する観点から観測した場合に、必ず４色で塗り分けられるような形にならないでしょうか？　
また、現在の数学に照らし合わせて・・・とも書いたのですが、普通に考えれば、これが抜けているでしょ、という見落としがあると思うのです。

紹介されたパズルをやりました。これとは別に以前は他のページで作成されていたパズルをやっていたんですが(JAVAだったかな？　)、こちらも中々出来がいいですね。

回答No.1

BookerL

>　「相互に隣り合う５つの領土を含む地図が実現できなければ、４色定理は正しい」と言ってしまっていいんじゃないかな

　そう簡単にはいきませんね。５つの領土でできなくても、多数個の領土なら５色必要な場合があるかも知れませんから。

　「どれだけ領土があっても４色で塗り分けられる」というのが定理ですから、５つの領土だけで示せても証明にはなりません。

お礼

回答ありがとうございます。
>５つの領土でできなくても、多数個の領土なら５色必要な場合があるかも知れませんから。
成程、６個以上の領土の際には、もしかしたら５色以上必要な可能性がある、という事ですね。
以前、BookerL様から頂いた回答も以前少し考えた事があるのですが、下記のように考えると、何カ国に増えようとも４色で足りてしまうように思うのです。

仮に、アルファベットを領土、領土と領土を結ぶ線を国境線の概念に例える場合、(線と線は交わらない事とします)
■２つの国の場合
　Ａ━Ｂ
■３つの国の場合(上記に領土Ｃを一つ追加し、互いを結ぶ線も追加する)
　Ａ━Ｂ
　┃　┃
　┗━Ｃ
■４つの国の場合(上記に領土Ｄを一つ追加し、互いを結ぶ線も追加する)
　┏Ａ━Ｂ━Ｄ┓
　┃┃　┃　┃┃
　┃┗━Ｃ━┛┃
　┃　　　　　┃
　┗━━━━━┛
↑等幅フォントでご覧下さい。
上記に仮に国土Ｅを任意の場所に設ける際、Ｅをどこに置こうが、国境を接する事ができない国が出てきてしまうのです。
６カ国目以降も同じです。
領土を追加する観点から観測すると、国境線を同時に接する事ができるのは３カ国。追加した領土を入れると４カ国。なので４色で良いのではないかと。
領土を追加される側から観測すると、国境線を同時に接する国は３カ国以上出てきますが、追加した時点で追加された国側からの色分けは済んでしまっているので、４色以上に増えないと思っているのです。

地球を模した球面上にＡＢＣＤの点を打ち、互いに線を結ぶと一番簡単な図では三角錐のような図ができると思いますが、仮にその球面上の図のどこに点Ｅを打とうとも、三カ国で形成された線に阻まれ、残りの一カ国と
国境を接する事ができません。
これを応用して平面に展開すると、同じ事が言えるのではないかと思うのです。増えた領土と同じ点領土ＦＧＨＩ・・・と増えても同じだと思うのです。
というのが、５人の領土問題に対する私なりの解釈なのですが、恐らくこれでも現在の数学に照らし合わせると、間違いやアラがあると思うのです。どこが間違っているか、または不足している部分があるのか教えて頂けないでしょうか？