Description
-
Take the following flow-network and run the Ford-Fulkerson algorithm on it. Once you are done, write the following items in your response:
Write the original / starting residual graph Gf for this network BEFORE execution of Ford-Fulkerson begins. This should be an Adjacency Matrix
Write out the final / ending residual graph Gf after Ford-Fulkerson completes. This should be an Adjacency Matrix and make sure to include backflow edges.
What is the final maximum flow f for this Graph?
-
Consider the flow network you see below (the bolded edges the first augmenting path that Ford-Fulkerson will discover). What is the maximum number of iterations that Ford-Fulkerson could make (i.e., what is the most number of times DFS could run). Explain how this maximum could be reached and why it is a major issue.
-
Suppose we want to take a flow-network as input, and return a set of at most jEj augmenting paths that produce the maximum flow on that network. Describe an algorithm to do this. Hint: Find the maximum flow using any number of augmenting paths first, then try to reverse engineer how to reach that flow with at most jEj augmenting paths.
