- 締切済み
４色定理はなぜグラフ理論で証明できないのでしょうか
４色定理についてですが、引っかかるところがあります。 現在はコンピュータで量的な証明がなされていると聞きますが、グラフ理論で証明されたという話は聞きません。 私の中ではグラフ理論で簡単に説明できるのではないかな、という甘い考えがあります（内容は下記に記載しました）。 ただ、こうした考えは以前もたくさんあって否定されているのだと思います。そこで何が悪いのかを教えて頂きたいのです。 納得できる回答が無かった場合は、私は私の考えが正しいんじゃないかと思っているので、私の胸の内で「私の考えで正しいのだ」と自己完結しようと思います。 この質問の内容は、「下記のようなグラフ理論の考え方で5色の塗りわけは無理＝４色の塗りわけで事足りるので、二次元における地図の塗りわけは４色が最大値であり、４色でことたりる」ということの説明ではどこか不足があるのだろう、その不備を教えて頂ければ、というのが論旨となります。 内容は極めて簡単なのですが、文章が少々難しくなってしまいました。ですが、どなたかお付き合い頂ける方、この論旨の問題点をご存知の方、あるいは少しでもこうではないかとおっしゃって頂ける方がいらっしゃいましたら教えて下さい。 尚、万が一の可能性として「こりゃ世紀の大発見也」みたいなこともあるかもしれませんが（とは言いつつも全く期待してません。まあ、今この文章を書きながら自分自身に笑っていますが）、賛同頂ける方、欠点は無い、と言う方もいらっしゃいましたら教えて下さい。 しかし私自身モヤモヤしているのも事実なので、これが正しいのか穴があるのかを教えて頂きたいのです。 ＜序論＞ 例えば、二次元平面に描かれた任意数のノードとエッジで観察するとき、地図でのいわゆる４色定理の観点から見ると、ノードが国、エッジが国境になります。 もともと４色問題の根源は、地図での色塗りの組み合わせにおいて、本当に必要な色の数として４色が最大値なのか、５色必要なパターンは無いのか、という点が論点であると私は考えています。 つまり、これをグラフ理論から見れば、 ・塗りわけが必要なのは、ノードがエッジによって接続されているケース であり、４色が必要なものは ・４つのノードが「全て」４つともエッジによって接続されているケース を想定するものです。 そして５色が必要なものは ・５つのノードが「全て」５つともエッジによって接続されているケース を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は４ということになります。 ＜前提などの説明＞ まず根源的な前提として、エッジを延ばすことのできる条件とはなんでしょうか？ それはノード間において遮蔽物が無いことです。遮蔽物が無いという状況はどんな状況でしょうか。 逆に言えば遮蔽物とは何か、ということなのですが、この地図塗りわけの問題をグラフ理論に適用すると、閉路グラフの「内部」にノードＡを一つプロットし、「外部」にノードＢをプロットします。 今回は地図塗りわけの問題をグラフ問題に展開していますので、エッジ間の交差はありません。 ですので、閉路グラフの内と外にプロットされているノードＡとＢは直接エッジで接続することはできない、というのが前提となります。 三次元での考えではこれらは無視できるのですが、今回は地図塗りわけがお題となるので、二次元平面上での問題となります。 ＜本論＞ 序文にも書きましたが、 ・５つのノードが「全て」５つともエッジによって接続されているケース を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は４ということになります。 まず一つずつ考えて生きます。 １．２つのノードの場合 →存在するノードが互いに全てエッジによって接続されている。 ○－○を想像して頂ければＯＫです。 この場合２色必要になります。 ２．３つのノードの場合 →存在するノードが互いに全てエッジによって接続されている。 正三角形の頂点に○をくっつけた図を想像して頂ければＯＫです。 この場合３色必要になります。 ３．４つのノードの場合 →存在するノードが互いに全てエッジによって接続されている。 正三角形の頂点に○をくっつけて、その中央に○を描き、 それらが全て互いに接続されている図を想像して頂ければＯＫです。 ４つのノードが互いに全てエッジによって接続されているケースはトポロジー的に必ずこのようになると思います。 この場合４色必要になります。 ４．５つのノードの場合 さて、それでは５つのノードが互いに全てエッジで接続されるケースを考えてみましょう。 実は上記３．「４つのノードの場合」で閉路グラフが構成されており、どこに５つ目のノードをプロットしようとも、その閉路の中の全てのノードにエッジを届かせることはできません。 ここでは前提として頂点Ａ、Ｂ、Ｃからなる正三角形と、その中央に位置する点Ｄ、そしてこれらの点をノードとし、全て互いにエッジで接続しあったグラフを用います。 そして５つ目の点Ｅを任意の位置にプロットし、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できたなら、地図の塗りわけとして５色必要、こうしたモデルがグラフでできないと証明できたなら５つは必要でなく、地図の塗りわけとしての最大必要色数は４色ということになります。 点Ｅを置く位置としてはグラフ図中の任意の位置となりますが、これを分類すると （１）三角形ＡＢＣの外に点Ｅを置く場合 （２）三角形ＡＢDの内側に点Ｅを置く場合 （３）三角形ＡCDの内側に点Ｅを置く場合 （４）三角形BCDの内側に点Ｅを置く場合 の４種に分けられると思います。 これを一つずつ見ていきましょう。 （１）三角形ＡＢＣの外に点Ｅを置く場合 点Ｅは、三角形ＡＢＣに構成される閉塞グラフの内側にある点Ｄにエッジが届かない。 よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。 （２）三角形ＡＢDの内側に点Ｅを置く場合 点Ｅは、三角形ＡＢＤに構成される閉塞グラフの外側にある点Ｃにエッジが届かない。 よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。 （３）三角形ＡCDの内側に点Ｅを置く場合 点Ｅは、三角形ＡＣＤに構成される閉塞グラフの外側にある点Ｂにエッジが届かない。 よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。 （４）三角形BCDの内側に点Ｅを置く場合 点Ｅは、三角形BＣＤに構成される閉塞グラフの外側にある点Ａにエッジが届かない。 よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。 以上のことからノードのＡＢＣＤＥが５つ全て互いにエッジで接続できるグラフは存在しない。よって地図塗りわけに対しての必要な最大の色数は４色である。 尚、数学的哲理的考察としては、任意ノード数で、互いに全てのノードをエッジで接続するケースを考えた場合、三つのノードで閉路グラフが形成され、四つ目のノードで「その閉路グラフの内側か外側に」プロットされてしまう。更に上記の例で言えばこの四つ目のノード自体をプロットすることにより、閉路グラフがＡＢＣ、ＡＢＤ、ＡＣＤ、ＢＣＤと四つ形成されてしまう。そしてそこから追加のノード点Ｅをどこに打とうとも、閉路グラフの内側に点Ｅを打てばその外側に、閉路グラフの外側に点Ｅを打てばその内側に、自分とは異なるノードが存在するので、点Ｅからそこのノードに到達するエッジを延ばすことはできない。 となります。 実は、数年前もここで同じような質問をさせて頂いたことはあります。ただ、その時に納得できたように思われたのですが、やはり何か私の心の中でモヤモヤしているものがあったので、再度の質問をさせて頂くことにしました。 どなたかご教授頂ける方がいらっしゃいましたら、宜しくお願い致します。
- みんなの回答 （6）
- 専門家の回答
みんなの回答
- muturajcp
- ベストアンサー率77% (511/658)
- tadys
- ベストアンサー率40% (856/2135)
- nag0720
- ベストアンサー率58% (1093/1860)
- tadys
- ベストアンサー率40% (856/2135)
- nag0720
- ベストアンサー率58% (1093/1860)
- nag0720
- ベストアンサー率58% (1093/1860)
＞そして５色が必要なものは ＞・５つのノードが「全て」５つともエッジによって接続されているケース ＞を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は４ということになります。 サラッと流していますが、問題はここではないですか？ 確かに ５つのノードが全て５つともエッジによって接続されているケースがある ⇒ ５色必要である は正しいですが、その逆、 ５つのノードが全て５つともエッジによって接続されているケースが存在しない ⇒ ５色必要ではない がどうして正しいと言えるのでしょうか？
お礼
早速の回答ありがとうございます。 うーん・・・。確かにここが煮込めきれていない部分かもしれません。 というよりここをちょっと精査させて下さい。 命題の裏は正しいと言い切れない、ということですよね。 そうすると、 ・５つのノードが全て５つともエッジによって接続されているケースが存在しない ⇒ ５色必要ではない というケースは正しいとも言い切れないし、正しくないとも言い切れない、この二つのケースが存在するという理解であってますでしょうか？ つまりは、 「５つのノードが全て５つともエッジによって接続されているケースが存在しな」くとも、 「５色必要である」ケースの存在がありうるということですよね。 一方、「５つのノードが全て５つともエッジによって接続されているケースが存在しな」い場合には、 「５色での塗りわけは不要である」ケースについては私が質問文で主張している通りです。 ここで少し説明させて下さい。 そもそもグラフにおけるノードの存在自体が、地図における色分けの必要があるという形になります。 もう少し具体的に言いますと、地図上での国がグラフでのノード、地図上での国境がグラフでのエッジになります。国境を接している場合（ノード間にエッジがある場合）は、国と国の区別をつけるために色分けが必要になります。つまり無数に広がるランダムのグラフから任意に抽出したグラフのうち、Ｎ個のノードが互いに全てエッジによってつながっている場合についてはＮ色の塗りわけが必要となります。 これに従うと、「５つのノードが全て５つともエッジによって接続されているケースが存在しな」い場合は、これはすなわち「５色で塗り分けられない」ということにつながると思うのですがいかがでしょうか。 もう少し具体的に言うと、ノード＝国、エッジ＝国境ですので、国境を接している国は塗り分ける必要があります。 ４つの国が全て互いに同時に接しているのであれば、４つの塗りわけが必要になります。 ５つの国が全て互いに同時に接しているのであれば、５つの塗りわけが必要になりますが、５つの国が全て互いに同時に接しているケースは、質問文に書いた通り、トポロジー上、グラフ理論上、私は存在しないと考えています。 回答に頂いた 「「５つのノードが全て５つともエッジによって接続されているケースが存在しない ⇒ ５色必要ではない」がどうして正しいと言えるのでしょうか？」 という文章を勝手に変えさせて頂きますと、 「「５つのノードが全て５つともエッジによって接続されているケースが存在しない ⇒ ５色必要ではない」が正しいと言い切れない」 「「５つのノードが全て５つともエッジによって接続されているケースが存在しない ⇒ ５色必要ではない」が正しくないケースもありうる」 ということになると思います。 それでは正しくないケースは具体的にどんなものだろう、と考えてみるのですが思い浮かびません。そもそも「５つのノードが全て５つともエッジによって接続されているケースが存在しない ⇒ 『５色で塗り分けることが不可能である』＝「５色必要ではない」＝「二次平面上では塗りわけ最大色数は４色でＭＡＸ」」だと思っています。 二次元平面上において互いに全てエッジ接続する閉路グラフを構成するノードの最小数は３であり、閉路の内と外でエッジ接続の疎外が出る数が＋２。つまり、５個のノードでは全て互いにエッジ接続ができない。そして全て互いにエッジ接続が可能なのが、閉路グラフを構成するノードの最小数の３と、閉路グラフの内側、もしくは外側にプロットされるノードの＋１の計４。 よって全て互いにエッジ接続可能なノード数の上限は４である。 そして５つのノードを置いたとき、全て互いにエッジ接続可能なグラフ構成は存在しない。 これをグラフから地図に置き換えた場合、４色の塗りわけだけでよく、５色目は必要無い。 これではダメでしょうか？ ５つのノードが全て５つともエッジによって接続されているケースが存在しない ⇒ ５色必要なケースもあるかもしれない。 この具体例も思い浮かばないのでこちらも分かれば教えて下さい。 ＜＜追記＞＞ 前提条件に次のものを加えさせて下さい。 「互いに全てエッジ接続する閉路グラフ」と書きましたが、閉路じゃないケースも考える必要があるんじゃないか、という回答もあるかと思います。 ただ、「互いに全てエッジ接続するグラフ」については、ノード数が３を超えたとき、これが必然的に閉路構成となることを前提としています。 宜しくお願い致します。
お礼
再度の回答ありがとうございます。 さて、私の頭は「命題の修辞レトリックがよく分からないからもう納得しちゃえよ」とギブアップ宣言の旗を揚げそうになっているのですが、いやいやここはきちんとチャレンジして行こうと思います。 申し訳ありませんが、お付き合いのほど宜しくお願いします。 > 実際に４色定理は証明されているわけですから、そんな例は存在しないでしょう。 > （もし存在したら定理が間違っていることになってしまう） 了解です。 若干補足する必要がありますが、私としましては「４色定理があるので、この問題は解決したんだね」というスタンスを取っていません。アメリカでの量的な解で解決がはかられたなら、グラフ理論での哲理的解決もできるだろう、それがなされていないのでやってみたいが、ひょっとしたら私の考えと同じ考えをしていた人がいて、どこかでＮＧになっているかもしれない。どこがＮＧなのかを知りたいというのがこの質問の趣旨です。 解や結論ありきで論じたいのではなく、哲理的な考えとして普遍的に通用するか否かの思考にチャレンジしたいのです。 そして心の奥底に、「願わくば『４色問題』における解を量的解ではなく、グラフにおける理論的解によって到達したい」という願望が恥ずかしながら少しだけあります。 宜しくお願いします。 さて、 >５つの国が全て互いに同時に接しているケースが存在しないのは誰にも異論はないと思います。 これはＯＫなのですね。 しかし、 >ある地図があって、どの５つの国を見ても５つの国が全て互いに同時に接しているケースはない。 >この地図は４色で塗り分けられるか。 > >としたとき、５色必要な地図が存在しないとどうして言い切れるでしょうか？ 回答を読んで私なりに整理したのですが、 ・私の説明したものはあくまでノードが最高で５つという限定された局所的な理論である。 これはこれで正しい。 ・しかし、Ｎの数が５よりも十分に大きいＮ個のノードを用意し、そこにランダムにエッジで接続した巨大なグラフを考えたとき、その中の組み合わせにおいて「５つのノードが全て互いに接続しあっている部分が存在しない」＝「５色必要な地図が存在しない」という証明にはなりえない。 というように読めましたが合っていますでしょうか。 つまりは私が書いた５個のノードだけではなく、巨大なグラフにおいてはその辺縁系までもが相互作用しあって最終的に「５つのノードが全て接続しうるようなケースが存在しない」という証明たりえていない、というように理解しましたが、合っていますでしょうか。 しかし、まだ疑問に思います。 塗りわけというのは、国と国が国境を接しているとき、その同時接続数のケースが塗りわけの数になります。今回の場合で言うと、グラフに展開できるということです。 グラフに展開できるということは、仮に巨大なグラフがあって互いに５つ同時に接続しているノード群が見つけられなければ証明完了ということになり、それは巨大ノード群Ｎからサンプルのノード群ｎを抽出しても結果は一緒ではないでしょうか。 仮に相互作用して最終的に５つのノードが全て互いに接続しあっているノード群が見つかったとしましょう。しかし、これらはエッジが交差可能なグラフ群ではなく、あくまでエッジが交差不可であるグラフ群からの抽出でありますので、そのノードの抽出数は互いに隣接し合う５つのノードだけで良いはずです。 接続しあうノードが回りまわって最終的に５色必要になる可能性が捨てきれないという考えも簡単に思いつきはするのですが、ただ、それも二次元平面状に展開し、エッジが交差しない条件でのグラフの展開から見れば、５色必要という理論は直接的に隣接していなければなりません。エッジが交差可能であったり、あるいは３以上のｎ次元だったり、トーラスであったりすればこれも考慮しなければならないと思うのですが、今回は「二次元平面状に展開し、エッジが交差しない」という条件が付与されます。即ちｎ色での塗りわけが必要というのは巨大グラフからのノードサンプル抽出であっても、ｎ個の同時「隣接」が必要なのであり、巨大グラフ全体での相互作用を考えなくとも、サンプルを抽出した後の考察で事足りると思うのです。 この考え方はどの辺がダメなのでしょうか？