检查一些边缘是否穿过一些最小切割

Question

我正在努力解决以下问题（实际上是解决方案）：

Given G(V,E), a flow-network (capacities are integers), We denote the maximum-flow by f*. Check for an edge e if:
1. It crosses some minimal-cut.
2. It crosses every minimal-cut.

解决方案建议：

1. 将边e的容量减少1并检查新的最大流量是否等于f*-1。 return 如果是，则为真。
2. 将边 e 的容量增加 1 并且 return 为真当且仅当最大流量增加了。

如果你能向我解释一下这个算法背后的想法，我会很高兴。

谢谢

Answer 1

来自 wikipedia:

the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in the minimum cut, i.e. the smallest total weight of the edges which if removed would disconnect the source from the sink.

1. 如果 e 确实穿过最小割，这意味着它是一组边缘之一（我们称之为 c_group）：

   A) 如果从图中移除，源和汇将不再连接（它们之间没有路径）

   和B）它们的权重之和（我们称它为c_sum）是最小的（没有一组边满足（A）并且具有更小的和）。

   当我们减少图中的 e's weight by 1, from (A) we know c_group is a cut, and from (B) we now that c_sum was the minimal value of a cut (sum of its edges' 权重时，现在 c_group 的值当然是 c_sum-1 因为 e 在 c_group 并且我们减少了它的权重 1。所以我们知道 c_sum-1 是图中新的最小切割值（即使 e 属于其他切割，它只能在一个切割中出现一次，所以它的权重减少意味着它所属的每个切割都得到了减少 1，因此最小切割值不能减少超过 1）。从max-flow min-cut定理我们知道，新的min-cut值意味着新的max-flow值是相同的(c_sum-1).

   另一方面，如果 e 没有穿过最小割，那么它穿过的每个割都不是最小的，这意味着组的权重总和大于最小割的值。因为我们只有整数值的权重，这意味着它们都比最小值至少大 1，所以当我们将 e 减少 1 时，它穿过的每个切口都会减少到变化前的最小切割值或更高的值，这意味着最小值没有被减少改变，并且通过最大流最小切割定理意味着最大流没有改变。

   所以现在我们知道，如果我们将 e 的值减少 1，我们可以检查最大流量值以及它是否发生变化（减少了 1）那一定意味着 e 确实越过最小值。

2. 我会在这里不详细介绍，但如果您仍然难以评论，我也会扩展它：

   当我们增加 e 的值时（这里增加多少并不重要）它会改变图中切割的最小值当且仅当它是图中每个最小切割的一部分.很明显，它增加了它所属的每个组的总和，并且如果有一组边构成一个最小切割（（1）中的条件（A）+（B））则e 不属于 然后增加其权重不会改变该组的权重总和，因此不会改变图中切割的最小值。从最大流最小切割定理可以得出，图中的最大流量增加，当且仅当 e 是图中每个最小切割的一部分。

注意：在将边缘组视为切割和将切割视为边缘交叉的假想线之间，我在这个答案中的语言有点交替。这种混淆来自问题中引用问题的不兼容语言和开始我的回答的引用定理。如果它混淆了任何人，我很抱歉。基本上 "cut" 在整个答案中都指代它们。