图论 - 全局最小割及其含义
Graph Theory - globally minimal cut and its implications
给定一个加权有向图，我们想要找到全局最小切割 - 即一组边，如果删除这些边，则将图分成两半，并且与任何其他此类边相比总重量最小切.
现在，尽管以下似乎可行，但有人告诉我推理是错误的。但坦率地说，我不明白也不确定他有多确定：
考虑由全局最小切割（即 s-t 切割，其中 s in U, t in V）分隔的节点集 U,V。注意：我们不关心从 V 到 U.
的边
对于任何 u in U, v in Vm，u-v-cut 不能小于 s-t-cut，否则，s-t-cut 不会（全局）最小。出于同样的原因，u中的两个顶点之间或V中的两个顶点之间的切割不能更小。
另一方面，u-v-cut 也不能更大，否则，它需要包含一些边 U->V 不是 s-t-cut 的一部分，这意味着 s-t-cut 没有切割完全没有。
因此，任意固定 s 并遍历所有其他顶点 x 就足够了。 s 在 U 中，如果 x 在 V 中，则 s-x-cut 对应于全局最小值，或者在 s 中，x-s-cut 对应于全局最小值在 V 中，x 在 U 中。如果它们都是同一组的一部分，则切割将至少与全局最小值一样大（但可能更大）。
因此，我们最终会通过计算两者来找到全局最小值，并跟踪到目前为止遇到的最小切割。
我觉得很有道理。我错了吗？如果是，为什么？
我的解释是，您基本上是在问以下问题：
Can we find a global minimum cut by fixing an arbitrary vertex s and computing all s-t and t-s min cuts for all vertices t != s?
答案是肯定的，而且很容易证明：考虑一个全局的 min-cut (U, V)，其值为 C。那么要么 s 在 U 中，要么 s 在 V 中。
情况1：s在U中。根据最小割的定义，我们有V != {}，所以V中有一个顶点t。那么(U, V) 是一个有效的 s-t 切割，所以最小 s-t 切割的价值最多为 C
情况2：s在V中，则U中存在一个顶点t，同上论证最小t-s割
给定一个加权有向图，我们想要找到全局最小切割 - 即一组边，如果删除这些边，则将图分成两半，并且与任何其他此类边相比总重量最小切.
现在，尽管以下似乎可行，但有人告诉我推理是错误的。但坦率地说，我不明白也不确定他有多确定：
考虑由全局最小切割（即 s-t 切割，其中 s in U, t in V）分隔的节点集 U,V。注意：我们不关心从 V 到 U.
对于任何 u in U, v in Vm，u-v-cut 不能小于 s-t-cut，否则，s-t-cut 不会（全局）最小。出于同样的原因，u中的两个顶点之间或V中的两个顶点之间的切割不能更小。
另一方面，u-v-cut 也不能更大，否则，它需要包含一些边 U->V 不是 s-t-cut 的一部分，这意味着 s-t-cut 没有切割完全没有。
因此，任意固定 s 并遍历所有其他顶点 x 就足够了。 s 在 U 中，如果 x 在 V 中，则 s-x-cut 对应于全局最小值，或者在 s 中，x-s-cut 对应于全局最小值在 V 中，x 在 U 中。如果它们都是同一组的一部分，则切割将至少与全局最小值一样大（但可能更大）。
因此，我们最终会通过计算两者来找到全局最小值，并跟踪到目前为止遇到的最小切割。
我觉得很有道理。我错了吗？如果是，为什么？
我的解释是，您基本上是在问以下问题：
Can we find a global minimum cut by fixing an arbitrary vertex s and computing all s-t and t-s min cuts for all vertices t != s?
答案是肯定的，而且很容易证明：考虑一个全局的 min-cut (U, V)，其值为 C。那么要么 s 在 U 中，要么 s 在 V 中。
情况1：s在U中。根据最小割的定义，我们有V != {}，所以V中有一个顶点t。那么(U, V) 是一个有效的 s-t 切割，所以最小 s-t 切割的价值最多为 C
情况2：s在V中，则U中存在一个顶点t，同上论证最小t-s割