DSA 最大流

最大流问题

最大流问题是关于在一个有向图中，找到从一个点到另一个点的最大流量。

更具体地说，流量来自源顶点 \(s\)，最终到达汇顶点 \(t\)，图中的每条边都定义了流量和容量，容量是指该边所能拥有的最大流量。

找到最大流可能非常有用

• 用于规划城市道路以避免未来的交通拥堵。
• 评估移除供水管道、电缆或网络电缆的影响。
• 找出流网络中扩展容量将带来最高最大流的位置，目的是增加例如交通、数据流量或水流量。

术语和概念

流网络通常是指有流量流过的有向图。

边的容量 \(c\) 告诉我们允许通过该边的流量是多少。

每条边还有一个流量值，表示该边的当前流量。

上图中的边 \( v_1 \rightarrow v_2 \)，从顶点 \( v_1 \) 到顶点 \( v_2 \)，其流量和容量描述为 0/7，表示流量为 0，容量为 7。因此，这条边的流量最多可以增加到 7，但不能再多。

最简单的形式，流网络有一个源顶点 \(s\)，流量从这里流出，一个汇顶点 \(t\)，流量在这里汇集。其他顶点只是让流量通过。

对于除 \(s\) 和 \(t\) 之外的所有顶点，都有流量守恒，这意味着进入顶点的流量必须与离开顶点的流量相同。

最大流是通过 Ford-Fulkerson 或 Edmonds-Karp 等算法找到的，通过在流网络中的边上发送越来越多的流量，直到边的容量使得不再能发送更多流量。这样一条可以发送更多流量的路径称为增广路径。

Ford-Fulkerson 和 Edmonds-Karp 算法是使用一种称为残余网络的工具来实现的。这将在接下来的页面中更详细地解释。

残余网络用每条边的残余容量设置，其中边的残余容量是该边的容量减去流量。因此，当一条边的流量增加时，其残余容量就以相同的数量减少。

对于残余网络中的每条边，还有一个反向边，其方向与原边相反。反向边的残余容量等于原边的流量。反向边对于在最大流算法中将流量沿某条边发送回很有用。

下图显示了本页顶部模拟图中的反向边。每条反向边都指向相反的方向，并且由于一开始图中没有流量，因此反向边的残余容量为 0。

这些概念中的一些，例如残余网络和反向边，可能很难理解。这就是为什么在接下来的两页中将更详细地解释这些概念并提供示例。

当找到最大流时，我们会得到一个关于流网络总共可以发送多少流量的值。

多个源顶点和汇顶点

Ford-Fulkerson 和 Edmonds-Karp 算法需要一个源顶点和一个汇顶点才能找到最大流。

如果图中存在多个源顶点或多个汇顶点，则需要修改图以找到最大流。

要修改图以便可以在其上运行 Ford-Fulkerson 或 Edmonds-Karp 算法，如果存在多个源顶点，则创建一个额外的超级源顶点；如果存在多个汇顶点，则创建一个额外的超级汇顶点。

从超级源顶点，创建到原始源顶点的边，容量为无穷大。类似地，从汇顶点创建到超级汇顶点的边，容量也为无穷大。

下图显示了这样一个图，其中有两个源 \(s_1\) 和 \(s_2\)，以及三个汇 \(t_1\)、\(t_2\) 和 \(t_3\)。

要在该图上运行 Ford-Fulkerson 或 Edmonds-Karp，会创建一个超级源 \(S\)，并与原始源节点之间建立容量为无穷大的边；同时创建一个超级汇 \(T\)，并与原始汇节点之间建立容量为无穷大的边。

Ford-Fulkerson 或 Edmonds-Karp 算法现在可以通过从超级源 \(S\) 到超级汇 \(T\) 的路径，找到具有多个源顶点和汇顶点的图中的最大流。

最大流最小割定理

要理解这个定理，我们首先需要知道什么是割。

我们创建两个顶点集：一个仅包含源顶点，称为“S”，另一个包含所有其他顶点（包括汇顶点），称为“T”。

