首页 > 其他 > 详细

Hall 定理

时间:2021-07-20 23:14:04      阅读:5      评论:0      收藏:0      [点我收藏+]

定理

二分图 \(G\) 中两部分顶点组成的集和分别为 \(X,Y\) ,那么它们构成完美匹配的充分必要条件就是X中的任意k个点至少与Y中的k个点相邻

必要性证明

连出去的边数都不足点数,那么显然不能构成完美匹配

充分性证明

假如存在一个满足 \(Hall\) 定理的二分图 , 且不满足完美匹配
那么假设两边都存在一个未匹配的点 , 由于满足 \(Hall\) 定理 , 这个没有被匹配的点肯定有一条没有被匹配的边
那么假设这条边对面的点被匹配过了 , 这个点和那个未匹配的点组成 \(|X|\) 后, 这个点又一定连向了除它匹配的点外的至少一个点
这样下去就一定可以找到这条增广路了 , 所以一定是可以满足完美匹配的

推论

二部图G中的两部分顶点组成的集合分别为 X,Y, 若∣X∣=∣Y∣,且 G 中有一组无公共端点的边,一端恰好组成X中的点,一端恰好组成 Y 中的点,则称二部图 G 中存在完美匹配

详细证明见关于Hall定理的学习

雾 @ @

Hall 定理

原文:https://www.cnblogs.com/Arielzz/p/15037145.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!