以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  给个简便方法证明Peterson图边色数是4  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=68696)

--  作者：ccyndi
--  发布时间：10/24/2008 6:11:00 PM

--  给个简便方法证明Peterson图边色数是4
RT
我只会画图，很麻烦~
--  作者：wkaing
--  发布时间：10/24/2008 10:12:00 PM

--  
先在peterson图中找一个哈密顿通路（当然不是回路），这条通路上是2边可着色的，在通路上添5条边构成peterson图，其中每个顶点最多连接两条边（两端点的各两条共四条，并且它们之间也不可能有边连接两短点，否者没哈密顿图），所以至多增加两色，一定是四边可着色的。在有peterson图的特点可知，那个通路的两个中的一个在加边后是形成的两个圈，他们奇偶数是一致的，所以一定不会是3边可着色的。

--  作者：ccyndi
--  发布时间：10/25/2008 2:40:00 PM

--  
首先更正一下，彼得森图应当是“Petersen” Graph

仍觉复杂，不过受到很多启发，谢了先^_^，另证如下，望指正：
证明：
也是先在petersen图G中找一个哈密顿通路C，则C是2-边可着色的（在通路上添应当是 6 条边构成petersen图），设其起点为A，其必连接该通路上不相邻两点a、b，形成边e_1、e_2, 则C+e_1必是3-边可着色的，而两新边相邻，e_1必着与e_2不同的颜色，故C+e_1+e_2必为4-边可着色的，而由维津定理：
X'(G)=△(G)or△(G)+1,故得X‘(G)=4
QED

--  作者：wkaing
--  发布时间：10/25/2008 4:16:00 PM

--  
是的，是在通路加6条边，疏忽了。关了电脑才意识到，呵呵。不过你这个还是注意下一，因为在顶点A上加两条边后，不一定必是4色的，如果加入e-1后构成的偶圈，e-2构成的奇圈，那么还是只用三色就行了，而且Petersen图里如果找一个哈密顿通路的话，起点和终点必加两边正好构成两个偶圈，而另一个顶点加两条边后则一个是奇圈一个是偶圈。所以，设A点时还是注明它是在内圈的好，否在在外圈的话，不一定必是4可着色的。呵呵。


[此贴子已经被作者于2008-10-26 13:35:51编辑过]
--  作者：ccyndi
--  发布时间：10/25/2008 9:10:00 PM

--  
恩，这点我确实得斟酌一下，不过真的很谢谢你呀！
--  作者：wkaing
--  发布时间：10/25/2008 11:27:00 PM

--  
不客气，哈哈（自己意见，也不知道对不对）
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 45.898ms