Homework Assignment 5, due June 3 11:59PM
留学生Cs代写 Show your knowledge of the Ford Fulkerson Network Flow Algorithm by carefully carrying out the steps on the graph pictures below.
1 Last (5th) homeworkassignment
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) 留学生Cs代写
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.
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?
1.3 Network Flow 2 (40 pts) 留学生Cs代写
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.
1.4 Minimum Weight Cut (10 pts)
Indicate a minimum-weight cut to separate s from t on the last picture.
