无向图中分离源和汇的最小割算法是什么？

Question

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

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

我还知道一个修改后的Ford-Fulkerson最大流算法用于无向图，它将每个无向边替换为2个相反的有向边，并同时更新它们的流。但是，使用此修改后，最大流-最小割定理似乎不再有效，因为在以下无向图上，最小割将无法正确确定：

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

最大流最小割定理表明，最小割就是那些边的流量等于它们的容量，并且通过修改后的Ford-Fulkerson算法得到所有这些边，但这显然不是正确的割。

我发现在无向图中有一个Stoer-Wagner算法用于寻找全局最小割，但这并不完全是我想要的，因为该算法不考虑任何源和汇，并且可以找到一种割，使节点在同一组件中。

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

- Youda008

---

将您的图形转换为有向图，通过用每个方向的2条边替换每个无向边，如何？ - Sam Segers

@SamSegers：这对于流程是有效的，但对于剪切不再适用了，我会尝试在问题中提供更多信息。 - Youda008

@Youda008：为什么这不能用于找到切割本身？ - SivanBH

Answer 1

你可以使用修改后的Ford-Fulkerson算法。

1. 首先，您需要找到源和汇之间的最大流，并记住它。
2. 从图中删除一些边。
3. 然后，您需要在新图中找到最大流。如果最大流不同于步骤一，则此边缘位于最小割中。
4. 将边缘返回到图形，选择另一个边缘并转到步骤2。

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

- 107th

---

我认为这不会起作用。如果您删除任何带有非零流量的边缘，则全局流量将始终发生变化。 - Youda008

Answer 2

最大流最小割定理指出，最小割是那些边的流量等于它们的容量...这不正确。您已经给出了一个反例。从最大流中找到最小割的正确算法在this post中给出。我在此引用它。

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

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

- xskxzr