DSA 最大流

最大流问题

最大流问题是关于寻找通过有向图的最大流，从图中的一个位置到另一个位置。

更具体地说，流量来自源顶点 \(s\)，最终到达汇点 \(t\)，图中的每条边都定义了流量和容量，其中容量是该边可以承受的最大流量。

寻找最大流非常有用

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

术语和概念

流量网络 通常被称为有向图，其中有流量流过它。

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

每条边还有一个流量值，它告诉我们该边的当前流量是多少。

上图中从顶点 \( v_1 \) 到顶点 \( v_2 \) 的边 \( v_1 \rightarrow v_2 \) 的流量和容量描述为 0/7，这意味着流量为 0，容量为 7。因此，该边的流量可以增加到 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) \]

上面的等式指出，将所有从源顶点流出的边的流量加起来，将得到与所有进入汇点顶点的边的流量加起来相同的和。