Standard 14: Max Flow 2: Ford-Fulkerson

Short description: Execute the Edmonds-Karp algorithm on examples; identify complexity.

Full description

Given a max flow input instance, execute Edmonds-Karp on the instance. Recall the runtime complexity of Edmonds-Karp. Explain the difference between Ford-Fulkerson and Edmonds-Karp.

Example problem

Run the Edmonds-Karp algorithm on the following graph. If there are multiple choices for an augmenting path, you can pick any of them.

An example graph. Source s, sink t, and capacities on the edges: c(s,v)=4, c(s,w)=9, c(w,v)=7, c(w,x)=3, c(v,x)=5, c(v,t)=2, c(x,t)=9.

In each round, give the following things:

The flow $f$, drawn as a graph, and the amount $|f|$.
The residual flow $r_f, G_f$, drawn as a graph (see above).
The augmenting path and the augmentation amount $d$.

Sample solution

Example Solution.

First round:

Flow: $|f| = 0$.

Residual flow:

Residual capacity equals original capacity on edges of the graph.

Path: $s,v,t$. Amount: $2$.

Second round:

Flow: $|f| = 2$.

Label 2/4 on (s,v). Label 0/9 on (s,w). Label 0/7 on (w,v). Label 2/2 on (v,t). Label 0/5 on (v,x). Label 0/3 on (w,x). Label 0/9 on (x,t).

Residual flow:

2 on (s,v), 2 on (v,s). 9 on (s,w). 7 on (w,v). 2 on (t,v). 5 on (v,x). 3 on (w,x). 9 on (x,t).

Path: $s,v,x,t$. Amount: $2$.

Third round:

Flow: $|f| = 4$.

Label 4/4 on (s,v). Label 0/9 on (s,w). Label 0/7 on (w,v). Label 2/2 on (v,t). Label 2/5 on (v,x). Label 0/3 on (w,x). Label 2/9 on (x,t).

Residual flow:

4 on (v,s). 9 on (s,w). 7 on (w,v). 2 on (t,v). 3 on (v,x), 2 on (x,v). 3 on (w,x). 7 on (x,t), 2 on (t,x).

Path: $s,w,x,t$. Amount: $3$.

Fourth round:

Flow: $|f| = 7$.

Label 4/4 on (s,v). Label 3/9 on (s,w). Label 0/7 on (w,v). Label 2/2 on (v,t). Label 2/5 on (v,x). Label 3/3 on (w,x). Label 5/9 on (x,t).

Residual flow:

4 on (v,s). 6 on (s,w), 3 on (w,s). 7 on (w,v). 2 on (t,v). 3 on (v,x), 2 on (x,v). 3 on (x,w). 4 on (x,t), 5 on (t,x).

Path: $s,w,v,x,t$. Amount: $3$.

Fifth round:

Flow: $|f| = 10$.

Label 4/4 on (s,v). Label 6/9 on (s,w). Label 3/7 on (w,v). Label 2/2 on (v,t). Label 5/5 on (v,x). Label 3/3 on (w,x). Label 8/9 on (x,t).

Residual flow:

4 on (v,s). 3 on (s,w), 6 on (w,s). 4 on (w,v), 3 on (v,w). 2 on (t,v). 5 on (x,v). 3 on (x,w). 1 on (x,t), 8 on (t,x).

Path: no path exists from $s$ to $t$. Stop.

Final amount of flow: $|f| = 10$.

Rubric

Rubric.

To pass, a solution must follow the course requirements for writing.

To pass, a solution must correctly implement Edmonds-Karp. It must give a legible, correct drawing of the flow and the residual graph at each round, using the conventions of the class. For the flow graph, edges must be labeled as flow/capacity. For the residual graph, edges must be labeled with their residual capacity and edges must only be present if they have nonzero residual capacity.

The numerical rubric for this problem is:

4 (Pass, Near-Perfect): correct, clear, well-presented.
3 (Pass, Proficient): correct, possibly not fully clearly presented in some cases. Perhaps a correct answer but with a minor arithmetic mistake that is carried through and the algorithm is otherwise correct.
2 (Fail, Progress): incorrect or not clearly presented. May contain multiple mistakes or significant mistakes that alter the result. May have a misunderstanding of one or more definitions.
1 (Fail, Wrong Track): Does not appear to be applying the algorithm or drawing the necessary diagrams.