以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  [第五周第二帖]Γzx,Γzy的长度依然为偶数吗?  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=38440)


--  作者:apolor
--  发布时间:9/28/2006 11:01:00 PM

--  [第五周第二帖]Γzx,Γzy的长度依然为偶数吗?
《离散数学教程》(2002年6月第1版)P122定理7.8(一个图G为二部图当且仅当图G中无奇圈)的证明中,有这样一句话:“设Vz∈V(Γzx)∩(Γzy)且Γzx与Γzy除Vz外无公共顶点,则因为Γzx,Γzy的长度依然为偶数,所以Γzx∪(Vx, Vy)∪Γzy为G中一个奇圈,这与G中无奇圈矛盾。”
如果Vz∈V2,那么Γzx,Γzy的长度不都成了奇数了吗?将“Γzx,Γzy的长度依然为偶数”改为“Γzx,Γzy的长度之和依然为偶数”似乎较为妥当。
--  作者:woaimeiying
--  发布时间:9/28/2006 11:58:00 PM

--  
书上是没有问题的
建议你再仔细看一遍
而且
我认为
其实也没有必要看这么仔细

--  作者:Logician
--  发布时间:9/29/2006 1:52:00 AM

--  
嗯。我觉得你说得对。
应该是“Γzx,Γzy的长度同奇偶”……


--  作者:computerlover
--  发布时间:9/29/2006 8:31:00 AM

--  
如果Vz∈V2,那么Γzx,Γzy的长度不都成了奇数了吗?将“Γzx,Γzy的长度依然为偶数”改为“Γzx,Γzy的长度之和依然为偶数”似乎较为妥当。

如果Vz∈V2,应该是:Γz长度是奇数,Γzy长度是偶数啊。(书上说Γzx与Γzy除了Vz外无公共顶点,这样如果Vz在V2中的话,图7.16是下面一行顶点(V2)的中间两个顶点就应该合为一个顶点啊)。
总之这个定理证明不严密,类式的还有很多,感到都没说清楚。

离散P112的定理7.5的证明中在必要性(2)第三行说:“必存在度分别分di,dj,顶点vi,vj,而(vi,vj)不属于E(g),(vi,vj)属于E(G)”
是怎么个必然存在法啊?而且不是所有情况都可以重复的啊,不一定能得到Gr吧。它的意思是删两条边,再加二条保证度数列不变,使Vi与V1想关联,但如果V1与Vj本身就不关联呢?那又怎么能通过加边(V1,Vi)
如果度数列为:1 1 0 0 0 0  0  还能通过重复过程得到Gr就不能等到Gr了啊 。(V1只与V2相关联啊,不满足V1与度为d1、d2、d3...........d(d1+1)的所有顶点都相邻啊。


W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
39.063ms