Hall定理（二分图匹配问题，Hungary算法基础）

前言

hall定理是判定二分图是否存在完全匹配的定理。

完全匹配&＃xff1a;是指最大匹配数为min(|X|,|Y|) 也就是X或Y集合其中一个集合所有点都被匹配了。

定理内容

设二分图中G&＃61;中 |V1|&＃61;m<&＃61;|V2|&＃61;n,G中存在从V1到V2的完全匹配当且仅当V1中任意k(k&＃61;1,2,...,m)个顶点至少与V2中k个顶点是相邻的。

证明

必要性

因为是完全匹配&＃xff0c;所以V1中任意k个点都是匹配的&＃xff0c;显然至少与V2中k个点是相邻的。

充分性

反证法。设G中不存在完全匹配&＃xff0c;取G的一个最大匹配M&＃xff0c;则V1中至少有一个点不在M上&＃xff0c;且该点必至少与一条不在M中的边相连&＃xff0c;该边的另一个顶点若也为M-非饱和点&＃xff0c;则与M为最大匹配矛盾&＃xff0c;若另一个顶点为M-饱和点&＃xff0c;则考察在M中与该顶点相邻的点&＃xff0c;利用饱和点去考察在M中相邻的饱和点&＃xff08;交错地考察&＃xff0c;即交错地通过M中的边和非M中的边&＃xff09;&＃xff0c;直至考察完毕&＃xff0c;由相异性条件知&＃xff0c;最后必考察至非饱和点&＃xff0c;此时出现一条增广路&＃xff0c;又与假设矛盾&＃xff08;M不是最大匹配&＃xff09;&＃xff0c;故充分性成立。

Hall定理的一个推论

设二分图中G&＃61;中|V1|&＃61;m<&＃61;|V2|&＃61;n&＃xff0c;V1中每个顶点至少关联正整数t条边&＃xff0c;V2中每个顶点至多关联t条边&＃xff08;t条件&＃xff09;&＃xff0c;则G存在从V1到V2的完全匹配。

证明&＃xff1a;因V1中任意k个顶点至少关联kt条边&＃xff08;kt条边至少关联V2中的k条边&＃xff09;&＃xff0c;故V1中任意k(k&＃61;1,2,...,m)个顶点至少与V2中k个顶点相邻&＃xff0c;即得到相异性条件&＃xff0c;得证。