图论算法：最大流与最小割⚓︎
约 5719 个字 9 张图片 预计阅读时间 19 分钟
照例，先上链接
- 首先推荐jyy（yyds！）老师的B站教程。目前中文教程中我所见的讲授最大流/最小割效果最好、信息含量够大、信息密度够高的。本篇笔记不过是对上述这个短短1h的授课视频的拙劣模仿。
这个笔记会从几个部分展开。我很早以前就想写这部分内容了。没想到2024年都快结束了才堪堪开始。首先你需要知道，最大流问题实际上可以认为是最小费用流的一个特例（可参考最小费用流的拓展。而最小费用流又可以视作一种线性规划问题的特例。我们会在后面简单讨论一下这个对偶问题的形式与含义）。
- 基础定义；以及从找路径到“割”；
- 如何从“找最多不重复路径”过渡到最大流；
- 为什么增广路径法在这个问题上是有效可行且正确的；
- 从最大流回归到线性规划
- 从线性规划回归到对偶，以及一种松弛的和紧凑的对偶形式；
现在我们开始。
S-T 割与路径存在的判定⚓︎
通过深度优先搜索和广度优先搜索，我们可以在一个给定的图中找到从节点 \(s\) 到节点 \(t\) 的路径。我们简单标记一下。图 \(G = (V,E)\), 起点 s，终点 t。一条路径 \([s, p_1, p_2, p_3, ... , t]\)。
现在，我们考虑这样一个问题。我们知道如果 \(s,t\) 之间能够找到路径，那么一定可以被 DFS/BFS 找到，那如果不存在路径呢？我们怎么证明的确不存在一个从 \(s\) 到 \(t\) 的路径呢？
我们可以考虑如下的情况：
由瞪眼法。注意到，左图中，\(s\) 到 \(t\) 的路径是存在的，而右图中是不存在的。
我们可以下意识地想到一个笨方法。比如我们可以写出所有的从 \(s\) 到 \(t\) 的路径排列，而先不考虑路径中的边是否存在。比如：
\(s \rightarrow t\)
\(s \rightarrow a \rightarrow b \rightarrow t\)
\(s \rightarrow d \rightarrow c \rightarrow t\)
甚至 \(s \rightarrow d \rightarrow c \rightarrow a \rightarrow b \rightarrow t\)... 你可以想象出很多很多种排列。
如果存在一个路径，比如左图中的 \(s \rightarrow a \rightarrow b \rightarrow c \rightarrow t\)，你会发现这个路径中的每一个边都出现在图的边中。（比如, \(s \rightarrow a, a \rightarrow b, b \rightarrow c, c \rightarrow t\)，而如果在右图中，你会发现，任意一个排列中，都==至少有一个边不存在于原来的图中==。
但是，这个证明毫无疑问地太长了，我们不可能总是去求所有“边的排列”吧？
所以，我们需要回顾一下BFS，DFS实际上是在干什么。我们都是从起点出发，根据它能到达的点延伸“已访问到的节点”，这样不断地拓展节点集合，直到能访问到终点。Done！终止。
我们可以发现这里是有2个节点集合的，一个是“已访问到的”，一个是“没访问到的”。
现在，我们需要引入这部分一个非常重要的概念：有向图的 S-T 割。
S-T割：将图中所有节点分成两个集合\(S,T\)，其中起点 \(s\) 必须处于 \(S\) 集合中，终点 \(t\) 必须处于集合 \(T\) 中。这就是一个“割”。我们定义割的大小就是 \(S\) 中的点向 \(T\) 中节点的连边的个数。
举个例子，上面左图中令 \(S = \{s, a, b, d \}, T = \{ c, t \}\)。这就是一个割。诶，此时边 \(b \rightarrow c\) 就是唯一一个从 \(S\) 通向 \(T\) 中节点的连边。这个割的大小就是 1.
再举个例子，上面右图中，令 \(S = \{s, a, b, d \}, T = \{ c, t \}\)。这就是一个割。此时你会发现，找不到一个边从 \(S\) 通往 \(T\)了。这个割的大小是 0.
这个时候你或许能够回答一个问题：割的作用是什么。
你或许发现了，上述DFS/BFS找不到路径的割就是一个大小为0的割。
或者这样理解。我们再回到那个“笨办法”：列举所有的排列，由于\(S-T\)割把所有节点分成2部分，起点一定在\(S\)中，终点一定在\(T\)中。假设，s-t之间真的存在一个路径，那么对于这个路径中的每一条边，都肯定会发生一次“一个边的相邻节点，一个处在 \(S\)，一个处在 \(T\) 中”。
反过来，如果找到一个大小为0的割，就能说明这个路径不是通路了。因为它没法从你现在的 \(S\) 通到 \(T\) 中了，由于 T 中包含了终点t，你也就不可能抵达终点了。
总之，你可以用“割”来“证明路径是否存在”。你只要找到了一个大小为 0 的割，那么这两个点之间一定不存在路径。
最多有多少条不相交的路径？⚓︎
现在我们进入下一个具体的问题。给定图和起终点后，我们想知道图中有多少不相交的从 \(s\) 到 \(t\) 的路径。
这里补充一下“不相交”的定义是什么：如果两条路径没有共同的边，那么就认为这两条路径是不相交的。
如下左图中。你可以发现，无论路径： \(s \rightarrow a \rightarrow b \rightarrow c \rightarrow t\) 还是 \(s \rightarrow d \rightarrow b \rightarrow c \rightarrow t\)，都需要经过 \(b \rightarrow c\) 这条边。所以这两条路径是相交的。只能找到一条不相交路径。这个 \(b \rightarrow c\) 就像是瓶颈(bottleneck)一样。
图2
反之，右图中，你可以找到 \(s \rightarrow a \rightarrow b \rightarrow c \rightarrow t\) 和 \(s \rightarrow a \rightarrow d \rightarrow b \rightarrow t\) 两条路径，是不重叠的。
好。这是个很小的图，如果说是个很大的图，找最大的不相交路径就显得有点太难了。我们不妨把这个最优化问题转化成一个“判定问题”。比如，我们想判断是否能找到 \(k\) 条从 \(s\) 到 \(t\) 的不相交路径呢？
上面我们判断能否找到从 \(s\) 到 \(t\) 的路径，其实就在解决 \(k = 1\) 的特殊情况。
如果 \(k = 2\) 呢？或者更大呢？
我们把目光转到“割”上来。你可以发现一个有意思的情况。
举个例子！
上面的图2的左图。我们能找到一个割 \(S = \{s, a, b, d \}, T = \{ c, t \}\)。这个割的大小是 1。此时，哪怕我们能在S集合中找到100种不同的路径，在T集合中也找到100个不同的路径，我终归只能通过 \(b\rightarrow c\) 这条边通往 \(T\) 集合中的点，就像一个独木桥！这个瓶颈（独木桥） 导致了，我最多只能找到1条不相交的路径。因为要想从\(S\)到\(T\)，都只有这一条路，如果有2条或者更多路径，那一定会重复使用 \(b\rightarrow c\) 的。
再举例子，上面的图2的右图。我们能随手找到一个割 \(S = \{s, a, b, d \}, T = \{ c, t \}\)。这个割的大小是 2。这导致，我最多只能找到2条不相交的从 \(s\) 到 \(t\) 的路径（至多2座独木桥）。因为在这个割下，统共只有2条边能从 \(S\) 中的点通到 \(T\) 中的点。我们顶多把这两条边全站满了！现在你再想增加一个路径，它势必要使用这两个边中的任意一个，如果用了，那它肯定和现有的2个路径之一是相交的了。 所以，至多只有2条路径。
这里还要补充一句，如果你随手找到了一个大小为 \(2\)，或者更大的割，不代表这个图就真的存在一个路径了！你可以参考图1的左图。我们的割 \(S = \{s\}, T = \{ a, b, d , c, t \}\) 的大小是2，但是这个图并不存在\(s-t\)路径！
所以，我们总结一下。如果我们随手找呀找，在图里找到一个大小为 \(l\) 的 S-T 割。那么至多只有 \(l\) 个不重复的路径。割的大小实际上提供了一个“上界”。我们先记住这个结论。
现在我们回到那个 “找不相交路径” 的问题上。
想一想，让你用手算来找不相交的路径，你会怎么做？
你一般会先找到一个路径，然后剔去这路径上所有的边，对残余的图继续寻找。也就是：
- 用DFS/BFS在 \(G(V,E)\) 中找到一条路径 \(P\)
如果找不到路径，结束！
- \(G \leftarrow (V, E \setminus P)\)，循环。
比如对于图二的右图：
我们一眼瞪出来： \(s \rightarrow a \rightarrow b \rightarrow c \rightarrow t\) 和 \(s \rightarrow a \rightarrow d \rightarrow b \rightarrow t\) 两条路径，是不重叠的。
但是如果我们一眼瞪出来了 \(s \rightarrow d \rightarrow a \rightarrow b \rightarrow c \rightarrow t\)，你堪堪把这些边删掉，你的残余网络就变成：
，
图3
你就找不到第二条不相交路线了！
有没有一种办法总是能尽可能多地找到不相交路径，哪怕是我们选了“错”的路的情况下。也就是，我们希望从图4的左图（只有一个不相交路径），改成图4右图的情况呢？
图4
我们先说做法，最后会证明为什么这种做法是正确的纠错。
假设我们先选中了 \(s \rightarrow d \rightarrow a \rightarrow b \rightarrow c \rightarrow t\)。我们已经找到1个不相交路径了。我们此时把这个路径中所有的边全部反向。也就是图变成如下左图的情况：
现在，我们在这个变化过了的图里继续寻找，能不能从\(s\)到\(t\)。
很显然是能找到的，如下右图。这相当于我们多找到了1个不相交路径。也就是2条不相交路径了。
此时我们再把这次找到的这个路径的所有边反向，如下右图所示。
好了，这下彻底找不到可以从\(s\)到\(t\)的路径了。如果你注意力比较好，你会发现我们这么一番折腾，最开始找的那个“错”路径的 \(d \rightarrow a\) 被纠正回来了，变成了原来图中的样子，因为找到2个不相交路径的解中，并不需要这条多余的边。我们完成了纠错。
接下来是我最喜欢的一个环节。
我们想知道，为什么在反向后的残留网络上找到一个路径，就一定能找到一个新的不相交路径呢？
可以用上图进行可视化。证明完毕。
（还是解释一下吧）
我们一开始有\(k\) (图中\(k=3\)条路径)，从 \(s\) 到 \(t\)。现在我们通过反转原来的所有路径的边，成了第二个的情况，也就是中间的图。我们在这个图中，找到了一个新的路径。这个路径==可能经过某些反转后的边==（比如和黑线重叠的红线），也可能包含某些原先就有的、尚未被经过的边（比如不和黑线重叠的那部分红色的边），总之，就像中间这个图一样歪歪扭扭，但是毕竟找到了这样一条路径。
现在，我们把“经过的反转的那些边”擦除，仅仅保留没有经过的，但是又被反转了的边，这次给它扭正过来，我们绝对可以画出右图所示的这样一条路径。这就是为什么“如果在反向后的残留网络上能够找到一个路径，那么就一定能找到一个新的不相交路径。”
我太爱这个无字证明了。所以我一定要亲手把这个图画下来。
我第一次看jyy的讲解看到这部分的时候真的拍桌直呼：太牛了吧...
总结一下
上述操作的细节是：
- 对于已经走过的边，允许它们“推一段”回去；
- 对于没走过的边，允许继续走；
- 以此重新寻找路径；
这实际就是Ford-Fulkerson 算法最经典的“反转路径、形成增广路径(augmenting path)”操作。虽然我们目前还没有提到“最大流”。
我们可以用上面的方法，每次找到新路径就反转，直到不能再找到路径为止，这样一直操作，直到残余网络中找不到一个 \(s\) 到 \(t\) 的路径了，终止。
你可能会问，我们是否真的求的得了最大数量的不相交路径呢？
答案是肯定的。Proof:
假设最大不相交路径的数量为 \(k\)。现在我们找到了 \(m\) 条不同的路径，肯定有 \(m \leq k\)。此时，我们一定可以找到一个大小为 \(m\) 的割。为什么？
因为我们可以直接考虑这样一个割： \(S = \{ s\}\), \(T\) 为除了\(s\)外其他所有节点的集合。因为我们有 \(m\) 个不相交路径了，那么一定有 m 个不同的边从 \(s\) 流出，也就是从 \(S\) 流出到\(T\) 中。这就是一个大小为 \(m\)的割。
如果你还记得，割的大小决定了“不相交路径的上界”。 那么，我们一定有 \(k \leq m\)。
夹逼准则，两头堵！
于是：
\(m \leq k \leq m\)
所以我们这时候得到的路径数 \(m\)，就是我们想要找的那个 \(k\)。那个“最大数量的不相交路径”。
再换句话说，我们整个图里，所有的割中，最小割的大小，就是不相交路径的数量。
原始的线性规划形式及建模⚓︎
现在，我们终于可以从“找不相交路径的最大数量”推广到“有权值的图”上来，就得到了最大流问题。
比如，如果我们假设，下图右图 中，从s到a点，权重是20，那么我们就看作这两个点之间有20条不同边，其权重都是1。以此类推。此时我们同样可以求从 \(s\) 到 \(t\) 的不相交路径的最大数量，依然是成立的。一个简单的例子如下。
我们可以把每个边的权重想象成“容量”，把每个路径流过这个边的权重想成“流量”，也就是有多少条流量可以经过这一条边，还不超过容量限制。如果说在加权图中，这个边的权重是20，那么最多有20条路径（更准确说，是20个大小的流量）可以流经这个边，如果权重是283.21，说明最多有283.21个大小的流量可以选择这个边。以此类推。
不妨写出所有从 s 到 t 的路径都写出来。比如：
\(P_1 = s \rightarrow a \rightarrow b \rightarrow t\)
\(P_2 = s \rightarrow c \rightarrow d \rightarrow t\)
\(P_3 = s \rightarrow c \rightarrow d \rightarrow b \rightarrow t\)
\(P_4 = s \rightarrow a \rightarrow c \rightarrow d \rightarrow b \rightarrow t\) ...
此时如果我们希望流量尽可能的大，其实也就是选择尽可能多的路径，同时不违背容量限制。
那么我们可以给每个路径设置一个流量。
比如，我们设 \(P_1\) 的流量为 \(x_1\)，以此类推。
\(\max x_1 + x_2 + ... + x_p\)，这里的 \(p\) 是所有的 \(s\) 到 \(t\) 的路径数。注意，这种建模方式中的路径数有指数多个，因此是一个很冗余繁琐的模型。但是它对于我们理解很有帮助。后面我们会提到更加紧凑的数学模型。
\[\begin{aligned}
\begin{cases}
\begin{align}
x_1 + x_4 + ... + &\leq 20 \\
x_2 + x_3 + ... &\leq 10 \\
... \\
x_i \geq 0,\forall i
\end{align}
\end{cases}
\end{aligned}\]
这里的约束 (1)，含义就是，所有包含了 \(s \rightarrow a\) 这条边的路径，其流量之和不能超过20。同理，约束 (2) 的含义就是，所有包含了 \(s \rightarrow c\) 这条边的路径，其流量之和不能超过10。以此类推。
上面也提到，决策变量有指数多个，很明显是很差劲的，但是为什么要专门提出来呢？因为这是网络流问题在优化语言描述下，最原始的形式。 它很基本、很原始地刻画了在容量限制下，对路径进行叠加，以找到尽可能多地从 \(s\) 到 \(t\) 的不相交路径 这样一个过程。
基于路径模型的完整形式
设 \(P\) 是从起点 \(s\) 到终点 \(t\) 的所有路径。\(x_i\) 是路径 \(i \in P\) 的流量。是一个连续型变量。我们用参数 \(a_{ik}\) 表示路径 \(i \in P\) 是否经过边 \(k\)，如果是，则为1，否则为0。记图中所有的边集合为 \(E\)，其中边 \(k\) 的容量限制是 \(c_k\)。那么，我们可以写出如下线性规划模型：
\[\max \sum_{i \in P} x_i\]
s.t.
\[\begin{aligned}
\begin{cases}
\sum_{i \in P} a_{ik} x_i \leq c_k,\forall k \in E \\
\end{cases}
\end{aligned}\]
现在，我们终于要回到运筹学课本上讲述的“网络流”的定义了。其实，那只不过是考虑了环流等更多情况下，该问题的一个简化（不再以路径为决策变量进行建模了）。
更加紧凑（经典）的网络流线性规划的建模⚓︎
如果不再以路径为决策变量进行建模，而是直接关注“每个边究竟应该流多少流量”这个核心问题，我们该怎么建模呢？(这部分主要就是抄书了)
同样以上图中的网络为例。我们记边 \((i,j)\) 的流量为 \(x_{ij}\)。你首先需要观察到一个很重要很重要的性质：
流平衡
什么意思呢，就是除开了 \(s\) 和 \(t\) 之外，其他所有节点，其流入的流量一定等于流出的。为什么呢？因为，除了 \(s\) 和 \(t\) 之外，其他所有节点，都是中间节点，既不是起点，也不是终点，我们不会在中间节点有流量的损失（否则我们就一定可以通过把这个流量补上，找到一个更大的流了呀！），我们也不会在中间节点有流量的增加（中间节点不会平白无故生产流量！）。
具体而言，以 \(a\) 节点为例， \(x_{sa} = x_{ab} + x_{ac}\), 以c节点为例，\(x_{sc} + x_{ac} + x_{bc} = x_{cd}\)。以此类推。有多少个节点（除了起终点），就有多少个流平衡！
我们把完整的、基于网络流而不是基于路径的、紧凑的建模写在这里。
给定图 \(G = (V,E)\) 以及起点 \(s\)，终点 \(t\)。设 \(x_{ij}\) 是边 \((i,j) \in E\) 上的流量。是一个连续型变量。我们用集合 \(\Omega^+(i)\) 表示流入节点 \(i \in V\) 的节点集合，用集合 \(\Omega^-(i)\) 表示流出节点 \(i \in V\) 的节点集合。那么，我们可以写出如下线性规划模型：
\[\max \sum_{j \in \Omega^-(s)} x_{sj}\]
s.t.
\[\begin{aligned}
\begin{cases}
\begin{align}
\sum_{j \in \Omega^+(i)} x_{ij} = \sum_{j \in \Omega^-(i)} x_{ji},\forall i \in V \setminus \{s,t\} \qquad \\
x_{ij} \geq 0, \forall (i, j) \in E \qquad
\end{align}
\end{cases}
\end{aligned}\]
对上述两个线性规划的对偶问题的整理⚓︎
做运筹相关整理，一直想对所有经典问题的对偶情况进行一些粗浅的分析。我们开始吧。
基于路径的LP的对偶⚓︎
我们先讨论那个笨拙的、基于路径的线性规划问题。
不言而喻地，对偶问题的决策变量是从原问题的约束条件入手的。 原问题的约束条件，对应的是每个边的容量限制。所以记图中有 \(|E|\) 条边，我们的对偶问题就有 \(|E|\) 个决策变量。记 \(y_k\)。如果你想具体一点，可以逐一罗列地写成：\(y_{sa}, y_{ab}, y_{bc}\) 等以此类推的形式。同样地，我们应该注意到，设原问题有 \(|M|\) 个决策变量，那么对偶问题就对应了 \(|M|\) 个约束条件。（注意这有指数多个约束，但是无妨，我们不会去解这个问题的）
Furthermore，原问题的每一个决策变量都对应了一个（对偶问题的）约束，因为这个决策变量是针对“某条路径”的，所以在对偶问题的语境下，这个约束也是针对“某条路径”而给出的，它的右端项始终为1。但是系数矩阵 ...
记得我们之前有 “用参数 \(a_{ik}\) 表示路径 \(i \in P\) 是否经过边 \(k\)”，那么在对偶语境下，倒过来，就是：边 \(k\) 是否被路径 \(i\) 所经过——其表示依然可以用 \(a_{ik}\) 这个参数！
我们先写好对偶问题的目标函数：\(\min \sum_{k \in E} c_k y_k\)。
我们再写约束条件：
\[\begin{aligned}
\begin{cases}
\begin{align}
\sum_{k \in E} a_{ik} y_k \geq 1,\forall i \in P \qquad \\
y_k \geq 0, \forall k \in E \qquad
\end{align}
\end{cases}
\end{aligned}\]
防止理解不了这个约束，我还是拿上图的例子来讲：
对第一个路径 \(s \rightarrow a \rightarrow b \rightarrow t\)，我们写出来的第一个约束就是： \(y_{s,a} + y_{a,b} + y_{b,t} \geq 1\) 以此类推。
那么回过头来看这个对偶问题，你做的事情实际上是，在每个边都已赋予一个权重的情况下，要求一个 \(y_k\)。我们假设令 \(y_k \in \{ 0, 1\}\)，就是要在所有的路径（路径反正是由边组成的，每个边有其权重）中，选一些边出来，使得选出来的边，其能够覆盖所有的路径（这也就是为什么，有路径个约束，同时约束是 \(\geq 1\)）的前提下，还能使得权重最小。
如果你的直觉足够强，你可以想象成下图所示，左侧每个长线都表示一个从 \(s\) 到 \(t\) 的路径，因为它们由不同的边组成，所以每一段的权重各有不同（以不同颜色表示）。而我们的最终解就是下面右图所示的那样。
这些选出来的边，也就构成了一个最小的割。 这就是为什么，在本质上，最大流和最小割是互为对偶，又冥冥之中互有联系的原因。
基于网络流的LP的对偶⚓︎
推荐链接：https://theory.stanford.edu/~trevisan/cs261/lecture15.pdf。等有空再补充好。