[過去ﾛｸﾞ] ☆四色問題の簡単な証明その３☆ (779ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
644(3): 帰納と類比 2013/02/22(金) 21:33:25.24 AAS
>>642>>643
以前にも書いたがＰ０を抜くと辺が一つ消える。
５集点からＰ０を抜くと回りの６集点が５集点になる。
さらに接合を行うと辺がさらに一つ消える。
不可壁な６集点は４集点となり可約配置になる。
サッカーボールも同様にして６集点が４集点になる。
よって簡単に４彩色可能となる。
645(1): 2013/02/22(金) 21:50:33.22 AAS
>>644
2つのBのうち接合して4集点になるのは必ず1つだけである。
>>642では4集点になることも考慮している。
>(1)A1がC'に隣接している場合: A1とC3を接合すると接合した頂点は
>A', B5(5集点), C', D4に隣接しているので5色目が必要になる。
>(2)A1がD'に隣接している場合: A1とD4を接合すると接合した頂点は
>A'', B2(5集点), C3, D'に隣接しているので5色目が必要になる。
(1)ではB2が4集点になりB5は5集点のままなので、B5(5集点)と
書いているし、
(2)ではB5が4集点になりB2は5集点のままなので、B2(5集点)と
書いている。
646(2): 2013/02/22(金) 21:54:33.78 AAS
>>644
>>642とは別の以前の問題を再度挙げる。
>>593 >>595について具体的な問題にする。
接合を使った証明法が正しいとして、1000頂点のグラフが4彩色可能
であることを示すことにする。
P0を取り除いて接合すると998頂点のグラフが作られ、接合した
頂点の彩色に5色目が必要になったとする。
998頂点のグラフが4彩色可能でないならば矛盾は生じないので、
接合した頂点の彩色に5色目が必要になったことを排除するには
998頂点のグラフが4彩色可能であることを前もって示しておかない
といけない。
>>582によると、帰納法の仮定では
>可約配置のないグラフを４彩色可能と仮定している。
998頂点のグラフが4彩色可能であることを示すのに接合を使うと
998頂点のグラフではケンペ鎖が切断されて5集点が可約であること
が確定する。
よって、998頂点のグラフが4彩色可能かつ可約配置のないグラフで
あることを示すには、接合を使わずにケンペ鎖を切断することなく
4彩色可能であることを示さなければならない。
接合を使わずにケンペ鎖を切断することなく998頂点のグラフが
4彩色可能であることを示すことはできるの？
653: 2013/02/24(日) 13:45:49.09 AAS
>>652
>5集点が可約でないと言い切れない状態でＡＣチェーンかＡＤチェーン
>の接合を行って矛盾が生じるから
接合前のグラフで5集点が可約かどうか分からないのは良いが、
接合後のグラフで5集点が可約でないことが分かっていないと
矛盾が生じることは言えない。
Nが小さいとき接合を使わずに4彩色できることは問題にしていなくて
接合後のグラフで矛盾が生じる場合の実例を知りたいのだが。
>Ｎが小さいときサッカーボールの配色が具体例になる。
サッカーボールの配色を接合した後のグラフは5集点が可約でない
ことを示してくれ。
ついでに書いておくと>>642 >>645よりサッカーボールの配色は
ケンペ鎖がなくても矛盾が生じる(>>644は誤り)。
別の例として、
外部ﾘﾝｸ[html]:mathworld.wolfram.com
Heawoodの例は25頂点のグラフであるが、P0を除いて5頂点を
A, B, C, D, BとしてACおよびADチェーンが存在する彩色を
実際に作ることができる。
接合後は23頂点なので23頂点以下のグラフにおいて5集点が
可約なら接合後に矛盾は生じない。
23頂点以下のグラフは5集点が可約でないと証明できるの？
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.026s