私が、グラフ理論で色づけ考えてたら、
思いついたこと。
これは、まさに
四色問題の簡単な証明だとおもう。
新たに、3色を解いた
もしかしてすでに解決済み？
資格取得のためにね・・
グラフ理論に最近触れてみたんだけど
いや・・・データベースとかUMLとかDF図とかマジめんどいが
やらないといけない・・。
素数やモジュロ演算も、暗号技術に出題されるし＾＾；
まず、エッジ（辺）とドット（点）で多様体を構成してると考える。
１辺で、色は２通りに分けることができる。
赤｜青
ってな感じで。
一点から３つの線が放射状にでているとしてどうか？
もちろん色は３色！
並べられる。
１辺に対して、割り当てられる色は・・
青｜緑、赤｜青、緑｜赤
の３通りである。
一点から４つの線が放射状にでているとし、
色はもちろん４種になり、一辺に対して割り当てられる色の
組み合わせは
青｜緑、青｜赤、青｜黄、緑｜赤、緑｜黄、赤｜黄
の６通りである。
こんな感じで、１点からｎ本放射状に出ているとして、
１辺に対する色の組合わせは・・・
n C 2 = n(n-1)/2
となる。
色の数ももちろんｎ色あります。
面もｎ個あります。
１点からでる辺の数は色、辺を囲む面の数に等しいと
わかりました。
逐次色を塗りつぶしていくと・・・
ただ一面だけ色は固定されるので、
ｎ本あると色の選択権は、n-1の組み合わせに限られます。
(n-1)(n-2)/2
となります。
ここで地図を見てみると、１点からは３辺出ているのが
一番最小値です。
例えば、国境や県境を見て
１、海から見て、神奈川と静岡県の中心点で３辺でている。
２、直線に線がでれば、点から出る辺の数は最小３本である。
３、島は除く。端点も除く。（接続境界の点だけを議論している）
４、直線や曲線や単なる直角に点は存在しない。交差したときに点が生まれる。
つまり、ここで言ってるのは辺が交差する点である。
以上は、公理です。
ここまでの議論より、
(n-1)(n-2)/2 ≧ 3
となる。
3なのは、少なくとも点で選択される
色の数は、3通りだからです。
これを解くと
n^2 - 3n - 4 ≧ 0
n ≧ (3±√25)/2
より、
n ≧ 4,-1
ｎは正の整数なので
－１は無いので
よって、
ｎ ≧ ４
少なくとも四色であれば塗りつぶせるわけである。ちなみに、上の右辺値において
3面のうち１面が底抜けとします。
そうなると、3色だけ済むかもしれません！！
やってみてだれか！
まぁ、四色のうち、一色だけ切り取ったということだから
3色になる。
3色になる方法！がなんとか・・・
ひらめいたのでメモしておきます。
(n-1)(n-2)/2 ≧ 2
で解くと3色ですみます。
左辺の2は、少なくとも間に直線だけ入ってれいば良い！
ということなので・・・
以下の図は3色で塗れます。
つまり、領域内を分断できる線を沢山描けばいいだけです
条件として、すべての面が外側につかなければ行けません。
結論として、
海と石川県と福井県でみれば、
海は領域外で、石川県と福井県だけ見ればいいということ。
つまり、色の選択は最小2通りであること。
これを懸念に計算をすることで
3色になる。
ちなみに、節と辺で表すには
で作られる図ならなんでもおｋ
では、内部に面がある場合の3色は分けられるか？
b0,b1,b2・・・は、固定された色で塗りつぶし後である。
○は、ここまで述べてきた点のことである。
点から出ている線が、a1,a2,a3・・・である。
1点にて、中央面b0とbiはただ２つ決定されてしまうので、
残り、n-2となる。
やはり、点から出ている線の数は3本が最小なので
他２つの面に色が決まってしまうと、残った面の色は一通りです。
ai本のとき、色を選択できる組み合わせは・・・
(ai-3)(ai-2)/2 ≧ 1
とすぐに決まる。
これが、b0の ｍ角形 の多角形とすれば・・・
Σ(ai-3)(ai-2)/2 ≧ m
（i=1～m）
ai ≧ 4 であれば、上の不等式は成立する。
周りが4面以上なら、解決できるということ。
最小である、すべてai=3を入れてしまうと
０になってしまいますが、
0/2＝０
と不等式がなりたたない。
これは、ｍ＝０
と置くことで成立する。
つまり、中央面のb0が無い状態を言っているのである。
b0無視して、周りが2の倍数の多角形なら可能であろう。
それを示してるのは、左項の式である。
この理論を元に
ためしに描いてみた、三彩色問題
周りは、4角形の図で、4面がまとわり付いている。
真ん中の緑の3角形は、5面がまとわりついている。
周りの4面 ≧ ４
周りの5面 ≧ ４面 ≧ ３
で三色に分けることができる。
テーマ : 研究発表
ジャンル : 学問・文化・芸術
