最大流 push-relabel 算法相关的一个习题

[olist]

算法导论习题 26.5-5：Suppose that at some point in the execution of a push-relabel algorithm, there exists an integer 0<k<=|V|-1 for which no vertex has v.h=k. Show that all vertices with v.h>k are on the source side of a minimum cut.
想了很久也没有证明出来。

知道答案了，大致说下思路给以后可能需要的读者。
首先可以根据 k 将所有的点分成左右两部分（左边点的高度大于 k ），同时得到一个割（ cut ） c 。由于此时的残留网络（ residual network ）中只有从右到左的边，我们已经找到了一个预流（ preflow ） pf，相应的有一个流（ flow ） f，它们的在 c 上的净流量等于从左到右的总容量。据此，我们可以把左边的所有点合并成一个新的源点，新图的一个最大流也是原图的一个最大流，同时新图的任一个最小割也是原图的一个最小割，左边的所有的点在原图的最小割的左侧。