二分图最大婚配-匈牙利算法

二分图最大匹配--匈牙利算法

二分图是什么就不啰嗦了。

匈牙利算法的核心就是：不断地找一条增广路径（增广路的定义(也称增广轨或交错轨)： 若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。（M为一个匹配）），然后反转这条路径，则匹配的边就会增加1

C语言代码：

二、Hall定理
　定理18.5(Hall定理)设二部图G＝<V1，V2，E>中，|V1|≤|V2|. G中存在从V1到V2的完备匹配当且仅当V1中任意k(k＝1，2，…, |V1|)个顶点至少与V2中的k个顶点相邻。
　　本定理中的条件常称为“相异性条件”。
　　证 定理的必要性显然。下面证明充分性，即证明只要满足相异性条件，G中最大匹配一定是完备匹配。设M为G中一个最大匹配。若M不是完备匹配，必存在vx∈V1为M的非饱和点。且必存在e∈E1＝E－M与vx关联，否则vx将是孤立点，这与相异性条件矛盾。并且V2中与vx相邻的顶点都是M－饱和点，若存在vy∈V2 (与vx相邻)为非饱和点，则M'＝M∪(vx,vy)也是匹配，这显然与M为最大匹配矛盾。考虑从vx出发的尽可能长的所有交错路径，由于M是最大匹配，又由定理18.4可知，这些交错路径都不是可增广的，即每条路径异于vx的端点一定是M－饱和点，于是这些端点全在V1中，令
　　　　S＝{v|v∈V1且v在从vx出发的交错路径上}
　　　　T＝{v|v∈V2且v在从vx出发的交错路径上}
由于各条交错路径的两个端点全在S中，所以|S|＝|T|+1. 这正说明V1中|T|+1个顶点只与V2中|T|个顶点相邻，这矛盾于相异性条件，因而V1中不可能存在M－非饱和点，故M是完备匹配。
　　图18.4(3)中，存在着V1中的两个顶点只与V2中的一个顶点相邻，因而不满足相异性条件，于是(3)中不存在完备匹配。而(1)，(2)均满足相异性条件，因而都存在完备匹配。
　　由定理18.5还可以得出下面定理。
　定理18.6 设二部图G＝<V1，V2，E>中，V1中每个顶点至少关联t(t≥1)条边，而V2中每个顶点至多关联t条边，则G中存在V1到V2的完备匹配。
　　证 由定理中的条件可知，V1中任意k(1≤k≤|V1|)个顶点至少关联kt条边，而因为V2中每个顶点至多关联t条边，所以这kt条边至少关联V2中k个顶点，这正说明G满足相异性条件，因而G中存在完备匹配。
　　常称定理18.6中的条件为t条件。图18.4中，(2)满足t＝2的t条件，当然存在完备匹配，而在(1)中不满足t条件，但因它满足相异性条件，所以才存在完备匹配。