|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- P200页习题5的证明 (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=54197) |
|
-- 作者：liuyan1031 -- 发布时间：10/23/2007 12:11:00 AM -- P200页习题5的证明 必要性： 由题意，交替选点，可设偶序列为第一个人选点集合，奇序列为第二个人选点集合。 V1＝{Vi│i为偶数}；V2＝{Vj│j是奇数}可构成二部图。 若第一个人胜出，则最后一个被选点Vz∈V1,又第一个人先选点，则可知│V1│＝│V2│+1； 由Hall定理，二部图G＝<V1,V2,E>中存在由V2到V1的完备匹配M,且│M│=│V2│。 因为V1＝V2+1,则V1中必有一个非饱和点，否则与M是最大匹配矛盾，所以不存在完美匹配。 充分性： 若有完美匹配，则G中顶点都是饱和点，V1中不含非饱和点，则对于任意的Vx∈V1，在V2中必有Vy与之对应，使得（Vx，Vy）∈M。由于顶点交替出现，且第一个人选取，则最后一个被选 点必属于V2，说明第二个人胜，与题设矛盾。 大家看看我的证明是否有问题,多谢指出! |
|
-- 作者：liuyan1031 -- 发布时间：10/23/2007 11:06:00 PM -- 帮帮忙呀,大家 |
|
-- 作者：sarahsd -- 发布时间：10/24/2007 11:01:00 AM -- 你证的是没错的，觉得从交错路径上讲跟直观. |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
30.273ms |