所有边缘的边缘容量增​​加1后,图表的最小切割是否相同？

Question

令G =(V,E)为任意流网络,每个边e具有源s和目标t以及正整数容量c(e).设(S,T)相对于这些容量是最小st cut.现在假设我们将每个边缘的容量增加一个,即所有边缘的c_new(e)= c(e)+ 1,那么(S,T)相对于这些新容量{c_new}仍然是最小的切割？

我的直觉是,如果G包含不同容量的边缘,增加的容量可能导致不同的最小切割.但是当所有边缘具有相同的容量时,最小切割将保持相同.

我对么？怎么证明这个？

Answer 1

是的,你的直觉是正确的.

当G包含不同容量的边时,将每个边的容量增加1 可能会改变最小切割.通过示例可以很容易地证明这一点,如下所示.最小切割(红色)具有容量3.增加每个边缘的容量增加,切割为6.因此从S到A的连接成为容量为5的新的最小切割.

当所有边缘具有相同的容量时,将每个边缘的容量增加1 将不会改变最小切割.证明背后的基本思想是,切口的容量是nc其中n是的边缘切口的数量,并且c是每个边缘的容量.由于c是常数,因此最小切割是最小切割n.我们将这个最小值称为N.

现在,如果每条边的容量增加1,则每次切割的新容量为n(c+1).因此,曾经是最小切割的新切割能力是N(c+1).假设容量大于N(c+1)存在的切口:由于所有边缘都有重量c+1,因此M对于某些人来说,这样的切割必须是切边M > N.但是在原始图表中,这个相同的切割将具有容量Mc > Nc,与那里的N-edge切割是最优的假设相矛盾,因此不存在这样的M切割,这意味着N-edge切割(现在具有容量N(c+1))在新的切割中保持最佳状态图形.

Answer 2

如果所有边缘容量增​​加一个常数，则最小切割是相同的。假设图中的边容量相同。否则可能会改变。

一个简单的解释是 -

我们使用 BFS 通过 dinic 算法计算最小割/最大流。我们应用从源到接收器的 bfs，并减去 bfs 路径中的最小容量/瓶颈容量边缘。我们添加这个edge-wt。流动。我们继续这个过程，直到没有从源到汇的路径。

如果您将边缘容量增​​加一个常数，则切割将始终保持不变。因为该算法的所有迭代中的 BFS 路径都是相同的。只有最大流量值会改变。