二分图类

orz hhw posted @ 2018年7月01日 21:32 in 算法学习 with tags 模板 二分图 算法学习 , 127 阅读
  • 简介

类型说明:基于有向图类,是一种左边有$ln$个点,右边有$rn$个点,有$m$条从左边的点$x$指向右边的点$y$的边。

最大匹配:找到最大的边集$M$,使得它们没有公共点,$|M|$为最大匹配的数值。

  • 匈牙利算法

不断暴力找增广路,最坏情况下时间复杂度$O(nm)$。

  • Hopcroft-Karp算法

匈牙利算法的优化,使用BFS每次找到最短的若干条增广路,再使用DFS对他们一起进行增广,最坏情况下时间复杂度$O(m\sqrt{n})$

  • 最小顶点覆盖

求出最大匹配,从左侧每个不在最大匹配中的点出发,找到一条非匹配边-匹配边-非匹配边-匹配边的路径。

注意必须以匹配边结尾,且其中经过的点不能和前面的重复。

最小顶点覆盖集为左部的有匹配且没出现在路径中的点和右部有匹配且出现在路径中的点的并。

证明:

1、最小顶点覆盖集|S|=二分图最大匹配M

2、S能覆盖所有的边:

3、S是最小的顶点集:如果S中的点再少,连M个匹配的边都不能覆盖

  • 最大独立集

 不在最小顶点覆盖中的点构成最大独立集,最大独立集=所有顶点-最小顶点覆盖

  • 最大团
最大团=补图的最大独立集
  • Hall定理

一个傻逼定理,很简单

  • 代码

https://github.com/lbn187/Graph-Theory/blob/master/Bipartite_Graph.hpp