现在，从源顶点开始，我们可以通过包含相邻顶点来扩展集合 S，并继续包含相邻顶点，只要不包含汇顶点即可。

扩展集合 S 将缩小集合 T，因为任何顶点都属于集合 S 或集合 T。

在这种设置下，当所有顶点都属于集合 S 或集合 T 时，集合之间就存在一个“割”。割由所有从集合 S 指向集合 T 的边组成。

如果我们加总从集合 S 指向集合 T 的所有边的容量，我们就得到了割的容量，这就是该割中从源到汇的总可能流量。

最小割是具有最低总容量的割，这将是瓶颈。

下图中，对本页顶部模拟图中的图进行了三种不同的割。

割 A：此割的集合 S 中包含顶点 \(s\) 和 \(v_1\)，其他顶点属于集合 T。此割中离开集合 S 的边（从汇到源）的总容量为 3+4+7=14。我们不计算边 \(v_2 \rightarrow v_1\) 的容量，因为这条边是反向的，从汇到源。因此，穿过割 A 的最大可能流量为 14。

割 B：割 B 的最大可能流量为 3+4+3=10。

割 C：割 C 的最大可能流量为 2+6=8。如果我们检查图中的所有其他割，都不会找到容量更低的割。这就是最小割。您是否运行过本页顶部的最大流模拟？那么您也知道 8 是最大流，这正是最大流最小割定理所说的。

最大流最小割定理表明，找到图中的最小割与找到最大流是相同的，因为最小割的值将与最大流的值相同。

最大流最小割定理的实际意义

使用 Ford-Fulkerson 等算法找到图中的最大流也有助于我们理解最小割在哪里：最小割将是边已达到满容量的地方。

最小割是瓶颈所在，因此如果我们想增加超过最大限制的流量，这在实际情况中很常见，那么我们现在就知道图中的哪些边需要修改才能增加整体流量。

修改最小割中的边以允许更大的流量在许多情况下都非常有用

• 可以实现更好的交通流量，因为城市规划者现在知道在哪里创建额外的车道，在哪里重新规划交通，或者在哪里优化交通信号。
• 在制造业中，可以通过针对瓶颈进行改进来提高产量，例如升级设备或重新分配资源。
• 在物流中，了解瓶颈在哪里，可以通过更改路线或增加关键点的容量来优化供应链，确保商品更有效地从仓库运往消费者。

因此，使用最大流算法找到最小割，可以帮助我们理解系统在哪里可以进行修改以允许更高的吞吐量。

最大流问题的数学描述

最大流问题不仅仅是计算机科学中的一个主题，它也是一种数学优化类型，属于数学领域。

如果您想在数学上更好地理解这一点，以下将用数学术语描述最大流问题。

图中所有边 (\(E\))，从顶点 (\(u\)) 到顶点 (\(v\))，其流量 (\(f\)) 小于或等于该边 (\(c\)) 的容量

\[ \forall (u,v) \in E: f(u,v) \leq c(u,v) \]

这基本上意味着边的流量受该边的容量限制。

此外，对于所有边 (\(E\))，从 \(u\) 到 \(v\) 的单向流量与从 \(v\) 到 \(u\) 的反向负流量相同

\[ \forall (u,v) \in E: f(u,v) = -f(v,u) \]

下面的表达式说明，除了源顶点 (\(s\)) 和汇顶点 (\(t\)) 之外，所有顶点 (\(u\)) 都保持流量守恒

\[ \forall u \in V \setminus \{s,t\} \Rightarrow \sum_{w \in V} f(u,w) = 0 \]

这基本上意味着进入顶点的流量与离开该顶点的流量相同（源顶点和汇顶点除外）。

最后，所有离开源顶点 \(s\) 的流量都必须在汇顶点 \(t\) 处结束

\[ \sum_{(s,u) \in E} f(s,u) = \sum_{(v,t) \in E} f(v,t) \]

上面的等式说明，将所有流出源顶点边的流量相加，将得到与将所有流入汇顶点边的流量相加相同的总和。