Pseudocode or written explanation only. Consider a network with capacities c(e)
ID: 3826067 • Letter: P
Question
Pseudocode or written explanation only.
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 its true or false and prove your answer.
1) It may be that the flow value was not increased even after the change.
2) It may be that the flow value icnreased 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(m + 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
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.