定义
二分图是图论的一种特殊模型. 若 (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|)-最大独立集.
证明
带权的覆盖 & 独立集
设 (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的博客 - CSDN博客
定义
在一个有向图中, 每个点都有一个权值 (v_i), 选择一个权值和最大的子图, 使得每个点的后继都在子图里面, 这个子图就叫最大权闭合子图.
求法
从源点 (s) 向每个正权点连一条容量为权值的边, 每个负权点向汇点 (t) 连一条容量为权值的绝对值的边, 有向图原来的边容量全部为无限大.
求它的最小割, 割掉后, 与源点s连通的点构成最大权闭合子图, 权值为 (正权值之和-最小割).
边/点连通度
图的匹配问题与最大流问题（四）——计算图的边连通度和点连通度 - smartxxyx的专栏 - CSDN博客
定义
图 (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的博客