Homework Assignment 5, due June 3 11:59PM
1 Last (5th) homework assignment
Work is to be your own. If you do use outside sources or help, be sure to cite them carefully.
1.1 Network Flow 1 (40 pts)
Show your knowledge of the Ford Fulkerson Network Flow Algorithm by carefully carrying out the steps on the graph pictures below. Use the Edmonds-Karp heuristic, which is the rule that each augmenting path should use as few edges as possible. Indicate your sequence of steps. State the current flow amount after each augmenting path.
v4v 12
142 9 16 7
st
v1 v2
13
2418s t v3 v4
6 v3 v4
v1 v2 v1 v2
stst
v3 v4 v3 v4
v1 v2 v1 v2
stst
v3 v4 v3 v4
1.2 Running Time (10 pts)
What is the (published) big-Oh running time for the above version of network flow on a graph with n vertices and m edges?
CMPS 132 Spring, 2018 1 Handout 26
Homework Assignment 5, due June 3 11:59PM
1.3 Network Flow 2 (40 pts)
Show your knowledge of the Ford Fulkerson Network Flow Algorithm by carefully carrying out the steps on the graph pictures below. Use the rule that each augmenting path should use as few ¡°reverse arcs¡± as possible. Indicate your sequence of steps.. State the current flow amount after each augmenting path.
v4v 12
142 9 16 7
st
v1 v2
13
2418s t v3 v4
6 v3 v4
v1 v2 v1 v2
stst
v3 v4 v3 v4
v1 v2 v1 v2
stst
v3 v4 v3 v4
1.4 Minimum Weight Cut (10 pts)
Indicate a minimum-weight cut to separate s from t on the last picture.
CMPS 132 Spring, 2018 2 Handout 26