algorithm - 最大流量最小切割

Question

假设有一个流网络 G=(V,E)，其中 c : E->R+ 作为容量函数，我们可以找到最小割 (A,B)。如果我们删除切割的边缘，即从 A 到 B 的转发边缘，会发生什么？如果有人能指出我的答案，我将不胜感激，在此先感谢。

Answer 1

你会发现你已经删除了一个最小割，并且没有从 A 到 B 的正容量边 --- 特别是，如果你在 A 中选择一个顶点 a，在 B 中选择一个顶点 b，则没有从 a 的路径到 b 在每条边上都有正容量。