我想在具有整数容量的流网络 G 中的所有最小切割中找到包含最少边数的切割。我们如何修改 G 的容量以创建一个新的流网络 G'，其中 G' 中的任何最小割都是 G 中边数最少的最小割。来源 - Cormen
问问题
333 次
1 回答
3
可以说图G有n顶点。
我们将对应于弧的弧e'的容量定义为。G'eGc(e') = c(e) * n + 1
因此，切入的值G'恰好是切入n的值的乘以切入G的边数。
假设我们现在有一个最小切入G'value n * x + a。这意味着切入的G值为x。如果存在G具有较小值的y < x切入，则该切入的值将与具有值的切入最小n * y + b <= n * (y+1) <= n * x < n * x + a这一事实相矛盾。我们刚刚证明了每个最小切入也是一个最小切入。但随之而来的是，最小切入是最小切入，并且具有所有最小切入的最小边数。n * x + aG'G'GG'GG
于 2017-06-13T16:26:43.447 回答