以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  [求助]离散第十三章习题6(1)  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=78272)


--  作者:blueteaxk
--  发布时间:11/22/2009 1:52:00 PM

--  [求助]离散第十三章习题6(1)
设二部图G=<V1,V2,E>满足相异性条件,且对任意顶点v属于V1,|N(v)|>=t,又已知|V1|=r,证明:若t<=r,则至少存在t!个V1到V2的完备匹配。

想了一天还是不会
而无论是网上下载的答案还是官方习题解答的证明,似乎都不对


--  作者:yinwpnew
--  发布时间:11/24/2009 12:29:00 PM

--  
可以这样想:V1、V2......Vi+1......Vr,一共r个点,任一个Vi+1选择匹配的时候,它所对应的的t个临界点之多已经被前面的点占用了i个,因此他还至少有t-i个选择。当到达Vt+1时,它的t个临界点不可能被全占完,否则不满足向异性条件。因此它始终是有一个匹配选择的,它以后的也是这个道理。因此依次有t,t-1,t-2,.......1,1,1,1,1,1...种选择。就是t!种了,希望我说明白了!!
--  作者:blueteaxk
--  发布时间:11/24/2009 2:16:00 PM

--  
谢谢,您的解答是:
“可以这样想:V1、V2......Vi+1......Vr,一共r个点,任一个Vi+1选择匹配的时候,它所对应的的t个临界点之多已经被前面的点占用了i个,因此他还至少有t-i个选择。当到达Vt+1时,它的t个临界点不可能被全占完,否则不满足向异性条件。因此它始终是有一个匹配选择的,它以后的也是这个道理。因此依次有t,t-1,t-2,.......1,1,1,1,1,1...种选择。就是t!种了,希望我说明白了!!”

这个和官方习题解答上的证明一样,但是我认为这是有问题的。

看下面情况,设
顶点集V1={1,2,3}
顶点集V2={a,b,c}
边集E={(1,a),(1,c),(2,b),(2,c),(3,a),(3,b)}
显然,|V1|=r=3,t=2
我们考察它的完美匹配数目

于是我们
先看V1中的顶点1,它邻接的边确实有2种选法:a,c
再看V1中的顶点2,它邻接的边确实至少有1种选法
但是我们并不能保证,对应上面顶点1和2的每种选法,顶点3邻接的边都存在至少1种选择

比如顶点1邻接a,顶点2邻接b,则此时顶点3的所有(t=2)个邻接点都被占完,它没有匹配选择
这就是我认为您证明中的问题所在


--  作者:yinwpnew
--  发布时间:11/25/2009 12:06:00 PM

--  
我思考了一下,你举得例子很厉害!!但是书中答案是说“vt+1是可以找到匹配的”,我认为这句话不应该静态地理解,而要这样:若vt+1得全部t个临界点都被前面的t个家伙霸占了,此时vt+1必定可以通过“排挤”前面的某一个点的匹配,或者是说让前面的某个点调整一下,若前面的t个点都不能再调整了,此时才有结论:不符合相异性条件。

至于若某个点被调整后,那么它的可选择数会不会因此少一个,这个问题我没理解透,还请继续交流哦,哈哈...


--  作者:blueteaxk
--  发布时间:11/25/2009 2:06:00 PM

--  
呵呵
对于这些情况作调整
是肯定可以调整出解的
问题在于不能与之前存在的解重复,即:
不仅不能与不需要调整就可以得到的普通解重复
而且不能与之前得到的调整过的解重复
这个比较困难

对于这些特殊的需要调整才能得到解得情况
网上的dengjian版解答(http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=32659)中有所考虑
但是他给出的调整解是与普通解相重复的


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