algorithm - 图论 - 全局最小割及其含义

Question

给定一个带权有向图，我们想要找到全局最小切割 - 即一组边，如果删除这些边将图分成两半，并且与任何其他此类切割相比，它们的总权重最小。

现在，尽管以下内容似乎可行，但有人告诉我推理是错误的。但坦率地说，我不明白也不确定他有多确定:

考虑由全局最小切割(即 s-t 切割，其中 s 在 U 中，t 在 V 中)分隔的节点集 U,V。注意:我们不关心从 V 到 U 的边。

对于任何 u in U, v in Vm，u-v-cut 不能小于 s-t-cut，否则，s-t-cut 不会是 (全局)最小。出于同样的原因，u 中的两个顶点之间或 V 中的两个顶点之间的切割不能更小。

另一方面，u-v-cut 也不能​​更大，否则，它需要包含一些边 U->V 而不是 s-t-cut 的一部分，这意味着 s-t- cut 根本就不是 cut。

因此，任意固定 s 并遍历所有其他顶点 x 就足够了。 s在U中，如果x在V中，则s-x-cut对应于全局最小值，或者如果 s 在 V 中并且 x 在 U 中，则 x-s-cut 会执行。如果它们都是同一组的一部分，则切割将至少与全局最小值一样大(但可能更大)。

因此，我们最终会通过计算两者来找到全局最小值，并跟踪到目前为止遇到的最小切割。

这对我来说似乎很有意义。我错了吗？如果是这样，为什么？

Answer 1

我的解释是您基本上是在问以下问题:

Can we find a global minimum cut by fixing an arbitrary vertex s and computing all s-t and t-s min cuts for all vertices t != s?

答案是肯定的，而且很容易证明:考虑一个值为 C 的全局最小割 (U, V)。那么要么 s 在 U 中，要么 s 在 V 中。

情况 1:s 在 U 中。根据最小割的定义，我们有 V != {}，因此 V 中有一个顶点 t。那么 (U, V) 是有效的s-t 割，所以最小的 s-t 割最多值 C

情况2:s在V中，那么U中存在一个顶点t，同上论证最小t-s割

此算法描述为例如 in Chapter 6.4 of these MIT lecture notes .