By the result of lemma 26.24, the total number of nonsaturating pushs is less than 
May 10, 2009
Exercise 26.4-9
Exercise 26.4-8
The shortest path will change only after saturated push. If the saturating push occurs, we can recalculate the shortest path by BFS.
Exercise 26.4-7
If h(u)≥|V| and h(u) -|V| < δ(u,s), that is, the length of shortest path P from u to s is greater than h(u) – |V|. Because any edge in residual network has height difference one, the height of u is at least |V| + length(P) > h(u), it is a contradiction. The another argument can be proved by the same argument.
Exercise 26.4-6
If we change the line 7 of INITIALIZE-PREFLOW, we need also modify the definition of height. Moreover, we must reproof the lemma 26.18 as follows. If we can find a augmenting path from s , u … t, the height of u must be greater than the s, because we saturated the edge (s,u) in the first iteration of algorithm. That is, height(u) is at least |V|-1, and we can get a contradication in the same argument of orginal proof.
Exercise 26.4-5
For one edge (u,v), we can push from u or v at least one unit at a time, so after k times push the edge will become saturated and the height of u or v might be relabeled. Hence the times of push is at most O(k|V||E|), and the total complexity is 
Exercise 26.4-4
Model bipartite matching as maximum flow problem and run push-relabel algorithm. The time complexity is 
Exercise 26.4-3
Fisrtly, find h, 0 < h < |V| such that there is no vertex v with height h at termination. We collect vertex whose height greater than h as S, S and V-S will be minimum cut.
Exercise 26.4-2
Because we can exmine a edge (u,v) from either relabel(u) or relabel(v) and height(u) or height(v) can change at most O(V) times. Hence, the algorithm spends a total of only O(|V||E|) time.
Exercise 26.4-1
Push and relabel operations are straightforward. We can maintain a queue to record all overflowing vertex. For one overflowing vertex, we can do either push or relabel.
