二分图匹配匹配.ppt

文档介绍：图论2江川二分图一个图的点集可以划分为两个不相交的子集,每一个子集中的点和该子集中的其他点没有边相连二分图一个图是二分图的充要条件是这个图里没有奇环二分图匹配匹配:给定一个二分图G,M为G边集的一个子集,如果M满足当中的任意两条边都不依附于同一个顶点,则称M是一个匹配。最大匹配:所有匹配中边数最多的。完备匹配:如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完备匹配。二分图匹配Hall定理一个二分图有完备匹配的充要条件是:任意k个点相邻的点的集合中不少于k个点匈牙利算法M-交错路:p是G的一条通路,如果p中的边为属于M中的边与不属于M的边交替出现,则称p是一条M-交错路。M-饱和点:对于v∈V(G),如果v与M中的某条边关联,则称v是M-饱和点,否则称v是非M-饱和点。M-可增广路:p是一条M-交错路,如果p的起点和终点都是非M-饱和点,则称p为M-可增广路。匈牙利算法匈牙利算法ForalliinX:1、从i出发寻找可增广路2、沿增广路更新(删除原属于M的边,增加不属于M的边)O(nm)