二分图

  • 其顶点可分为两集合X和Y,所有的边关联的两顶点中,恰一个属于X,另一个属于Y。同一集合的结点不相连。
  • 如果一图是二分图,那么它一定没有奇环。
  • 如果一图没有奇环的话,那么他可以是二分图

二分图的判顶

  • 染色法:假设DFS初始点A涂黑色,与它相邻的点涂白色。如果搜到某一个点u的相邻点v已经涂色并且与u同色,就不可能是二分图

概念

  • 匹配:给定一个二分图G,在G的一个子图M中,M的边集合{E}中的任意两条边都不依附同一个顶点,则称M是一个匹配
  • 最大匹配:包含的边数最多的匹配
    • 任意取一个匹配M(可以是空集或只有一条边)
    • 令S是非饱和点(尚未匹配的点)的集合
    • 如果S = 空集 ,则M已经是最大匹配
    • 从S中取出一个非饱和点u0作为起点,从此起点走交错(交替属于M和非M的边构成的极大无重复点通路或回路)P
    • 如果P是一个增广路(P的终点也是非饱和点)令M = (M-P)U(P-M)
    • 如果p都不是增广路,则从S中去掉u0 转到第三步
  • 完美匹配:所有的点都在匹配边上的匹配
  • 最佳匹配:如果G为加权二分图,则权值和最大的完美匹配称为最佳匹配
  • 图三、图四中红色的边就是图二的匹配,图四是最大匹配也是完美匹配*
    图片说明

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

  • 交替路:从一个未匹配点出发,依次经过非匹配、匹配边、非匹配边...形成的路径
  • 增广路:从一个未匹配点吃法,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路
  • 图五中的一条增广路如图(匹配点均用红色标出)*
    图片说明
    增广路取反【黑变红,红变黑】就可以多找一个匹配【黑色多于红色】

由增广路定义可以推出下述三个结论

若P是图G中一条连通两个未匹配顶点的路径,并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。

  • 1——P的路径长度必定为奇数,第一条边和最后一条边都不属于M【首尾是未匹配点】
  • 2——p经过取反操作后可以得到一个更大的匹配M'
  • 3——M为G的最大匹配当且仅当不存在相对于M的增广路径

算法的轮廓

  • 置M为空
  • 找出一条增广路径P,通过取反操作获得更大的匹配M' 代替M
  • 重复第二步,直到找不出增广路径为止
  • 复杂度O(V*E)