network-flowproof-writing
Let's start out by reviewing max-flow min-cut, as well as the flow networks they operate on.
http://en.wikipedia.org/wiki/Flow_network
http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
Let $G = (V,E)$ be a flow network. Prove a minimum cut is also a minimum-capacity
cuts of $G$.
Thanks for any help, this problem has been throwing me for a loop!
Note: NOT homework, extra problems from our book I'm working through for exam preparation.
Generally in solving a maximum flow problem, one finds not only the total flow from source to sink, but the capacity limited flows on each edge of the graph (network). For example:
By Min_cut.png: Maksim derivative work: Cyhawk (Min_cut.png) CC-BY-SA-3.0 or GFDL, via Wikimedia Commons
Now the problem of the fewest edges whose capacity must be increased in order to increase the total flow can be solved as a "shortest path" problem for a related graph. Here the source node is $s$ and the sink node is $t$.
Let edges whose capacity is fully used ("tight" constraint) be assigned length one, and let edges whose capacity is less than fully used ("slack" constraint) be assigned length zero.
Then the corresponding shortest path from $s$ to $t$ will have length two:
$$ s \to p \to r \to t $$
since the edge from $s$ to $p$ has length zero in this context.
Thus we need only increase the capacities of the two "tight" edges along this path, $p$ to $r$ and $r$ to $t$, in order to increase the total flow.
In this example it is not hard to see by inspection that capacity increases to at least two edges are needed, as both $q\to t$ and $r\to t$ are tight, and also $o\to q$ and $p\to r$ are tight, and any path from $s$ to $t$ must pass through one of each of these independent pairs.
Add the edges $su$ and $vt$ to the network with infinite capacity to obtain the modified network $N'$. It is not difficult to see that the finite ($st$-)cuts in $N'$ are precisely those finite cuts in $N$ that contain the edge $e$. This means that a min-cut in $N'$ is a min-cut in $N$ among those cuts that contain $e$. So you just have to check whether the min-cut in $N'$ has the same capacity as the min-cut in $N$, which can be done using the Ford-Fulkerson (or, to be more precise, the Edmonds-Karp) algorithm.
Note that this method easily generalizes to the case when you have multiple prescribed edges.
Best Answer
Here is a way to do this. Consider a max flow $f$ and the residual network $E_f$. From the max flow min cut theorem it is easy to get that $E_f$ doesn't contain any edge that goes from $S$ to $T$. Neither does it contain any edges from $S'$ to $T'$. Then it also has no edges going from $S \cup S'$ to $T \cap T'$.
But if no edge from $E_f$ crosses the cut $(S \cup S',T \cap T')$, then $$ c(S \cup S', T \cap T') = f(S \cup S', T \cap T'), $$ and using the min cut max flow theorem once again we see that cut $(S \cup S', T \cap T')$ is also minimal.