2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Jesko Thanks for the formatting help! $\endgroup$ – BHD Nov 18 '12 at 21:27
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Let me run through that logic real quick, I'm not nearly as good at this stuff as I should be, hence the practice. $\endgroup$ – BHD Nov 18 '12 at 21:36
  • $\begingroup$ Seems to be correct! Thanks very much! My solution was a page long and still incorrect. Nice to see where I was going wrong. $\endgroup$ – BHD Nov 18 '12 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.