Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
@Jesko Thanks for the formatting help! –  BHD Nov 18 '12 at 21:27

1 Answer 1

up vote 1 down vote accepted

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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