[過去ﾛｸﾞ] ☆四色問題の簡単な証明その３☆ (779ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
157(1): 2011/04/02(土) 01:26:30.39 AAS
３枝地図において三辺国，四辺国，五辺国は不可避非集合であるといった方が
文章的には分かりやすいだろうか?
244(2): 2011/04/10(日) 12:46:01.39 AAS
五色必要を回避するためには少なくとも片方のチェーンは切れるという主張だが
チェーンを切らずに>>145のように塗り替えられる可能性もないわけではない。
>>145では
B---○---B を A---○---A に替えたが、今度は
B---○---B を D---○---C に替えることを考えてみる
この塗り替えは「絶対に」できることが保証される。
なぜなら、塗り替え前の左のB色はACチェーンに囲まれているので、
左のB色から始まるBDチェーンはDBチェーンに替えられる。
同様に、塗り替え前の右のB色はADチェーンに囲まれているので、
右のB色から始まるBCチェーンはCBチェーンに替えられる。すると、
B---○---B を D---○---C に替えることをができて、
真ん中の○にB色を置けば、周囲の色と衝突しない。
よってチェーンを切らずに四色塗り分け可能が示された。THE END
245: 2011/04/10(日) 13:29:31.39 AAS
>>244
それって、ケンペがこけたのと同じところでこけてないか？
276(3): 2011/05/11(水) 19:06:20.39 AAS
>>274
帰納法の仮定を選べば、矛盾が生じる場合と生じない場合の両方とも
作り出すことができます。
271は帰納法の仮定より接合後に色を入れ替える方法が存在するので
矛盾が生じない場合で、矛盾が生じる場合は別の問題が生じて帰納法
が成立しません。
635(1): 2013/02/19(火) 21:48:42.39 AAS
>>633
>この場合、４彩色可能ということに矛盾する。従って４彩色した後に
>展開するとＡＣまたはＡＤチェーンが切れていたことになる。
接合して5色目が必要になることが帰納法の仮定に矛盾するのならば、
>>619 >>620 >>624に書いたことにより、5頂点をA, B, C, D, Bと
するとケンペ鎖の有無に関係なく全てのグラフでAとC、AとD、BとC、
BとDのいずれかを接合すると5色目が必要になるので帰納法の仮定に
矛盾することになる。
>仮定が間違いならばＮが小さいときに矛盾が生じるはずである。
Nが小さいときに5頂点をA, B, C, D, Bとして、AとC、AとD、BとC、
BとDを接合しても5色目が必要にならず帰納法の仮定と矛盾しない
グラフの彩色の実例があるのならばそれを示してくれ。
760: 4色パズル攻略法? 2014/10/19(日) 01:52:24.39 AAS
758の仮定で(任意のn個の頂点は4色で塗り分けることができ、任意の、n+1個の頂点は5色なければ塗り分けられないグラフについて考えるとき)
任意のn+1個の頂点に1,2,...,n+1とラベリングする。
仮定より、1を除いたグラフは4色で塗りわけできる。そして1の色は2,3,...,n+1とは違う色でなければならない。
これは2,3,4,...,n+1についても同様。
こうやって塗り分けていけばいいのだ。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 1.961s*