和点。 如果没有,那么肯定是最大匹配了,如果 有,从图中的任一选定的非饱和点出发,用标号 法寻找增广链。如果找到增广链,则就可以得到 增广;否则从图中另一个非饱和点出发,继续寻
找增广链。重复这个过程直到G中不存在增广链
结束,此时的匹配就是G的最大匹配。这个算法 通常称为匈牙利算法.
匈牙利算法
基本思想:设G是具有二部划分(V1,V2)的二部图,从图G的 任意匹配M开始.若M饱和V1,则M是G的匹配.若M不能饱和 V1,则在V1中选择一个非M饱和点x,若G中存在以x为起点 的M可增广路P,则M’=MP就是比M更大的匹配,利用M’ 代替M,并重复这个过程.若G中不存在以x为起点的M可增 广路,则令H是根在x的M交错子图的顶点集,并令 S=HV1,T=HV2, 由定理1,T=NG(S),且G中不存在以x为 起点的M可增广路,此时称x为检验过的非M饱和点.对V1中 其它未检验过的非M饱和点重复该过程,直到V1中的所有 非M饱和点全部检验过为止.当整个过程结束时,由于G中
• 最简单的情况是G是一条单通路。显然
• ①G的边应交错地属于M(M不能有邻接的边)。
• ② G的第一条边和最后一条边中至少应有一条 边属于M (否则M不是最大匹配)。如下图所示:
• 定义4:若M是图G的一个匹配,若从G中 一个顶点到另一个顶点存在一条道路,此 路径由属于M和不属于M的边交替出现组成
§8.3
Hall定理
设有m个人,n项工作,每个人会做其中的若
干项工作,能不能适当安排,使得每个人都有工
作做?
w1
w2
w3
w4
w5
m1
m2
m3
m4
当m>n时,肯定是不可能的,即使是 m≤n也不一定。但如果每个人能做的工作 越多,越容易实现。