4

让 G = (V, E) 是一个网络，其中 s 和 t 是源和汇。设 f 是 G 中的最大流。找到一个算法来确定 G 中是否存在唯一的最小割。

我设法在这个网站上找到了一个类似的问题：

确定最小切割的唯一性

那里给出的答案摘要：

在残差图中找到从 s 可达的所有顶点，我们在 G 中找到了一个最小割 (S,T)。

查看相同的残差图，从 t 开始。以箭头的相反方向查看从 t 可到达的顶点组（表示可以到达 t 的所有顶点）。

这组也是最小切。

如果该剪辑与您的原始剪辑相同，则只有一个。否则，您只找到了 2 个剪辑，所以原来的剪辑不可能是唯一的。

我不明白为什么如果剪辑与原始剪辑相同，那么剪辑就是独一无二的。谁能向我们保证没有其他最小切割？

提前致谢

4

4 回答 4

7

实际上，我不太了解该解决方案。但在最初的问题中，davin 提供的第二个答案是绝对正确的。

我只是复制粘贴到这里

Given a minimum S-T cut, (U,V) with cut-edges E', we make one simple observation:
If this minimum cut is not unique, then there exists some other minimum cut with 
a set of cut-edges E'', such that E'' != E'.

If so, we can iterate over each edge in E', add to its capacity, recalculate the
max flow, and check if it increased.

As a result of the observation above, there exists an edge in E' that when
increased, the max flow doesn't increase iff the original cut is not unique.

我自己的一些解释：

你实际上需要证明的是 

there exists an edge in E' that when increased, the max flow doesn't increase
<=>
the original cut is not unique

=>：
你将边的容量增加e1，计算新的最大流量，它保持不变，这意味着它e不在新的最小切割中。（如果e在，根据最小割的性质，f(e)=e的容量，这导致增加）。由于e不在新的最小割中，它也是原图的最小割，与我们知道的割具有相同的体积。因此，原始割不是唯一的。

<=：
原始剪切不是唯一的（我们称它们为Eand E'），这意味着您可以找到e在 inE但不在的边E'。然后你只需将容量增加e1。在计算新图的最小切割时，E'已经存在。由于E'不包含 edge e，因此 max flow 毫无疑问保持不变。

希望你能理解 ：）

于 2013-12-23T11:46:41.133 回答
1

您谈到的算法比建议的算法更有效。算法：

对于图 G=(V,E)

  1. 求图中的最大流量，令 R 为最后一个残差图。
  2. 从 s 运行 BFS（查找从 s 可到达的节点），我们称它们为 X
  3. 从 t 用反向边运行 BFS（找到有到 t 的路径的节点），我们称它们为 Y。
  4. 如果 X + Y = V ('+' as in union) 返回 TRUE，否则返回 FALSE

一个简短的解释：

在第 2 步中，我们找到确定最小割 (X, V/X) 的节点。X 是我们最后一个残差图中从 s 可到达的所有节点的集合。在步骤 3 中，我们在最后一个残差图中找到 t 可以到达的节点集。该集合定义了最接近 t 的最小切割 (VY,Y)。在第 4 步中，从两端（X + Y = V）进行相同的切割，则图具有唯一的最小切割。

复杂性主要是找到最大流量。使用 Edmonds Karp O(|E|^2|V|) 和 BFS O(|E| + |V|)。

建议答案的复杂度为 O(|V||E|^3)。

于 2018-02-20T15:20:23.830 回答
1

通过矛盾证明第一种方法的另一种选择：->：假设有一个带有切边 E' 的最小 (S,T) 切。在将属于 E' 的边 e 的容量增加 1 并发现最大流量保持不变后，导致 e 不在新的最小割中。（如果 e 在 E' 中，根据 min-cut 的性质，最大流量会增加）。然而一开始我们说 e 在 E' - 矛盾

于 2017-01-28T23:56:06.233 回答
0

到目前为止，对原始帖子中提出的算法的所有讨论（这里和复制它的帖子中的 d ）似乎都没有真正证明如果两个最小切割相同，那么它就是唯一的最小值切。但这并不难！

好的，那么这两个最小削减是多少？我们运行最大流量算法并查看残差图。第一个切割是 (S,T=VS)，其中 S 是仅使用具有剩余容量的边可以从源到达的所有节点的集合。第二个切点是 (VT,T)，其中 T 是仅使用具有剩余容量的边可以到达汇的所有节点的集合。

如果这两个切割不同，那么显然不止一个最小切割。但是如果它们相同，那么我们可以使用 laike9m 描述的技术来证明这是唯一的最小割。为什么？好吧，根据上一段中 S 和 T 的定义，切割中的每条边 e=(v0->v1) 都有一条路径 s->v0 和一条路径 v1->t 具有剩余容量。因此，如果我们增加 e 的容量，我们知道我们将增加最大流量。由于这对于切割中的每条边 e 都是正确的，这意味着这个最小切割是唯一的。

于 2020-12-23T20:28:59.000 回答