91Ó°ÊÓ

The principle behind the method is that the transmit flow down one of the pathways from the source (start node) to the sink (end node), as long as there is adequate capacity on all edges of the path. Then we discover a new way, and so on. An augmenting route is one that has available capacity

(a)

The Ford-Fulkerson algorithm is to find the maximum flow by searching for incremental paths in the residual graph. If the incremental path found for the first time is $S→B→A→T$by continuing the routine, then the incremental flow would be $S→B→A→T$. So that only one incremental path with flow 1 is found each time and a total of to iterate 2000 times.

Therefore, the total of 2000 iteration.

(b)

The Dijkstra’s algorithm can be used here depending on the fact that if a capacity of the path is $s→K→r→t$is equal to c or greater than c.

Consider that cp(v) be the capacity value of all paths from s to v. Initialize cp(v) to 0 and then the Dijkstra’s algorithm can be modified as follows,

for all edges$\left(u,v\right)∈E:$

$$\begin{gathered} \mathrm{if}cp\left(v\right)<\min \left(cp\left(u\right),c\left(u,v\right)\right) \\ cp\left(v\right)=\min \left(\mathrm{cp}\left(\mathrm{u}\right),\mathrm{c}\left(\mathrm{u},\mathrm{v}\right)\right) \\ \mathrm{K} \end{gathered}$$

Therefore, It has been shown that the fattest s - t path in a graph can be computed by a variant of Dijkstra’s algorithm.

(c)

Consider a graph G(V,E), that has a minimum cut, that each cut edge e corresponds to exactly a path $p_e$that is equal to $c\left(e\right)$.The sum of the $p_e$is the maximum flow because the number of cut edges $\left|E\right|$will not exceed the number of paths.

Therefore , it can be seen as the maximum flow that cannot be aggregated by more than $\left|E\right|$edge paths.

(d)

Consider the graph that the graph G(V,E) with the largest flow F, that can be summed up by not more than E paths. Then the flow of the fattest path must not be less than $\frac{F}{\left|E\right|}$. Consider the maximum flow be C co-graph after the $t^{th}$iteration, the relation is obtained as follows,

$c_{t+1}≤-\frac{c_t}{\left|E\right|}$

Therefore, the number of iterations are $O\left(\left|\mathrm{E}\right|\mathrm{logF}\right)$.