Exercise 26.5-5

Because every vertex v, |V|+1 > h[v] > k can not reach sink. Hence, we can set the height to |V|+1.

Exercise 26.5-4

We can prove the times we call the nonsaturating push, and we use the distance funcion d instead of height function h. Let K = . For a node v, let d’(v) = || / K. Set the potential function = . We divide the algorithm into phase, the phase is between consecutive change  of d* = . We can classify the phases into two category: cheap and expensive. Cheap phase contains at most K nonsaturating push. We know there are at most cheap phase, and every expensive will decrease the potential function by K. The time complexity will become .

Exercise 26.5-3

It is valid, but the relabel operation may not create admissible edge. Hence the time complexity will increase.

Exercise 26.5-2

Iit is the same as relabel to front algorithm

Exercise 26.5-1

Exercise 26.4-9

By the result of lemma 26.24, the total number of nonsaturating pushs is less than = , because |V| < |E| for all graph |V|≥4.

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 .