Consider the following simple network with edge capacities as shown

Step 1 of 6

(a)

The maximum flow in a graph from the start vertex to the sink vertex can be computed by using the Ford-Fulkerson algorithm. According to the Ford-Fulkerson algorithm, the flow increases at least one unit per iteration. The algorithm terminates after iteration. Here is the sum of capacities leaving source and. The running time of this algorithm is.

Given the network, . The maximum flow graph theorem states that: There exists a flow network with real capacities such that Ford-Fulkerson does not terminate. Thus, the values of the flows found may converge to some value arbitrarily far from the max flow.