FC2ブログ

3彩色問題の謎が解けました【完全】

私が、グラフ理論で色づけ考えてたら、
思いついたこと。
これは、まさに四色問題の簡単な証明だとおもう。
新たに、3色を解いた

もしかしてすでに解決済み?


資格取得のためにね・・
グラフ理論に最近触れてみたんだけど
いや・・・データベースとかUMLとかDF図とかマジめんどいが
やらないといけない・・。



素数やモジュロ演算も、暗号技術に出題されるし^^;



まず、エッジ(辺)とドット(点)で多様体を構成してると考える。

1辺で、色は2通りに分けることができる。

赤|青 

ってな感じで。

一点から3つの線が放射状にでているとしてどうか?
もちろん色は3色!
並べられる。
1辺に対して、割り当てられる色は・・
青|緑、赤|青、緑|赤
の3通りである。

一点から4つの線が放射状にでているとし、
色はもちろん4種になり、一辺に対して割り当てられる色の
組み合わせは
青|緑、青|赤、青|黄、緑|赤、緑|黄、赤|黄
の6通りである。


こんな感じで、1点からn本放射状に出ているとして、
1辺に対する色の組合わせは・・・

n C 2 = n(n-1)/2

となる。
色の数ももちろんn色あります。
面もn個あります。
1点からでる辺の数は色、辺を囲む面の数に等しいと
わかりました。




逐次色を塗りつぶしていくと・・・
ただ一面だけ色は固定されるので、

n本あると色の選択権は、n-1の組み合わせに限られます。

(n-1)(n-2)/2

となります。


ここで地図を見てみると、1点からは3辺出ているのが
一番最小値です。

例えば、国境や県境を見て
1、海から見て、神奈川と静岡県の中心点で3辺でている。
2、直線に線がでれば、点から出る辺の数は最小3本である。
3、島は除く。端点も除く。(接続境界の点だけを議論している)
4、直線や曲線や単なる直角に点は存在しない。交差したときに点が生まれる。

つまり、ここで言ってるのは辺が交差する点である。
以上は、公理です。

ここまでの議論より、


(n-1)(n-2)/2 ≧ 3

となる。
3なのは、少なくとも点で選択される
色の数は、3通りだからです。
これを解くと

n^2 - 3n - 4 ≧ 0

n ≧ (3±√25)/2

より、

n ≧ 4,-1

nは正の整数なので
-1は無いので
よって、

n ≧ 4

少なくとも四色であれば塗りつぶせるわけである。



ちなみに、上の右辺値において
3面のうち1面が底抜けとします。

そうなると、3色だけ済むかもしれません!!

やってみてだれか!


まぁ、四色のうち、一色だけ切り取ったということだから
3色になる。


3色になる方法!がなんとか・・・
ひらめいたのでメモしておきます。

(n-1)(n-2)/2 ≧ 2

で解くと3色ですみます。

左辺の2は、少なくとも間に直線だけ入ってれいば良い!
ということなので・・・
以下の図は3色で塗れます。


kukei.png

つまり、領域内を分断できる線を沢山描けばいいだけです
条件として、すべての面が外側につかなければ行けません。


maru.png

結論として、
海と石川県と福井県でみれば、

海は領域外で、石川県と福井県だけ見ればいいということ。

つまり、色の選択は最小2通りであること。
これを懸念に計算をすることで

3色になる。


ちなみに、節と辺で表すには
3syoku.png

で作られる図ならなんでもおk


では、内部に面がある場合の3色は分けられるか?

b0,b1,b2・・・は、固定された色で塗りつぶし後である。
○は、ここまで述べてきた点のことである。
点から出ている線が、a1,a2,a3・・・である。

3syoku2.png

1点にて、中央面b0とbiはただ2つ決定されてしまうので、
残り、n-2となる。

やはり、点から出ている線の数は3本が最小なので
他2つの面に色が決まってしまうと、残った面の色は一通りです。

ai本のとき、色を選択できる組み合わせは・・・


(ai-3)(ai-2)/2 ≧ 1

とすぐに決まる。

これが、b0の m角形 の多角形とすれば・・・

Σ(ai-3)(ai-2)/2 ≧ m
(i=1~m)

ai ≧ 4 であれば、上の不等式は成立する。
周りが4面以上なら、解決できるということ。

最小である、すべてai=3を入れてしまうと
0になってしまいますが、
0/2=0
と不等式がなりたたない。

これは、m=0
と置くことで成立する。

つまり、中央面のb0が無い状態を言っているのである。

b0無視して、周りが2の倍数の多角形なら可能であろう。
それを示してるのは、左項の式である。

この理論を元に
ためしに描いてみた、三彩色問題

tameshi.png

周りは、4角形の図で、4面がまとわり付いている。
真ん中の緑の3角形は、5面がまとわりついている。

周りの4面 ≧ 4
周りの5面 ≧ 4面 ≧ 3

で三色に分けることができる。

スポンサーサイト



テーマ : 研究発表
ジャンル : 学問・文化・芸術

コメントの投稿

非公開コメント

No title

4色問題は、(1)外側に接している部分Aと、外側に接していない内部の部分Bの2種類を考察し、外側に接しているAは3色で塗り分けることができきることを証明する。

(2)内部の部分Bのうち、Aに接しているものB'と、Aに接していない内部Cに分けて、Aに接しているものB'を、Aで使用した2色と使用していない1色で塗り分けられることを証明する。

あとは数学的帰納法でいけるかな?(2)の証明が難しそう。

No title

>一点から4つの線が放射状にでているとし、
>色はもちろん4種になり、一辺に対して割り当てられる色の
>組み合わせは
>青|緑、青|赤、青|黄、緑|赤、緑|黄、赤|黄
>の6通りである。

ここ、4色じゃなくて、2色で塗り分けられるので、その後の

>1点からでる辺の数は色、辺を囲む面の数に等しいと
>わかりました。

これ間違いです。

あと、不等式に単位ついたものと
単位なしのもの並べるのは…^^;

>周りの4面 ≧ 4
>+周りの5面 ≧ 4面 ≧ 3

No title

ネタで言ってんの?

n≧4なんだから、

少なくとも四色であれば塗りつぶせるわけである。
 ↓
少なくとも四色必要である。でしょ?n≦4を示さなきゃ。

4色必要であることは図一つあれば簡単に示せる。

そんな簡単に4色定理が証明できるなら、少なくともド・モルガンがやってるさ。

さらにここで述べられている方法で、3色彩色可能な地図を
生成する事は可能かも知れない(厳密に見てない)が、全ての
地図に対して3色彩色可能であるかを判定する事は明らかに
不可能でしょ?(条件に合わない3色彩色可能な地図は沢山ある)
出来たのだとすれば、明らかに多項式時間判定なのでP=NPになる。

あと知ってると思うが3彩色可能かどうかを多項式時間で判定するアルゴリズムを考えたらフィールズ賞とチューリング賞,ミレミアム懸賞金100万ドルがもらえるよ。(3彩色問題を解決することは、P?=NP問題解決する事と同じ)

論文でも書いてみる?
ぶろぐかんりしゃ

SmartWoods
最近MoEは・・・
一休み

***** ひとこと *****

MoEの後継ともいわれる
Resonance gamez
完全スキルMMOが
気になるところ



********************


↓2016/3/26更新
My MoE









**********

NEWとらっくばっく
あーかいぶ
かてごりー
リンク
ぶろぐないけんさく
RSSふぃーど
おともだちになろ

この人とブロともになる