璐村惂鐢ㄦ埛_00aAACU馃惥的个人资料 - RAT

璐村惂鐢ㄦ埛_00aAACU馃惥 -

-

关注数: 281 粉丝数: 340 发帖数: 1,500 关注贴吧数: 14

关于归纳法的一个4色定理证明求救一下各位大神,这个证明存在什么问题么?这是百度文库上的一篇文章,无意中看到,挺感兴趣的. 对（连通的简单）平面图（记为G）的结点数n进行归纳。当n=1时，结论当然成立。假设当n=k(k是自然数)时结论成立，当n=k+1时：根据（连通的简单）平面图的性质，必存在一个结点，设为v，其度（记为d(v)）<=5。 1、当d(v)<4时，图G除去结点v得到的子图，记为G-{v}，根据归纳法假定，结论成立。而结点v可以用4种颜色中的某一种进行着色，故结论成立。 2、当d(v)=4时，图G除去结点v得到的子图，记为G-{v}，根据归纳法假定，结论成立。设与结点v相联的结点依此为v1,v2,v3,v4，其着色各不相同，依此为c1,c2,c3,c4（着色若有相同，则结点v就可以用4种颜色中的某一种进行着色），如图1所示。现在来证明结点v可以用4种颜色中的某一种进行着色。（接下来主要要证明v1,v2,v3,v4，其着色必须要有相同，只要证明过程没错就整段没事。）从结点v1出发，构造可达结点集，其结点的着色只有2种，c1和c3交替出现，依此为c1,c3,c1,c3,c1,c3,c1,c3，……。若该结点集不包含结点v3，则结点v3就可以用c1进行着色，而不影响其他结点的着色，那么，结点v就可以用c3进行着色。若该结点集包含结点v3，则从结点v2出发，构造可达结点集，其结点的着色只有2种，c2和c4交替出现，依此为c2,c4,c2,c4,c2,c4,c2,c4，……。则该结点集不可能包含结点v4（否则，就不是平面图了），那么，结点v4就可以用c2进行着色，那么，结点v就可以用c4进行着色。 3、当d(v)=5时，图G除去结点v得到的子图，记为G-{v}，根据归纳法假定，结论成立。设与结点v相联的结点依此为v1,v2,v3,v4,v5，且只有2个结点的着色相同（若有2个以上结点的着色相同，则结点v就可以用4种颜色中的某一种进行着色），着色相同的结点对的物理位置有相邻和相隔2种情况：（1）相邻。与结点v相联的结点的着色依此为c1,c1,c2,c3,c4，如图2所示。现在来证明结点v可以用4种颜色中的某一种进行着色。从结点v3出发，构造可达结点集，其结点的着色只有2种，c2和c4交替出现，依此为c2,c4,c2,c4,c2,c4,c2,c4，……。若该结点集不包含结点v5，则结点v5就可以用c2进行着色，而不影响其他结点的着色，那么，结点v就可以用c4进行着色。若该结点集包含结点v5，则从结点v4出发，构造可达结点集，其结点的着色只有2种，c3和c1交替出现，依此为c3,c1,c3,c1,c3,c1,c3,c1，……。该结点集不可能包含结点v1和v2（否则，就不是平面图了），则结点v4就可以用c1进行着色，而不影响其他结点的着色，那么，结点v就可以用c3进行着色。（2）相隔。与结点v相联的结点的着色依此为c1,c2,c1,c3,c4，如图3所示。现在来证明结点v可以用4种颜色中的某一种进行着色。从结点v2出发，构造可达结点集，其结点的着色只有2种，c2和c3交替出现，依此为c2,c3,c2,c3,c2,c3,c2,c3，……。若该结点集不包含结点v4，则结点v4就可以用c2进行着色，而不影响其他结点的着色，那么，结点v就可以用c3进行着色。若该结点集包含结点v4，则从结点v2出发，构造可达结点集，其结点的着色只有2种，c2和c4交替出现，依此为c2,c4,c2,c4,c2,c4,c2,c4，……。若该结点集不包含结点v5，则结点v5就可以用c2进行着色，而不影响其他结点的着色，那么，结点v就可以用c4进行着色。若该结点集中包含结点v5，则从结点v4出发，构造可达结点集，其结点的着色只有2种，c3和c1交替出现，依此为c3,c1,c3,c1,c3,c1,c3,c1，……。该结点集不可能包含结点v1（否则，就不是平面图了），则结点v1就可以用c3进行着色，而不影响其他结点的着色。同样道理，从结点v5出发，构造可达结点集，其结点的着色只有2种，c4和c1交替出现，依此为c4,c1,c4,c1,c4,c1,c4,c1，……。该结点集也不可能包含结点v3（否则，就不是平面图了），则结点v3就可以用c4进行着色，而不影响其他结点的着色，因此，结点v就可以用c1进行着色。综上所述，当n=k+1时，结论成立。根据归纳法性质，4色定理得证。

送个51wan 新服 v1号. 刚开了5天的服,50+,只招了个太史慈.不过紫魂挺多的. v1号. 要上学,没时间玩.求人打理,以后不会再将号找回来了. 有意思速度联系QQ179105696

唉，要上学了 - -

明天开学先伤心一下

水水更健康

好吧我是来水的不解释

哦哦哦哦哦哦

坐等杯具。

我一口盐汽水喷死你

关于c6-00 c6-01 n97 mini 准备进手其中一部，那部比较好？求大虾指教

腾讯，神马都是浮云，不解释

汉魅咋搞，家里用连不上

杰哥V5 期待复活中。。。。。。。。

还要多久才写完一个寒假没看，然后用了一天疯狂看，感觉这样比较爽，不然很难受

继续一发 rt

华南5区路过- - rt

为凑30贴压力大，不要被封啊

有点冷清。。 RT

1 下一页