4色定理についてですが、引っかかるところがあります。
現在はコンピュータで量的な証明がなされていると聞きますが、グラフ理論で証明されたという話は聞きません。
私の中ではグラフ理論で簡単に説明できるのではないかな、という甘い考えがあります(内容は下記に記載しました)。
ただ、こうした考えは以前もたくさんあって否定されているのだと思います。そこで何が悪いのかを教えて頂きたいのです。
納得できる回答が無かった場合は、私は私の考えが正しいんじゃないかと思っているので、私の胸の内で「私の考えで正しいのだ」と自己完結しようと思います。
この質問の内容は、「下記のようなグラフ理論の考え方で5色の塗りわけは無理=4色の塗りわけで事足りるので、二次元における地図の塗りわけは4色が最大値であり、4色でことたりる」ということの説明ではどこか不足があるのだろう、その不備を教えて頂ければ、というのが論旨となります。
内容は極めて簡単なのですが、文章が少々難しくなってしまいました。ですが、どなたかお付き合い頂ける方、この論旨の問題点をご存知の方、あるいは少しでもこうではないかとおっしゃって頂ける方がいらっしゃいましたら教えて下さい。
尚、万が一の可能性として「こりゃ世紀の大発見也」みたいなこともあるかもしれませんが(とは言いつつも全く期待してません。まあ、今この文章を書きながら自分自身に笑っていますが)、賛同頂ける方、欠点は無い、と言う方もいらっしゃいましたら教えて下さい。
しかし私自身モヤモヤしているのも事実なので、これが正しいのか穴があるのかを教えて頂きたいのです。
<序論>
例えば、二次元平面に描かれた任意数のノードとエッジで観察するとき、地図でのいわゆる4色定理の観点から見ると、ノードが国、エッジが国境になります。
もともと4色問題の根源は、地図での色塗りの組み合わせにおいて、本当に必要な色の数として4色が最大値なのか、5色必要なパターンは無いのか、という点が論点であると私は考えています。
つまり、これをグラフ理論から見れば、
・塗りわけが必要なのは、ノードがエッジによって接続されているケース
であり、4色が必要なものは
・4つのノードが「全て」4つともエッジによって接続されているケース
を想定するものです。
そして5色が必要なものは
・5つのノードが「全て」5つともエッジによって接続されているケース
を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は4ということになります。
<前提などの説明>
まず根源的な前提として、エッジを延ばすことのできる条件とはなんでしょうか?
それはノード間において遮蔽物が無いことです。遮蔽物が無いという状況はどんな状況でしょうか。
逆に言えば遮蔽物とは何か、ということなのですが、この地図塗りわけの問題をグラフ理論に適用すると、閉路グラフの「内部」にノードAを一つプロットし、「外部」にノードBをプロットします。
今回は地図塗りわけの問題をグラフ問題に展開していますので、エッジ間の交差はありません。
ですので、閉路グラフの内と外にプロットされているノードAとBは直接エッジで接続することはできない、というのが前提となります。
三次元での考えではこれらは無視できるのですが、今回は地図塗りわけがお題となるので、二次元平面上での問題となります。
<本論>
序文にも書きましたが、
・5つのノードが「全て」5つともエッジによって接続されているケース
を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は4ということになります。
まず一つずつ考えて生きます。
1.2つのノードの場合
→存在するノードが互いに全てエッジによって接続されている。
○-○を想像して頂ければOKです。
この場合2色必要になります。
2.3つのノードの場合
→存在するノードが互いに全てエッジによって接続されている。
正三角形の頂点に○をくっつけた図を想像して頂ければOKです。
この場合3色必要になります。
3.4つのノードの場合
→存在するノードが互いに全てエッジによって接続されている。
正三角形の頂点に○をくっつけて、その中央に○を描き、
それらが全て互いに接続されている図を想像して頂ければOKです。
4つのノードが互いに全てエッジによって接続されているケースはトポロジー的に必ずこのようになると思います。
この場合4色必要になります。
4.5つのノードの場合
さて、それでは5つのノードが互いに全てエッジで接続されるケースを考えてみましょう。
実は上記3.「4つのノードの場合」で閉路グラフが構成されており、どこに5つ目のノードをプロットしようとも、その閉路の中の全てのノードにエッジを届かせることはできません。
ここでは前提として頂点A、B、Cからなる正三角形と、その中央に位置する点D、そしてこれらの点をノードとし、全て互いにエッジで接続しあったグラフを用います。
そして5つ目の点Eを任意の位置にプロットし、ノードのABCDEが5つ全て互いにエッジで接続できたなら、地図の塗りわけとして5色必要、こうしたモデルがグラフでできないと証明できたなら5つは必要でなく、地図の塗りわけとしての最大必要色数は4色ということになります。
点Eを置く位置としてはグラフ図中の任意の位置となりますが、これを分類すると
(1)三角形ABCの外に点Eを置く場合
(2)三角形ABDの内側に点Eを置く場合
(3)三角形ACDの内側に点Eを置く場合
(4)三角形BCDの内側に点Eを置く場合
の4種に分けられると思います。
これを一つずつ見ていきましょう。
(1)三角形ABCの外に点Eを置く場合
点Eは、三角形ABCに構成される閉塞グラフの内側にある点Dにエッジが届かない。
よって点Eのこの位置のプロットでは、ノードのABCDEが5つ全て互いにエッジで接続できない。
(2)三角形ABDの内側に点Eを置く場合
点Eは、三角形ABDに構成される閉塞グラフの外側にある点Cにエッジが届かない。
よって点Eのこの位置のプロットでは、ノードのABCDEが5つ全て互いにエッジで接続できない。
(3)三角形ACDの内側に点Eを置く場合
点Eは、三角形ACDに構成される閉塞グラフの外側にある点Bにエッジが届かない。
よって点Eのこの位置のプロットでは、ノードのABCDEが5つ全て互いにエッジで接続できない。
(4)三角形BCDの内側に点Eを置く場合
点Eは、三角形BCDに構成される閉塞グラフの外側にある点Aにエッジが届かない。
よって点Eのこの位置のプロットでは、ノードのABCDEが5つ全て互いにエッジで接続できない。
以上のことからノードのABCDEが5つ全て互いにエッジで接続できるグラフは存在しない。よって地図塗りわけに対しての必要な最大の色数は4色である。
尚、数学的哲理的考察としては、任意ノード数で、互いに全てのノードをエッジで接続するケースを考えた場合、三つのノードで閉路グラフが形成され、四つ目のノードで「その閉路グラフの内側か外側に」プロットされてしまう。更に上記の例で言えばこの四つ目のノード自体をプロットすることにより、閉路グラフがABC、ABD、ACD、BCDと四つ形成されてしまう。そしてそこから追加のノード点Eをどこに打とうとも、閉路グラフの内側に点Eを打てばその外側に、閉路グラフの外側に点Eを打てばその内側に、自分とは異なるノードが存在するので、点Eからそこのノードに到達するエッジを延ばすことはできない。
となります。
実は、数年前もここで同じような質問をさせて頂いたことはあります。ただ、その時に納得できたように思われたのですが、やはり何か私の心の中でモヤモヤしているものがあったので、再度の質問をさせて頂くことにしました。
どなたかご教授頂ける方がいらっしゃいましたら、宜しくお願い致します。
A 回答 (6件)
- 最新から表示
- 回答順に表示
No.6
- 回答日時:
以下の例では
どの5つのノードも互いに接続されているケースが存在しませんが、
ノードの塗りわけには5色必要です。
ただし局所的にどの5つのノードを取り出しても
エッジが交差しないように2次元展開可能ですが、
2次元の4色定理は証明されているので、
全体的にはエッジが交差して2次元展開不可能です。
どの5つのノードも互いに接続されているケースが存在しないからといって、
エッジが交差しないように2次元展開可能とは限りません。
例)
ノード:
A,B,C,D,E,F,G,H,I
エッジ:
A-B,A-C,A-D,B-C,B-D,C-D,
B-E,C-E,D-E,
A-F,B-F,C-F,
C-G,D-G,E-G,
A-H,B-H,F-H,
E-I,G-I,F-I,H-I
とすると
A,B,C,Dが4つとも接続されているから
A=1
B=2
C=3
D=4
とするとEはB=2,C=3,D=4と接続されているから
E=1
FはA=1,B=2,C=3と接続されているから
F=4
GはC=3,D=4,E=1と接続されているから
G=2
HはA=1,B=2,F=4と接続されているから
H=3
(EとFは接続していない、GとHも接続していないけれども)
IはE=1,F=4,G=2,H=3と接続されているから
I=5
となって
5色必要となります。
No.5
- 回答日時:
No.3です。
>>・しかし、Nの数が5よりも十分に大きいN個のノードを用意し、そこにランダムにエッジで接続した巨大なグラフを考えたとき、その中の組み合わせにおいて「5つのノードが全て互いに接続しあっている部分が存在しない」=「5色必要な地図が存在しない」という証明にはなりえない。
5角形の中心と各頂点を結ぶような国の集まりを含む地図が有って、その5カ国を4つの色を使って塗り分けているとします。
そんな地図は存在しえないとするのであれば、その証明が必要です。
中心の点を拡大して5角形とし、周りの5カ国と接続させるとします。(ノードを1個増やす事に相当します)
私が、3色の場合の反例に出した配置ですね。
このままだと、真ん中の国を塗るのに5番目の色が必要になってしまいます。
この地図を4色で塗り分けるのにはどうすればいいのでしょう?
これは、ケンペがこの問題の解決を持って4色問題の解決としたものですが、ヒーウッドの反例によって否定されています。
4角形の国を4色からなる4カ国が取り囲んでいる場合についてはケンペにより解決されています。
http://d.hatena.ne.jp/Polyhedron/20100408/127073 …
ケンペの証明とヒーウッドの反例について調べてみるのが良いでしょう。
4色問題の解説本としては「四色問題」{ロビン・ウィルソン (著), 茂木 健一郎 (翻訳)}が出版されています。
http://www.amazon.co.jp/%E5%9B%9B%E8%89%B2%E5%95 …
ロビン・ウィルソンの本より先にブルーバックスから「四色問題」{一松 信(著) 1978年}が出版されています。
この本の付録にはアッペルとハーケンが証明に使用した1834個の可約配置を示す [グラフ] が示されています。
可約配置:その国(または国々)を除く地図が4色で塗り分け出来るならば、その国(国々)を追加した全体が4色で塗り分け出来るような国(国々)
自明な可約配置としては、3カ国以下の国で囲まれた国が相当する。
自明でない可約配置を最初に見つけたのはバーコフで、その配置は「バーコフのダイヤモンド」と呼ばれている。
http://ohkawa.cc.it-hiroshima.ac.jp/www32.ocn.ne …
No.4
- 回答日時:
>・しかし、Nの数が5よりも十分に大きいN個のノードを用意し、そこにランダムにエッジで接続した巨大なグラフを考えたとき、その中の組み合わせにおいて「5つのノードが全て互いに接続しあっている部分が存在しない」=「5色必要な地図が存在しない」という証明にはなりえない。
>というように読めましたが合っていますでしょうか。
はい、そのとおりです。
>つまりは私が書いた5個のノードだけではなく、巨大なグラフにおいてはその辺縁系までもが相互作用しあって最終的に「5つのノードが全て接続しうるようなケースが存在しない」という証明たりえていない、
>というように理解しましたが、合っていますでしょうか。
いいえ、違います。
「5つのノードが全て接続しうるようなケースが存在しない」ことが証明できていないと言っているのではありません。
そうではなくて、
局所的には4色で十分だとしても、地図全体では5色必要かもしれないということです。
#3さんも同じようなことを書かれていますが、
「局所的に3色で十分なら、全体でも3色で十分」に反例(1つの国の周りに5つの国が隣接)があるのに、
どうして「局所的に4色で十分なら、全体でも4色で十分」と言えるのかということです。
3色のときの反例をどのように解釈しているのでしょうか?
No.3
- 回答日時:
4色定理の証明にグラフ理論は使われていますよ。
と言うか、グラフ理論は4色定理の証明に不可欠です。
>・5つのノードが「全て」5つともエッジによって接続されているケース
>を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は4ということになります。
平面上に5つのノードが「全て」5つともエッジによって接続されているケースが存在しない事は多面体についてのオイラーの定理を利用すれば簡単に証明できます。
地図の外側全体を一つの国と考えて球面に張り付ければ多面体と等価になります。
5つのノードが「全て」5つともエッジによって接続されているケースはオイラーの定理で簡単に確かめられます。
これが証明になるのであれば、100年以上続く難問題になる事は無かったでしょう。
この証明で得られるのは5色あれば塗り分けられると言う事だけです。
5つのノードが「全て」5つともエッジによって接続されているケースを言いかえると、5カ国の全てがお互いに接触している地図と言えます。
この様な5カ国が無い地図が4色で塗り分けられるのであれば、お互いに接触する4カ国が無い地図は3色で塗り分けられる事になりますが、お互いに接触する4カ国が無い地図で4色を必要とする地図は有ります。
例えば、5角形の国を5つの国が取り囲んでいる地図です。
もし、お互いに接触する5カ国が無い地図は4色で塗り分けられる事を主張するのであれば、なぜ4カ国の場合は駄目で、5カ国の場合は良いのかを証明する必要があるでしょう。
No.2
- 回答日時:
>5つのノードが全て5つともエッジによって接続されているケースが存在しない ⇒ 5色必要なケースもあるかもしれない。
>この具体例も思い浮かばないのでこちらも分かれば教えて下さい。
実際に4色定理は証明されているわけですから、そんな例は存在しないでしょう。
(もし存在したら定理が間違っていることになってしまう)
5つの国が全て互いに同時に接しているケースが存在しないのは誰にも異論はないと思います。
しかし、局所的に4色で塗れるということと、全体でも4色で塗れるということは別問題です。
例えば、
ある地図があって、どの4つの国を見ても4つの国が全て互いに同時に接しているケースはない。
(つまり、局所的には3色で塗り分けられる)
この地図全体を3色で塗り分けることができるか。
この場合、4色必要になる地図はすぐ見つかると思います。
これと同じように、
ある地図があって、どの5つの国を見ても5つの国が全て互いに同時に接しているケースはない。
この地図は4色で塗り分けられるか。
としたとき、5色必要な地図が存在しないとどうして言い切れるでしょうか?
再度の回答ありがとうございます。
さて、私の頭は「命題の修辞レトリックがよく分からないからもう納得しちゃえよ」とギブアップ宣言の旗を揚げそうになっているのですが、いやいやここはきちんとチャレンジして行こうと思います。
申し訳ありませんが、お付き合いのほど宜しくお願いします。
> 実際に4色定理は証明されているわけですから、そんな例は存在しないでしょう。
> (もし存在したら定理が間違っていることになってしまう)
了解です。
若干補足する必要がありますが、私としましては「4色定理があるので、この問題は解決したんだね」というスタンスを取っていません。アメリカでの量的な解で解決がはかられたなら、グラフ理論での哲理的解決もできるだろう、それがなされていないのでやってみたいが、ひょっとしたら私の考えと同じ考えをしていた人がいて、どこかでNGになっているかもしれない。どこがNGなのかを知りたいというのがこの質問の趣旨です。
解や結論ありきで論じたいのではなく、哲理的な考えとして普遍的に通用するか否かの思考にチャレンジしたいのです。
そして心の奥底に、「願わくば『4色問題』における解を量的解ではなく、グラフにおける理論的解によって到達したい」という願望が恥ずかしながら少しだけあります。
宜しくお願いします。
さて、
>5つの国が全て互いに同時に接しているケースが存在しないのは誰にも異論はないと思います。
これはOKなのですね。
しかし、
>ある地図があって、どの5つの国を見ても5つの国が全て互いに同時に接しているケースはない。
>この地図は4色で塗り分けられるか。
>
>としたとき、5色必要な地図が存在しないとどうして言い切れるでしょうか?
回答を読んで私なりに整理したのですが、
・私の説明したものはあくまでノードが最高で5つという限定された局所的な理論である。
これはこれで正しい。
・しかし、Nの数が5よりも十分に大きいN個のノードを用意し、そこにランダムにエッジで接続した巨大なグラフを考えたとき、その中の組み合わせにおいて「5つのノードが全て互いに接続しあっている部分が存在しない」=「5色必要な地図が存在しない」という証明にはなりえない。
というように読めましたが合っていますでしょうか。
つまりは私が書いた5個のノードだけではなく、巨大なグラフにおいてはその辺縁系までもが相互作用しあって最終的に「5つのノードが全て接続しうるようなケースが存在しない」という証明たりえていない、というように理解しましたが、合っていますでしょうか。
しかし、まだ疑問に思います。
塗りわけというのは、国と国が国境を接しているとき、その同時接続数のケースが塗りわけの数になります。今回の場合で言うと、グラフに展開できるということです。
グラフに展開できるということは、仮に巨大なグラフがあって互いに5つ同時に接続しているノード群が見つけられなければ証明完了ということになり、それは巨大ノード群Nからサンプルのノード群nを抽出しても結果は一緒ではないでしょうか。
仮に相互作用して最終的に5つのノードが全て互いに接続しあっているノード群が見つかったとしましょう。しかし、これらはエッジが交差可能なグラフ群ではなく、あくまでエッジが交差不可であるグラフ群からの抽出でありますので、そのノードの抽出数は互いに隣接し合う5つのノードだけで良いはずです。
接続しあうノードが回りまわって最終的に5色必要になる可能性が捨てきれないという考えも簡単に思いつきはするのですが、ただ、それも二次元平面状に展開し、エッジが交差しない条件でのグラフの展開から見れば、5色必要という理論は直接的に隣接していなければなりません。エッジが交差可能であったり、あるいは3以上のn次元だったり、トーラスであったりすればこれも考慮しなければならないと思うのですが、今回は「二次元平面状に展開し、エッジが交差しない」という条件が付与されます。即ちn色での塗りわけが必要というのは巨大グラフからのノードサンプル抽出であっても、n個の同時「隣接」が必要なのであり、巨大グラフ全体での相互作用を考えなくとも、サンプルを抽出した後の考察で事足りると思うのです。
この考え方はどの辺がダメなのでしょうか?
No.1
- 回答日時:
>そして5色が必要なものは
>・5つのノードが「全て」5つともエッジによって接続されているケース
>を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は4ということになります。
サラッと流していますが、問題はここではないですか?
確かに
5つのノードが全て5つともエッジによって接続されているケースがある ⇒ 5色必要である
は正しいですが、その逆、
5つのノードが全て5つともエッジによって接続されているケースが存在しない ⇒ 5色必要ではない
がどうして正しいと言えるのでしょうか?
早速の回答ありがとうございます。
うーん・・・。確かにここが煮込めきれていない部分かもしれません。
というよりここをちょっと精査させて下さい。
命題の裏は正しいと言い切れない、ということですよね。
そうすると、
・5つのノードが全て5つともエッジによって接続されているケースが存在しない ⇒ 5色必要ではない
というケースは正しいとも言い切れないし、正しくないとも言い切れない、この二つのケースが存在するという理解であってますでしょうか?
つまりは、
「5つのノードが全て5つともエッジによって接続されているケースが存在しな」くとも、
「5色必要である」ケースの存在がありうるということですよね。
一方、「5つのノードが全て5つともエッジによって接続されているケースが存在しな」い場合には、
「5色での塗りわけは不要である」ケースについては私が質問文で主張している通りです。
ここで少し説明させて下さい。
そもそもグラフにおけるノードの存在自体が、地図における色分けの必要があるという形になります。
もう少し具体的に言いますと、地図上での国がグラフでのノード、地図上での国境がグラフでのエッジになります。国境を接している場合(ノード間にエッジがある場合)は、国と国の区別をつけるために色分けが必要になります。つまり無数に広がるランダムのグラフから任意に抽出したグラフのうち、N個のノードが互いに全てエッジによってつながっている場合についてはN色の塗りわけが必要となります。
これに従うと、「5つのノードが全て5つともエッジによって接続されているケースが存在しな」い場合は、これはすなわち「5色で塗り分けられない」ということにつながると思うのですがいかがでしょうか。
もう少し具体的に言うと、ノード=国、エッジ=国境ですので、国境を接している国は塗り分ける必要があります。
4つの国が全て互いに同時に接しているのであれば、4つの塗りわけが必要になります。
5つの国が全て互いに同時に接しているのであれば、5つの塗りわけが必要になりますが、5つの国が全て互いに同時に接しているケースは、質問文に書いた通り、トポロジー上、グラフ理論上、私は存在しないと考えています。
回答に頂いた
「「5つのノードが全て5つともエッジによって接続されているケースが存在しない ⇒ 5色必要ではない」がどうして正しいと言えるのでしょうか?」
という文章を勝手に変えさせて頂きますと、
「「5つのノードが全て5つともエッジによって接続されているケースが存在しない ⇒ 5色必要ではない」が正しいと言い切れない」
「「5つのノードが全て5つともエッジによって接続されているケースが存在しない ⇒ 5色必要ではない」が正しくないケースもありうる」
ということになると思います。
それでは正しくないケースは具体的にどんなものだろう、と考えてみるのですが思い浮かびません。そもそも「5つのノードが全て5つともエッジによって接続されているケースが存在しない ⇒ 『5色で塗り分けることが不可能である』=「5色必要ではない」=「二次平面上では塗りわけ最大色数は4色でMAX」」だと思っています。
二次元平面上において互いに全てエッジ接続する閉路グラフを構成するノードの最小数は3であり、閉路の内と外でエッジ接続の疎外が出る数が+2。つまり、5個のノードでは全て互いにエッジ接続ができない。そして全て互いにエッジ接続が可能なのが、閉路グラフを構成するノードの最小数の3と、閉路グラフの内側、もしくは外側にプロットされるノードの+1の計4。
よって全て互いにエッジ接続可能なノード数の上限は4である。
そして5つのノードを置いたとき、全て互いにエッジ接続可能なグラフ構成は存在しない。
これをグラフから地図に置き換えた場合、4色の塗りわけだけでよく、5色目は必要無い。
これではダメでしょうか?
5つのノードが全て5つともエッジによって接続されているケースが存在しない ⇒ 5色必要なケースもあるかもしれない。
この具体例も思い浮かばないのでこちらも分かれば教えて下さい。
<<追記>>
前提条件に次のものを加えさせて下さい。
「互いに全てエッジ接続する閉路グラフ」と書きましたが、閉路じゃないケースも考える必要があるんじゃないか、という回答もあるかと思います。
ただ、「互いに全てエッジ接続するグラフ」については、ノード数が3を超えたとき、これが必然的に閉路構成となることを前提としています。
宜しくお願い致します。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
CPUの考え方を教えてください ...
-
ルート要素ノードが2個ある場合?
-
あるノードリストに、特定の名...
-
SNMP リンクダウンとノードダ...
-
双方向リストの関数
-
TreeViewの再表示のちらつきを...
-
同じタグ名の項目取得
-
ノード数とは?
-
昔Winnyってありましたけど、あ...
-
XML::LibXMLのfindnodes()で、...
-
最長経路探索
-
ToolStripMenuItemの選択(VB)
-
C#でtreeviewの指定ノードを選...
-
複数のマックPCによる数値計算...
-
インターネットって、どうやっ...
-
ツリービューのノードをダブル...
-
カウントアップ
-
2分探索木の高さを求めるプロ...
-
アローダイアグラムの描画について
-
XML文書の指定した属性値を持つ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
CPUの考え方を教えてください ...
-
SNMP リンクダウンとノードダ...
-
同じタグ名の項目取得
-
昔Winnyってありましたけど、あ...
-
コンテキストメニュークリック...
-
ルート要素ノードが2個ある場合?
-
マスターノード
-
複数のマックPCによる数値計算...
-
あるノードリストに、特定の名...
-
TreeView の初期表示について
-
TreeViewの再表示のちらつきを...
-
ツリービューのノードをダブル...
-
C# TreeView 効率良いノード追...
-
ノード数とは?
-
XML文書の指定した属性値を持つ...
-
C#のツリービューでツリーノー...
-
VB6.0でDOMを使用して...
-
TreeViewで複数ノードの選択は...
-
ノードとは
-
VisualBasic.net(2008) ツリー...
おすすめ情報