二分图与网络流：基础概念、关键定理与常用算法详解
定义
二分图是图论的一种特殊模型. 若 $G=<V, E>$ 是一个无向图, 如果顶点V可分割为两个不相交的子集 $(X, Y)$, 且图中的每条边 $(i, j)$均满足$i \ in X, j \in Y$, 则称图$G$为一个二分图。
二分图判定
- 无向图 $G=<V, E>$ 为二分图的充要条件是G的所有回路的长度均为偶数。 反证法/染色法易证
一些概念
记一般图 $G=(V,E)$.
-
匹配: 在图G的一个子图M中，M的边集E中任意两条边都不依附于同一个顶点, 则称M是一个匹配.
- 匹配点: 匹配边上的点
- 匹配数: 匹配 $M$ 的边集 $E$ 的大小
- 对于一个匹配$M=(V', E')$, $2|E'| = |V'|$
-
极大匹配(Maximal Matching): 指匹配 $M$无法通过增加未匹配的边的方式来增加匹配的边数.
-
最大匹配(Maximum Matching): 所有极大匹配当中边数最大的一个匹配.
-
完美匹配(完备匹配)：一个图中所有的顶点都是匹配点的匹配, 即 $2|M| = |V|$.
- 完美匹配一定是最大匹配, 但并非每个图都存在完美匹配.
-
最优匹配(带权最大匹配): 在带有权值边的图中，匹配边上的权值和最大的匹配.
- 二分图中, 一般X和Y集合顶点个数相同, 最优匹配也是一个完备匹配. 如果个数不相等, 可以通过补点加0边来转化.
- 一般使用KM算法解决该问题. KM(Kuhn and Munkres) 算法, 是对匈牙利算法的一种贪心扩展.
-
最小覆盖: 最小覆盖分为最小顶点覆盖和最小路径覆盖.
- 最小顶点覆盖: 指求最少的顶点数, 使得图中的每条边都至少与其中一个点相连.
- 最小路径覆盖: 指求最少的不相交简单路径覆盖图中的所有顶点.
-
最大独立集: 寻找最大的点集, 使得其中任意两点在图中无对应边.
- 最大独立集 = 补图最大团 (反之亦然)
- 一般图求最大独立集为 NP-Complete 问题, 但在二分图中有多项式解法.
定理 & 算法
最大流最小割定理
网络 $G=(V,E)$ 的最大流 $f_{max}$ = 最小割 $C_{min}(S,T)$.
首先, $f \le C(S,T)$. 利用反证法.
然后, 构造出一个 $f = C(S,T)$:
定义 $S$ 集合为当前残留网络中s能够到达的点, $T=V-S$.
此时(S,T)构成一个割(S,T). 且对于任意的 $u∈S,v∈T$, 有$f(u,v)=c(u,v)$.
因此有 $f(S,T)=\sum f(u,v)=\sum c(u,v)=C(S,T)$
因此, $f_{max} = C_{min}(S,T)$.
覆盖 & 匹配 & 独立集
在二分图中, 最大匹配=最小顶点覆盖=$|V|$-最小边覆盖=$|V|$-最大独立集.
证明
- 二分图中对最小顶点覆盖、最小边覆盖、最大独立集的理解 - Iguodala的博客 - ****博客
- 二分图最小顶点覆盖数=最大匹配数的证明 - Klaier - 博客园
带权的覆盖 & 独立集
设 $p$ 点权值为 $v_p$.
对于二分图一侧的边, 连边 $(s,p,v_p)$; 另一侧的点, 连边 $(p,v,v_p)$.
那么最小割即为带权最小顶点覆盖. 这可以通过最大流求出.
类似上面的, 有 最大点权独立集=$\sum v_i$-最小点权覆盖.
一些定理
Hall 定理 集合 S_1,S_2,…,S_m ，每个集合都能选出唯一代表，当且仅当，|⋃_i∈IS_i|≥|I| for all I⊆{1,2,…,m}
这个充要条件 |⋃_i∈IS_i|≥|I| for all I⊆{1,2,…,m} 被称为 Hall's condition。
König-Egerváry 定理：二部图中，最大匹配的大小等于最小点覆盖集的大小。
Menger 定理：在图上分开两个点至少要去掉几个点？等于这两点间不相交的路径的个数。
Dilworth 定理：一个偏序集分成多少个 chain？等于最大 antichain 的大小。
最小路径(点)覆盖
最小点不相交路径覆盖
似乎只有DAG上的解法, 一般图上的并不会...
将原图中的点 $p$ 拆成 $p', p''$. 对于边 $(u, v)$, 在新图中连边 $(u', v'')$.
答案即为(原图点数 - 新图最大匹配).
最小点可相交路径覆盖
用floyd传递闭包, 如果 $u$ 可以到达 $v$, 加边 $(u, v)$.
然后就转化为了不相交路径覆盖, 解法同上.
最长反链
链指一个点集, 满足其中任意两点 $u,v$, 或者能从 $u$ 到达 $v$, 或者能从 $v$ 到达 $u$.
反链指一个点集, 满足其中任意两点不可互相到达.
Dilworth定理: 最长反链 = 最小链覆盖.
同时, 链一定是路径的一部分. 因此最小链覆盖 = 最小可相交路径覆盖.
因此, 最长反链 = 最小链覆盖 = 最小可相交路径覆盖
算法见上.
圈覆盖
即求有向图有多少个点不相交的环, 覆盖图上所有点.
类似最小不相交路径覆盖建图, 跑二分图匹配.
有解的充要条件是二分图有完美匹配; 此时, 可以把得到的匹配看做一个置换, 置换的每个环都是一个圈.
最大权闭合子图
网络流——最小割求最大权闭合子图 - CaptainChen的博客 - ****博客
定义
在一个有向图中, 每个点都有一个权值 $v_i$, 选择一个权值和最大的子图, 使得每个点的后继都在子图里面, 这个子图就叫最大权闭合子图.
求法
从源点 $s$ 向每个正权点连一条容量为权值的边, 每个负权点向汇点 $t$ 连一条容量为权值的绝对值的边, 有向图原来的边容量全部为无限大.
求它的最小割, 割掉后, 与源点s连通的点构成最大权闭合子图, 权值为 (正权值之和-最小割).
边/点连通度
图的匹配问题与最大流问题（四）——计算图的边连通度和点连通度 - smartxxyx的专栏 - ****博客
定义
图 $G = (V, E)$ 的边连通度指边集 $E$ 的一个最小子集 $E'$ 的大小, 使得 $G - (V, E')$ 或者是非连通图, 或者是一个平凡图（仅包含一个独立点的图).
图 $G = (V, E)$ 的点连通度指点集 $V$ 的一个最小子集 $V'$ 的大小, 使得 $G - (V', E)$ 或者是非连通图, 或者是一个平凡图（仅包含一个独立点的图).
求法
边连通度: 任选一点为源点, 枚举汇点求最小割, 最小值即为边连通度.
点连通度: 拆点建图: $(u', v'', +\infty)$, $(u', u'', 1)$. 任选 $u''$ 为源点, 枚举 $v'$ 为汇点, 求最小割即可.
最小割计数
假的
最小割计数 - 题目 - Universal Online Judge
UOJ #85 最小割计数 题解 - 博客 - PoPoQQQ的博客
参考资料
- 二分图大合集——二分图最大匹配（最小覆盖数），完美匹配以及最优匹配（带权最大匹配） - ling_wang的博客 - ****博客
- 关于最大匹配，最小点覆盖，最少路径覆盖和最大独立集的总结 - vocaloid01的博客 - ****博客
- 网络流常见建模总结 - Panda2134's Blog