二分图的对集
设二分图为,本节求饱和中每个点的对集的一个充分必要条件,这是Hall在1935年给出的,称为Hall定理。
中的邻域,即与
中顶点相邻的所有顶点全体。
例
设是二分图,则G有饱和X的每个顶点的对集的充分必要条件是对所有,均有
与Hall定理等价的有相异代表元定理:
集合的一个子集簇有一个相异代表元当
且仅当对于集合的所有子集,有
:
必要性:假设是二分图的一
个饱和中每个顶点的一个对集,对中的
任一个子集
则在中有个顶点在下分别
与配对,因此有
充分性:假设满足条件, 是的一个最大对集。下证饱和中所有点。
反证法。假设是一个非饱和点。令
记为中在下与配对的顶点集合。
下证,其中。
否则,设,记,使,则
。下分两种情况讨论:
情况1: 是非饱和点
因,可以证明图中存在
可扩路,矛盾。
情况2: 是饱和点
则存在使。可以证明
从而得到,矛盾。
二分图有完美对集的充分必要条件是,并且对一切,均有
是正则二分图,则有完美对集。
证: 是正则二分图,则,分别用表示与中顶点相关联的边子集。而是
正则二分图,故。
, 有完美对集。
设是连通的二分图,则G的每一条边都含在一个完美对集中的充分必要条件是,且对X的每一个非空真子集S,均有
证明思路
必要性:对中的每个非空真子集,
因为连通,存在使与中一个
点相邻,又中存在含边的完美对
集,则就是的完美对集。结
【精品】PPT课件 5.3 二分图的对集 来自淘豆网m.daumloan.com转载请标明出处.
