最小总容量削减

Question

在下面的网络中，数字表示边的容量。这是一个网络流量问题。本题要求的是 minimum total capacity cut. 我的讲师的答案，如图所示，用红色的抖动线表示，是 。

The minimum total capacity cut contains arcs {AB, SC, SE} as shown.

我的答案是： {SA, SC, EF}. 我基本上也是这样做的，只是我避免了边角料 SA 并使用 EF 而非 AB. 为什么我错了？

Answer 1

流量仍然可以通过S->E->C->D->T，所以你的一组边甚至不是切口。

切口是一组边缘，一旦去掉就不可能发生从S到T的流动。

请记住，移除边缘并不会移除顶点本身。

这里有一个简单的方法来获得最小切割。

• 在残图上运行任何一个最大流量算法（Ford-Fulkerson, EdmondsKarp, Dinic等）。
• 从源节点开始做BFS，忽略饱和边(流量值=边容量的边)
• 现在把所有从访问过的节点到未访问过的节点的边都取为
• 这些边缘将是可能的最小切割之一。