[過去ﾛｸﾞ] ☆四色問題の簡単な証明その３☆ (779ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
595(3): 帰納と類比 2013/02/01(金) 00:28:23.20 AAS
>>593>>594
以前の過去レスから証明方法を確認してほしい。
まだ何色で彩色できるか分からないＮ点のグラフが与えられて可約配置がない
と仮定して、Ｎ−１点で４彩色可能と仮定して、Ｎ−２点で接合して５色
必要になるか、接合前に５頂点が３彩色可能を示しているので５集点が可約
であることは仮定前に分からない状態で、５集点の可約配置を導いている。
>>593-594 何かとんちんかんなことを言ってるよ。
597(1): 2013/02/01(金) 21:31:58.09 AAS
>>595
5集点が可約である、あるいは可約でないかの必ずどちらかである。
どちらの場合でもN点のグラフからP0(5集点)を取り除いてN-1点の
グラフを作ってから接合している。
5集点が可約でない場合にP0(5集点)を取り除けないとした場合は
>>594に書いたようになる。
>>595によると>>594は正しくないようなので、
5集点が可約でない場合にもP0(5集点)を除去可能である。
3, 4集点が含まれない場合を考えているので5集点は必ず含まれて
おり、接合を繰り返せば5集点が可約でない場合にもグラフの
頂点数を減少させることができる。
この場合も可約配置を取り除いていく場合と同様にグラフの頂点数
を減少させることで4色以下にでき帰納法の仮定を満たすことができる。
つまり、N点では彩色に5色必要であるがP0を取り除くことで
N-1点で4彩色可能になるケースを除外できない。
598(1): 2013/02/01(金) 21:35:30.68 AAS
>>595
>>594が正しくないとすると別の問題も生じる。
接合後のグラフは3, 4集点を含まず5集点が必ず含まれ、また
5集点が可約でない場合でも接合できるので、3, 4集点を含まない
グラフの頂点数の最小値が存在しないことになる。
N=4だと4集点のみ、N=5だと3, 4集点のみを含むことは簡単に
確認できるが、帰納法のスタート地点のグラフの頂点数は
いくつになるの？
他の問題点も存在するが>>594に関連することは現時点では
以上のようなことが挙げられる。
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彩色可能であることを示すことはできるの？
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.029s