最小总产能削减
Minimum total capacity cut
在下面的网络中，数字表示边的容量。是网络流量问题。该问题要求 minimum total capacity cut。我讲师的答案，如图中红色波浪线所示，是：
The minimum total capacity cut contains arcs {AB, SC, SE} as shown.
我的答案是{SA, SC, EF}。我基本上也在做同样的事情，只是我避免使用边缘 SA 并使用 EF 而不是 AB。为什么我错了？
流仍然可以通过 S->E->C->D->T，因此您的边集甚至不是一个切口。
切割是一组边，一旦删除，就不可能发生从 S 到 T 的流动。
请记住，移除边并不会移除顶点本身。
这是获得最小割的简单方法：
- 运行 残差图上的任何最大流算法（Ford-Fulkerson，Edmonds
卡普、迪尼克等）
- 从源节点执行 BFS，忽略饱和边
（流量值 = 边容量的边）
- 现在取所有的边
从已访问节点到未访问节点
- 这些边将是可能的最小切割之一
在下面的网络中，数字表示边的容量。是网络流量问题。该问题要求 minimum total capacity cut。我讲师的答案，如图中红色波浪线所示，是：
The minimum total capacity cut contains arcs {AB, SC, SE} as shown.
我的答案是{SA, SC, EF}。我基本上也在做同样的事情，只是我避免使用边缘 SA 并使用 EF 而不是 AB。为什么我错了？
流仍然可以通过 S->E->C->D->T，因此您的边集甚至不是一个切口。
切割是一组边，一旦删除，就不可能发生从 S 到 T 的流动。
请记住，移除边并不会移除顶点本身。
这是获得最小割的简单方法：
- 运行 残差图上的任何最大流算法（Ford-Fulkerson，Edmonds 卡普、迪尼克等）
- 从源节点执行 BFS，忽略饱和边 （流量值 = 边容量的边）
- 现在取所有的边 从已访问节点到未访问节点
- 这些边将是可能的最小切割之一