|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- 关于四色猜想的证明 (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=74057) |
|
-- 作者：killsking -- 发布时间：4/10/2009 3:03:00 PM -- 关于四色猜想的证明 关于四色猜想的证明 |
|
-- 作者：lazycat_work -- 发布时间：4/11/2009 12:25:00 PM -- 不是只有五色的证明么？四色的证明还没有说服力 |
|
-- 作者：xuchao1221 -- 发布时间：4/12/2009 2:30:00 PM -- 是的，四色定理是用计算机证出来的，所以没有说服力，不过也不会轻易考。 |
|
-- 作者：killsking -- 发布时间：4/20/2009 5:50:00 PM -- 关于四色猜想的证明 1、 证明任何平面均为四可着色，即证明极大平面图是四可着色的。 极大平面图可以通过一个非极大平面的平面图加边得到 而平面图也可以通过某一极大平面图去边得到（注 同一阶的极大平面图存在异构） 2、 G为n(n>=3)阶简单平面图的简单连通图，G为极大平面图当且仅当G的每一个面的次数均为3. 证明：必要性 因为G为简单平面图，所以G中无环和平行边，又因为G是至少有3个顶点的极大平面图，所以G连通且无割点和桥，于是G中各面的边界数均为圈且次数均大于3.下面只需证明各面的次数均不大于3。否则没存在面Ri,deg(Ri)=S>=4见图1。在G（平面嵌入）中，若V1,V3不相邻在Ri内加边（V1,V3）不破坏平面性，这矛盾于G为极大平面图，因而（V1,V3）必相邻；类似的，（V2,V4）必相邻且边(V2,V4)也在Ri的外部，边（V1,V3）于（V2,V4）均在Ri的外面，无论用怎样的画法，它们必相交，这又矛盾于G是平面图，所以S=3 充分性 若G中不存在不相邻等点，结论显然。若G中存在不相邻顶点，只需证明任何不相邻顶点之间再加边均会产生边之间的相交即可。没U,V为二不相邻的顶点，则U,V不可能都在外部面R0的边界上。因而至少有一个顶点，比如V不在R0的边界上，见图2，则与V关联各边也不在C0上，没G’=G-V，G’中存在原来含V的圈C，因为U和V不相交，所以U不在C上，由约当定理可知，若加边（U,V），则它必与C相交，所以G为极大平面图。 3、 当n=3时 极大平面图是三个点，由于只有3个顶点，故是四可着色的 当n=4时 可以在三个点的极大平面图加一个点得到四个点极大平面图，而该点只能加在三个点的极大平面图的面中或加在边上，而该点最多与三个点连接，故四个点的极大平面图。 假设k个顶点的极大平面图是是四可着色的。 在该极大平面图加一个点可以得到k+1个顶点的极大平面图。 而这个点只能加在这个极大平面图的面上或边上： 1. 该点加在面中，则该点最多与三个顶点相连之后得到极大平面图，而这三点只用了三种颜色，故可以用第四种颜色染上。 2. 该点加在边上，则由于在边上加了一个点，故将该边收缩，就得到k-1个顶点的图，将其中的平行边删除得到平面图，而k-1顶点的平面图是四可着色的，故可以将加点的边染成相同颜色，那么与新加的点可以相连组成极大平面图的点最多用了三种颜色。 综上有k+1顶点的极大平面图是四可着色的。 故所有的平面图是四可着色的。
|
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
50.781ms |