以文本方式查看主题 - 中文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!种了,希望我说明白了!!” 这个和官方习题解答上的证明一样,但是我认为这是有问题的。 看下面情况,设 于是我们 比如顶点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 -- 呵呵 对于这些情况作调整 是肯定可以调整出解的 问题在于不能与之前存在的解重复,即: 不仅不能与不需要调整就可以得到的普通解重复 而且不能与之前得到的调整过的解重复 这个比较困难 对于这些特殊的需要调整才能得到解得情况 |
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
78.125ms |