Q5: Consider a network with capacities c(e) over edges. Say that we found the ma
ID: 3826532 • Letter: Q
Question
Q5: Consider a network with capacities c(e) over edges. Say that we found the maximum flow function from s to t. Denote by f(e) the flow on e, Say that we choose one of the directed edges e and increase the capacity of this edge e by 1. Namely the capacity of e is c(e) + 1 now. In the following 4 questions each can be true or false. Hence answer for each one of them if it’s true or false and prove your answer. Saying only yes/no will not get many points.
1. It may be that the flow value was not increased even after the change.
2. It may be that the flow value increased by 2 after the change.
3. It may be that the flow increased by 1 after the change.
4. It is possible to find in time O(n + n) if the current flow f is still a maximum flow, or otherwise find a new maximum flow. Here V = n and E = n
Explanation / Answer
Ans 1) True.Increse in the capacity of the edge does not increase the flow of a network
Consider the graph G ,
s------------->u------------------->v-------------------------->t
3 3 3
In the above graph forms a minimum (s,t)-cut.So, increase in the capacity of this edge does not lead increase in the maximum flow of a network .Suppose we incresed the capacity of edge (v,t) by 1, but still the maximum flow will be 3.
s------------->u------------------->v-------------------------->t
3 3 4
Still only 3 units of flow can be possible.
Ans 2) False.In the below graph, to increase the flow by two you will have to increase the capacity of an edge by 2 not by one.
s------------->u------------------->v-------------------------->t
1 3 3
Ans 3)True.In the below graph, the maximum capacity flow is 1.Now we increase the capacity of an edge (s,u) be 1.Now the the maximum capacity flow is 2 can be passed.
s------------->u------------------->v-------------------------->t
1 2 2
After increase
s------------->u------------------->v-------------------------->t
2 3 3
Ans 4) True. Suppose that the edge from u to v increases its capacity by one.From the previous maximum flow f, just make a new iteration of Ford-Fulkerson algorithm with the modified graph.
The resulting residual flow graph increases the capacity of edge (u,v) with 1.Make a graph search (in O(m+n)) to see if there is any path in the residual graph along which the flow increase.If there is one, there must be a flow size one.If not,f still the maximum flow.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.