标签：原图 匹配 最大 覆盖 对于 flow 最小

\(\bf\sf 0x01\) 网络最大流

算法

Dinic

算法过程：

• 建出原图 \(G\) 的层次图
• dfs 找出阻塞流 \(f\)，并加入原最大流中
  • 当前弧优化，对于已经增广到极限的边 \((u,v)\)，可以直接修改 \(h\) 数组不遍历，注意每次递归完都要重新赋值一遍。
  • 若当前前面流到 \(u\) 的流已经流完，直接返回。

时间复杂度：

• 对于普通图，时间复杂度为 \(\mathcal O(n^2m)\)。
• 对于单位容量网络，时间复杂度为 \(\mathcal O(m\min(\sqrt{m},\sqrt[3]{n^2}))\)。
• 特殊的，对于二分图最大匹配问题，时间复杂度为 \(\mathcal O(m\sqrt n)\)。

ISAP

算法过程：

• 倒序 bfs，并从 \(0\) 开始给 \(lev\) 赋值
• 重复以下过程，直至 \(lev_s\ge n\)
  • dfs 找出阻塞流 \(f\)，并加入原最大流中
    • 当前弧优化 + 无流返回
  • 未返回，说明 \(u\) 的所有出边已经遍历完毕而且 \(u\) 还有残余流量，有以下两种更新方法：
    • 此时只要将 \(lev_u\gets lev_u + 1\)，即每次一定会对仍然还有流的节点 \(lev\) 增加，而且因为有流就有连续路径，所以不存在断流。因为最多增广 \(n\) 次，于是保证了时间复杂度，这种更新比下面好写很多。
    • 此时可以更新 \(lev\) 数组为 \(\min\{lev_v\}+1\)，相当于提前做了 BFS，注意节点回退。

时间复杂度：

• 理论上应该也是 \(\mathcal O(n^2m)\)，但是因为此算法是在 Dinic 基础上优化的，所以实际上是会比 Dinic 快的，而且不算很难写。

模型

最小割

定义

定义一个有向图 \(G=(V,E)\)，的割为一种点的划分方式：将所有的点划分为 \(S\) 和 \(T=V\ \backslash\ S\) 两个集合，其中源点 \(s\in S\)，汇点 \(t\in T\)，割的容量为 \(c(S, T)=\sum_{u\in S, v\in T}c(u,v)\)，最小割即 \(c(S,T)_{\min}\)。

算法

我们只要跑一遍最大流，即为最小割。

证明

见「最大流最小割定理」证明。

最大权闭合子图

定义

定义一个有向图 \(G=(V,E)\) 的闭合子图 \(G'=(V', E')\)，满足对于 \(∀(u,v)∈E\)，若 \(u∈V′\)，则 \((u,v)\in E', v∈V′\)。

