1
$\begingroup$

Hi I'm trying to prove the following proposition:


Given a network $G,s,t,\omega$ where $\omega$ is the capacity, create a minimal cut cut ${S=\left\{ (s,v)\in E_{G_{r\_max}}\right\} }$ where $G_{r\_max}$ is graph representing the the residual network(meaning we take the group of all vertices that are reachable from s in $G_{r\_max}$). So that the cut is $\left(S,V\backslash S\right)$.

Given two maximal flows $f_1\neq f_2$ prove that $\left(S_1,V\backslash S_1\right)=\left(S_2,V\backslash S_2\right)$ (which are defined in the above mentioned form for each maximal flow).


I've tried proving by assuming the contrary and saying that $S_1 $ is not subset of $S_2$. Tried to say that this leads to $\exists \ v\in S_1 \ \ \mbox{s.t} \ \ v\notin S_2$. Tried looking at the intersection and union of these groups but to no avail.

I'd appreciate some guidance\explanation as to how best prove this claim.

$\endgroup$
1
$\begingroup$

Here are some hints. Instead of trying to prove the contrapositive, try proving the statement directly. If $f_1 \ne f_2$, then that means that there is some edge $e$ where $f_1$ sends a different amount of flow down than $f_2$ does. What does that imply about the residual graph for $f_1$, vs the residual graph for $f_2$? Those two residual graphs must differ in some specific way: how? What does that difference imply for $S_1$ vs $S_2$? Try writing out some small examples, with small graphs, where you draw the flows, residual graphs, and cuts explicitly. What do you find?

I suggest you spend a bit more quality time on your own, trying a bit harder to solve it yourself. This is your exercise; you need to solve it yourself. And you need to put in a bit more effort to explore this problem. Don't give up easily -- you can do it!

$\endgroup$

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.