Consider a network with capacities c(e) over edges. Say that we found the maximu

Question

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. The following question can be true or false. Hence answer for each one of them if its true or false and prove your answer. Saying only yes/no will not get many points.

2. It may be that the flow value increased by 2 after the change.

Explanation / Answer

Solution:

So for the given example lets call bottle necks of the flow in the graph G(V, E) as b1, b2, b3, .....bn

Now let's say we have achieved maximum flow f which is achieved using two of these bottlenecks named as b1, b2 and they are the part of some augmenting paths p1, p2

Now value of each node is increased by 1, so is for the bottlenecks. So now what will happen in this case the value of maximum flow will be increased by 2. But suppose if only one augmenting path would have been there then only one bottleneck b1 would have participated in the maxflow then f would have been f+1 in the updated graph.

or may be more than two bottlenecks are there making more than two augmenting paths who are participating in max flow, then the result would have been true. But not always.

I hope this helps. Don't forget to give a thumbs up if you like this.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.