5

我有一个边加权无向图和 2 个节点（通常称为源和汇）。我需要找到一组可能权重最小的边，将这 2 个节点分成 2 个弱分量。

我知道Ford-Fulkerson 的最大流算法和他关于有向图上的最大流和最小割关系的定理。

我还知道 Ford-Fulkerson 的无向图最大流算法的修改，它用 2 个相反的有向边替换每个无向边，并同时更新流向它们的流。但是通过这种修改，max-flow-min-cut-theorem 似乎不再有效，因为在以下无向图中，将无法正确确定最小切割：

nodes: 0, 1, 2, 3
edges & capacities: {0,1}->5, {0,2}->6, {1,2}->2, {1,3}->7, {2,3}->4
source: 0
sink: 3

最大流最小割定理说，最小割是那些边，流动等于它们的容量，而通过修改后的福特-富克森就是所有的边，这显然不是正确的割。

我找到了一个Stoer–Wagner 算法，用于在无向图中找到全局最小割，但这不是我想要的，因为该算法不考虑任何源和汇，并且可以找到一个让节点位于的割相同的组件。

是否有任何算法可以有效地在具有源和汇的无向图中找到最小割，将这两个指定节点分开？我可以以某种方式修改前面提到的算法以使它们适用于我的情况吗？

4

2 回答 2

0

最大流最小切定理说，最小切是那些边缘，其流量等于它们的容量......

这是不正确的。你已经给出了一个反例。这篇文章给出了从最大流中找到最小切割的正确算法。我在这里引用它。

最小切割是将节点分成两组。

一旦找到最大流，就可以通过创建残差图来找到最小割，当从源遍历这个残差网络到所有可达节点时，这些节点定义了分区的一部分。将此分区称为 A。其余节点（不可达的节点）可以称为 B。最小割的大小是原始网络中从 A 中的一个节点流向 A 中的节点的边的权重之和B.

因此，正如您所说，您可以将每条边转换为 2 个相反的有向边，计算新图中的最大流量，然后使用上面的算法将最大流量转换为最小切割。

于 2021-07-20T08:16:37.470 回答
0

您可以使用 Ford-Fulkerson 算法的一些修改。

  1. 首先，您需要找到源和接收器之间的最大流量并记住它。
  2. 从图中删除一些边。
  3. 然后你需要在新图中找到最大流量。如果最大流量与第一步不同，则该边缘处于最小切割中。
  4. 将边返回到图形，选择另一条边并转到第 2 步。

当您找到最大流量时，只需将无向边视为具有相同容量的两条有向边。

于 2016-04-27T04:01:57.490 回答