最大权闭合子图即为对每个节点赋权值 \(val\)，所得到的最大 \(\sum\limits_{p\in V'}val_p\)。

算法

我们构造超级源点 \(s\) 和汇点 \(t\)：

• 对于 \(val_u > 0\)，在新图上连边 \((s, u, val_u)\)。
• 对于 \(val_u\le 0\)，在新图上连边 \((v, t, -val_v)\)。
• 对于 \((u,v)\in E\)，在新图上连边 \((u,v,+\infty)\)。

所有正权值之和减最小割即是答案。

证明

感性证明一下，首先对于原图中的边 \((u,v,+\infty)\) 不可能在最小割里面，然后我们令若 \((s,u,val_u)\) 选到了最小割集，就代表不选 \(u\)；若 \((u, t,-val_u)\) 选到了最小割集，就代表选 \(u\)。选出来的图必定是闭合子图，因为对于一个没选的正权点 \(u\)，因为原图除去割集不联通，所以 \(u\) 的所有负权后继与 \(t\) 之间的边必然在割集内，也就是已经选到了最终权值中。

那怎么保证最大呢？最小割保证损失节点权值（定义为负）和与负权权值之和最小，自然闭合子图总权值最大。

最大密度子图

定义

定义一个图 \(G=(V,E)\) 的密度为 \(\dfrac {|E|} {|V|}\)，则对于一个图 \(G=(V,E)\)，选出其一个子图 \(G'=(V', E')\)，使得密度最大，该图就是最大密度子图。

算法 1

我们考虑 0/1 分数规划，二分答案为 \(g\)，判断 \(\dfrac {|E'|} {|V'|}\ge g\)，即 \(|E'|-g|V'|\ge 0\)，于是我们只需要求 \(\max\{|E'|-g|V'|\}\) 即可。这里注意二分范围为 \(\left[\dfrac 1 n, m\right]\)，\(\epsilon=\dfrac{1}{n^2}\)，即最小子图密度之差为 \(\dfrac{1}{n^2}\)。

然后又有选了边 \((u,v)\) 又一定要选点 \(u,v\) 的限制，考虑最大权闭合子图的做法，建立超级源点 \(s\) 和汇点 \(t\)：

• 对于表示边的点 \(u\)，在新图上连边 \((s, u, 1)\)。
• 对于表示点的点 \(u\)，在新图上连边 \((u, t, g)\)。
• 对于 \((u,v)\in\)，在新图上连边 \((u,v,+\infty)\)。

跑一遍最小割，令 \(m\ge n\)，二分次数为 \(\log T\approx \log nm\)，时间复杂度即为 \(\mathcal O(m^3\log T)\)。

证明

算法正确性显然，唯一需要注意点的是，最终答案不可能会出现只选表示点的点而不选与之相连的边，因为最优答案一定是原图的导出子图。

算法 2

证明 1 中说明了最终答案一定是一个导出子图，于是我们尝试在原图中找出最小割，割出一个导出子图。

首先按照算法一做一遍 0/1 分数规划，再将 \(\max\{|E'|-g|V'|\}\) 转化为 \(\min\{g|V'|-|E'|\}\)，便于最小割，然后我们化一下式子：

\(\begin{aligned}g|V'|-|E'|=&\sum\limits_{u\in V'}g-\left(\dfrac{\sum\limits_{u\in V'}deg_u-c(V',\overline{V'})}{2}\right)\\=&\dfrac 1 2\left(\sum\limits_{u\in V'}(2g-deg_u)+c(S,T)\right)\end{aligned}\)

然后呢他有个神仙建图，从后往前推我不会，就先讲建图：

• 对于原图中的点 \(u\in V\)，在新图上连边 \((s,u,\Delta),(u,t,2g-deg_u+\Delta)\)。
• 对于 \((u,v)\in E\)，在新图上建边 \((u,v,1)\)。

最后求最小割，关系式为 \(|E'|-g|V'|=\dfrac{n\Delta-c(S,T)}{2}\)，我们发现 \(c(S,T)\) 和 \(|E'|-g|V'|\) 是线性关系的，这就说明了最小割正确性，这个关系式在下面给出证明。其中 \(\Delta\) 为偏移量，为了使边权非负，一般取 \(\Delta = n\)。

令 \(m\ge n\)，二分次数为 \(\log T\approx \log nm\)，时间复杂度即为 \(\mathcal O(n^2m\log T)\)。

证明

我们尝试推出 \(c(S,T)\) 的本质，令 \(V'=S\ \backslash\ \{s\}, \overline{V'}=T\ \backslash\ \{t\}\)。

\(\begin{aligned}c(S,T)&=\sum\limits_{v\in \overline{V'}}\Delta+\sum\limits_{u\in V'}(2g-deg_u+\Delta)+\sum\limits_{u\in V'}\sum\limits_{v\in \overline{V'}}c(u,v)\\ &=\sum\limits_{v\in \overline{V'}}\Delta+\sum\limits_{u\in V'}\left(2g+\Delta-\left(deg_u-\sum\limits_{v\in \overline{V'}}c(u,v)\right)\right)\\ &=\sum\limits_{v\in \overline{V'}}\Delta+\sum\limits_{u\in V'}\left(2g+\Delta-\sum\limits_{u\in V'}c(u,v)\right)\\ &=n\Delta+2g|V'|-2|E'|\end{aligned}\)

然后移个项就得到了 \(|E'|-g|V'|=\dfrac{n\Delta-c(S,T)}{2}\)。

DAG 最小不相交 / 可相交路径覆盖

定义

在一个有向无环图中选出若干条不相交的路径，使得每个点都属于一条路径，这种方案称为不相交路径覆盖，最小路径覆盖即为路径数最小的方案。

同理，在一个有向无环图中选出若干条路径，使得每个点都至少属于一条路径，这种方案称为可相交路径覆盖，最小可相交覆盖即为路径条数最小的方案。

算法

• 不相交路径

对于每个点 \(u\in V\)，拆成入点 \(u'\) 和出点 \(u\)，对于原图中 \((u,v)\in E\)，在新图中建边 \((u,v',1)\)，最终答案为总点数减去二分图 \(G=(X,Y,E)\) 的最大匹配，其中出点集合为 \(X\)，入点集合为 \(Y\)，时间复杂度 \(\mathcal O(m\sqrt n)\)。

• 可相交路径

我们发现链可以相交，尝试着转化为链不相交的做法。

我们对原图做一次传递闭包，这样路径就可以跳着走，也就是如果两条链相交，可以选择一条链跳过相交点，这样就转化为了不相交做法。然后其实最终的方案可以和可相交路径方案对应的。时间复杂度 \(\mathcal O(n^2(\dfrac n \omega+ \sqrt n))\)。

对于更普遍的情况，我们指定某些点必须被覆盖，将所有点分成两层 \((0,u)\) 和 \((1,u)\)，考虑以下建图方式：

• 对于必须被覆盖的点 \(u\)，连结 \((S, (0,u), 1)\) 和 \(((1,u), T, 1)\)
• 对于原图中的边 \((u,v)\) 在新图中连结 \(((0, u), (1, v), +\infty)\)；
• 对于所有点 \(u\)，连结 \(((1, u), (0, u), +\infty)\)

此时每条流量为 \(1\) 的可行流都代表路径中的一条边，用覆盖点总数 - 最大流即是答案，这里将图分成两层的原因是防止出现 \(S\overset{1}{\rightarrow}u\overset{1}{\rightarrow}t\) 的可行流。

证明

• 不相交路径

对于没有边的原图，答案显然是 \(|V|\)。而在新图中的每一条边 \((u,v')\)，都代表原图中的路径合并，且因为求的是最大匹配，所以路径一定合法。于是答案就为点数减合并最大次数。

• 可相交路径

显然。

定理

最大流最小割定理

最大流等于最小割。

证明

upd：这玩意儿别看了，不知道当时自己在证什么鬼东西，有空补一下吧。

显然对于任意割一定大于等于任意流，特别的，有 \(|f|_{\max}\le c(S, T)_{\min}\)。

然后对于任意割 \(c(S, T)=|f|\) 的情况，\(f\) 此时一定是最大流，因为割的容量等于割的流量，相当于原图中已经没有增广路径，即最大流。又因 \(|f|_{\max}\le c(S, T)_{\min}\le c(S, T)=|f|_{\max}\)，即可得 \(|f|_{\max}= c(S, T)_{\min}\)。

Kőnig 定理

二分图最小点覆盖为最大匹配。

证明方式 1

我们考虑一个不存在增广路的最大匹配 \(M\)，并如下对点做标记：每次从一个未被匹配的左部点走交错路径，即从左往右走未匹配边，从右往左走匹配边，走过的所有点都打上标记。

其中对于所有未标记的左部点和标记的右部点为最小点覆盖集 \(C\)，我们将分两步证明。

点覆盖集合法

• 对于一条匹配边，一定是右端点先被标记，然后遍历左端点被标记，所以一条匹配边刚好有一个点属于点覆盖集。

• 对于一条未匹配边，必然至少有一个点属于点覆盖集，否则其左部点已被标记而右部点未被标记，显然这是不符合的。

点覆盖集最小

首先肯定有 \(|C|\ge |M|\)，因为每个匹配边至少需要一个单独的覆盖点。

然后证明 \(|C|=|M|\)：

• 对于右部被标记的点，必然被匹配，否则可以和左部过来的点匹配。

• 对于左部未被标记的点，必然被匹配，特殊情况为孤立点，此时交错路径退化为单点。

以上证明了如此构造点集一一对应匹配边，且为最小点覆盖集。

证明方式 2

考虑转化成最小割形式，令左部点集合为 \(X\)，右部点集合为 \(Y\)，则有 \((s,u,1), u\in L\)，\((u,t,1),u\in R\)，\((u,v,+\infty),u\in L, v\in R\)。若得到最小割 \(c(S,T)_{\min}\)，这个最小割的容量即为 \(|X\cap T|+|Y\cap S|\)，因为不存在 \((u,v),u\in S, v\in T\) 被割。

于是我们构造点覆盖集合 \(P=|X\cap T|\cup|Y\cap S|\)，则所有 \((u,v),u\in S, v\in T\) 中 \(u,v\) 至少有一个在 \(P\) 中，否则不构成割集。所以最小割为最小点覆盖，又因最大匹配为最大流，最大流等于最小割，所以最小点覆盖为最大匹配。

霍尔定理

对于二分图 \(G=(X,Y,E)\)，\(\forall S\subseteq X,|S|\le N(S) \Leftrightarrow\) 二分图具有完美匹配，当然，\(|X|=|Y|\)。

推广定理：\(\forall S\subseteq X,m|S|\le N(S) \Leftrightarrow\) 二分图具有 \(m\) 组完美匹配。

首先如果有完美匹配，必然有 \(\forall S\subseteq X,|S|\le N(S)\)，剩下的有两种方式证明：

证明方式 1

首先原图没有完美匹配但是满足以上条件，我们在左部图 \(X\) 找到一个未被匹配的点，因为满足条件，所以右部与之相邻的点至少有一个且全部都一定被匹配，否则必定有更大的匹配。于是我们随便走到一个已经匹配的右部点，然后再走到相对应匹配的左部点，然后再随便找一个未走过的左部点，因为满足假设，我们最终一定停留在右部点。于是我们找到了一条增广路，不符合最大匹配。

证明方式 2

和 Kőnig 定理证明一样，如下连边：令左部点集合为 \(X\)，右部点集合为 \(Y\)，则有 \((s,u,1), u\in L\)，\((u,t,1),u\in R\)，\((u,v,+\infty),u\in L, v\in R\)，并得到最小割 \(c(S,T)_{\min}\)。

我们假设满足 \(\forall S\subseteq X,|S|\le N(S)\) 而二分图不具有完美匹配，则最大匹配 \(|M|<|X|\)，同时最小割 \(c(S,T)_{\min} < |X|\)。我们令 \(L_1=S\cap X\)，\(L_2=X\ \backslash\ L_1\)，\(R_1=N(L_1)\cap Y\)，则由 \(L_2\cap R_1\) 一定在割集内，又因假设满足，所以有 \(|L_1|\le |R_1|\)。得到关系式 \(c(S,T)_{\min}\ge |L_2\cap R_1|\ge|L_2\cap L_1|=|X|\)，与假设矛盾，得证。

二分图 Vizing 定理

对于二分图 \(G=(X,Y,E)\)，对每一条边染色，使得每个点所连的边颜色各不相同，若满足条件的最小颜色数为 \(\chi'(G)\)，点的最大度数为 \(\Delta(G) = \max\limits_{u\in V}deg_u\)，则有 \(\chi'(G)=\Delta (G)\)。

证明

考虑构造性证明。令颜色集合为 \(\{1,2,\dots, \Delta(G)\}\)，对于每个点 \(u\) 所连的边中，未被染的最小颜色编号为 \(C_u\)。

我们依次加入每一条边 \((u,v)\)：

• 对于 \(C_u=C_v\)，将边 \((u,v)\) 染成 \(C_u\) 颜色。
• 对于 \(C_u\not=C_v\)，令 \(C_u< C_v\)，则我们从 \(v\) 开始找到一条增广路，颜色为交替 \(C_u,C_v,C_u,\dots\)，将整条路颜色翻转，并将 \((u,v)\) 染成 \(C_u\) 颜色。

得证。

Dilworth 定理

在有向无环图中，最长反链等于最小链覆盖；其对偶定理为最长链等于最小反链覆盖。

注意：链不一定要连续，即链不等于路径

证明

对于原图，我们对其进行传递闭包，和求最小可相交路径覆盖一样，对于每个点 \(u\in V\)，拆成入点 \(u'\) 和出点 \(u\)，对于原图中 \((u,v)\in E\)，在新图中建边 \((u,v',1)\)，最小链覆盖即为总点数减最大匹配。

还有一个结论：原图最长反链为最大独立集，以下证明：

对于原图中的任意一个点 \(u\)，在新图中 \(u\) 和 \(u'\) 中必然至少有一个点在最大独立集中，否则必然存在 \((a,u')\) 和 \((u, b)\) 两条边，使得 \(a,b\) 都在最大独立集内，但如此原图便存在 \((a,b)\)，故不成立，所以最大独立集满足对于每个点在新图中的入点和出点尽可能多。显然对于这些点可以形成一组反链，因为最大独立集保证没有前驱和后继与原点相连，且这组反链可以和原图对应。

然后因为由「其他定理 1」可得二分图最大匹配 = 最大独立集补集，所以最小链覆盖等于最长反链。

其他定理

二分图最大匹配 = 最小点覆盖 = 最大独立集补集

证明

我们发现点覆盖 \(C\) 和独立集 \(I\) 的定义恰好相反，即 \(\forall (u,v)\in E,u\in C\vee v\in C\) 和 \(\not\exists (u,v)\in E,u\in I\wedge v\in I\)。所以最大独立集的补集，就保证了每条边都被覆盖。

根据「Kőnig 定理」，可得二分图最大匹配 = 最小点覆盖 = 最大独立集补集。

---

二分图最小边覆盖 = 点数减最大匹配

证明

很显然，对于最小边覆盖，我们希望一条边覆盖两个点的边数越多越好，即匹配数最大，于是最后总点数减去覆盖两个点的边即为最小边覆盖。

---

最大团 = 补图最大独立集

证明

最大独立集两两之间没有边，补图则两两之间有边，则为团。

\(\bf\sf 0x02\) 最小费用最大流

算法

SSP（基于 EK）

算法过程：

• 用 SPFA 跑出原图最短路（忽略无流量的边）并在过程中记录找到的一条增广路，直到不存在增广路。

时间复杂度：\(\mathcal O(nmf)\)。

zkw 费用流

*Capacity Scaling

咕。

\(\bf\sf 0x03\) 有源汇上下界最小 / 最小流

我们试图先找到一组可行流。对于无源汇，分别建出下界网络（\(w=L\)）和差网络（\(w=R-L\)），最终的可行流一定是下界网络和差网络的和。假设下界网络都是满流，但是流量不一定平衡，考虑在差网络上添加边。对于一个点 \(u\) 在下界网络上的 \(in_u\) 入流和 \(out_u\) 出流，如果入流比出流大，则添加 \((S, u, in_u - out_u)\) 的边，这样保证出去此边差网络的出流比入流大 \(in_u-out_u\)，反过来同理。如果附加边没有流满，则没有可行流。对于有源汇，源汇流量一定不平衡，则在源汇之间连一条流量为 \(\infty\) 的边即可。

我们找到一组可行流，则在差网络上从源到汇再跑一次最大流就是上下界最大流，同样的，从汇到原就是上下界最小流。

标签：原图,匹配,最大,覆盖,对于,flow,最小
From： https://www.cnblogs.com/notears/p/18540730