I am studying graph theory on my own, and I was looking for extra problems online. One that I came across was from the following source.
I am stumped on how to choose which edges we can increase the flow on, if the capacity were increased.
In the following directed graph of a maximum flow:
For each of the edges in the above graph, I want to identify which edges I can increase the value of the flow on, if the capacity of the edge is increased.
The solution is as follows:
Best Answer
You have to identify the bottlenecks. By the max flow min cut theorem ,the maximum value of an $s-t$ flow is equal to the minimum capacity over all $s-t$ cuts, in this case this value is $14$.
It is not difficult to see that this minimum capacity is reached over the cut $$\{(C,t), (s,B),(C,B)\},$$ which are your bottlenecks. So it clear that increasing the capacities over any edge that does not belong to this cut will not enable to increase the maximum flow.
Conversely, if you increase the capacity of edge $(C,t)$ by $x$ units, you free a bottleneck, and you can increase the flow on the path $s-A-C-t$ by $\;\min\{2,x \}$ units.
The same logic holds for edges $(s,B)$ and $(C,B)$ with paths $s-B-D-t\;$ and $s-A-C-B-D-t$, respectively.