令 G = (V,E) 是一个任意流网络，具有源 s 和目标 t 以及每条边 e 的正整数容量 c(e)。令 (S,T) 是关于这些容量的最小 st cut。现在假设我们将每条边的容量增加一，即所有边的 c_new(e) = c(e) + 1，那么 (S, T) 是否仍然是这些新容量 {c_new} 的最小 st 切？
我的直觉是，如果 G 包含不同容量的边，容量的增加可能会导致不同的最小切割。但是当所有边都具有相同的容量时，最小切割将保持不变。
我对么？如何证明这一点？
问问题
10670 次
3 回答
10
是的，你的直觉是正确的。
当 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，这样的割必须是-边割。但是在原始图中，这个相同的切割将具有容量，这与-edge 切割在那里是最优的假设相矛盾，因此不存在这样的 -edge 切割，这意味着-edge 切割（现在具有容量）在新的图形。MM > NMc > NcNMNN(c+1)
于 2016-10-27T07:14:16.720 回答
2
如果所有边缘容量都增加一个常数，那么最小切割是相同的。假设图中的边容量相同。否则可能会改变。
一个简单的解释是——
我们使用 BFS 通过 dinic 算法计算 min-cut/max-flow。我们将 bfs 从源应用到接收器，并减去 bfs 路径中的最小容量/瓶颈容量边缘。我们添加这个边缘重量。流动。我们继续这样做，直到没有从源到接收器的路径。
如果您将边缘容量增加一个常数，则切割将始终保持不变。由于该算法的所有迭代中的 BFS 路径都是相同的。只有最大流量值会改变。
于 2016-10-27T06:40:54.627 回答
0
如果所有边的容量都相同，则问题等于：“如果所有边的容量都乘以一个正数，则最小割保持不变。（A） ”很容易证明（A）。这个问题应该是(A)的一个特例，其中所有边缘容量都乘以c+1/c。
于 2019-05-14T09:06:58.460 回答