我想找到，在具有积分能力的流网络G中的所有最小切割中，其中包含最小数量的边缘。我们如何修改G的能力以创建一个新的流网络G'，其中最小切割G'的最小切割是G。Cormen中的最小值。看答案假设图G有n顶点。我们定义了弧的能力e'在G'对应于弧e在G作为c(e')=c(e)*n+1.因此，削减的价值G'完全是n时间削减的价值G+切口中的边缘数。可以说我们现在最低限度G'有价值n*x+a。这意味着削减的价值G是x。如果有削减G价值较小y这个削减的价值n*y+b这与以价值削减的事实矛盾n*x+a最低限度G'。我们刚刚证明了每一个最低限度G'也是最小切割的G。但是随后，最小切入G'最小切入G并具有所有最