CSCI 570 – Fall 2020 – HW9
Due November 4th 11:59pm 2020
1 Graded Problems
1. In the network below 1, the demand values are shown on vertices. Lower bounds on flow and edge capacities are shown as (lower bound, capacity) for each edge. Answer the following questions:
1. Describe how to reduce the circulation problem into a maximum flow problem.
2. Compute the maximum flow of the reduced problem.
3. Determine if there is a feasible circulation in the original graph.
2. Whether the statement is True or False? Give your explanation.
1. For every graph G and every maximum flow on G, there always exists an edge such that increasing the capacity on that edge will increase the maximum
flow that¡¯s possible in the graph.
2. The problem of deciding whether a given flow f of a given flow network
G is maximum flow can be solved in linear time.
3. In any maximum flow there are no cycles that carry positive flow.(A cycle
< e1, ..., ek > carries positive flow iff f (e1) > 0, …, f (ek) > 0.)
4. Given a flow network where all the edge capacities are even integers, the Ford-Fulkerson algorithm will require at most C/2 iterations, where C is the
total capacity leaving the source s.
Figure 1: Q1 1
2 Practice Problems
3. Reading assignment: Kleinberg and Tardos, Chapter 7.
2