Chapter 26, Problem 5P

(a)

Program Plan Intro

To argue that a minimum cut of graph $G$ has capacity at most $C\left|E\right|$ .

(b)

Program Plan Intro

To explains the finding of augmenting path having capacity of at least $K$ in $O(E)$ time.

(c)

Program Plan Intro

To argue the statement that MAX-FLOW-BY-SCALING returns a maximum flow.

(d)

Program Plan Intro

To explain the capacity of a minimum cut of the residual network $Gf$ is at most $2K\left|E\right|$ each time when line 4 is executed.

(e)

Program Plan Intro

To argue the statement that the inner while loop of line 5-6 executes $O(E)$ times for each value of $K$ .

(f)

Program Plan Intro

To explain the MAX-FLOW-BY-SCALING can be implemented so that it runs in $O(E^2\lg C)$ time.