给定一个加权有向图，我们希望找到全局最小割——也就是说，如果删除一组边，将图分成两半，并且与任何其他此类割相比，它们的总权重最小。
现在，尽管以下似乎可行，但有人告诉我推理是错误的。但坦率地说，我不明白他是如何确定的，我不确定他有多确定：
U,V考虑由全局最小割（即 st-割，其中s in U, t in V）分隔的节点集。注意：我们不关心从V到的边缘U。
对于任何u in U, v in Vm uv-cut 不能小于s-t-cut，否则，st-cut 不会（全局）最小。出于同样的原因，两个顶点之间的切口u或两个顶点之间的切口V可以更小。
另一方面，uv-cut 也不能更大，否则，它需要包括一些U->V不属于 st-cut 的边缘，这意味着 st-cut 根本没有切割。
因此，s任意固定并遍历所有其他顶点就足够了x。s是 in U，则 sx-cut 对应于全局最小值 if xis in V，或者 xs-cut 对应于 if sis inV和xis in U。如果它们都是同一集合的一部分，则切割将至少与全局最小值一样大（但可能更大）。
因此，我们最终将通过计算两者来找到全局最小值，并跟踪迄今为止遇到的最小割。
这对我来说似乎很有意义。我错了吗？如果是这样，为什么？