1
$\begingroup$

Let $G = (V,E)$ be a directed graph with source $s$ and sink $t$ and $s \neq t$. For each edge $e \in E$, we have $c(e) \in \Bbb N$.

also, we are given a max flow function $f$ on that network.

Let $R_f$ be the residual network that represents the max-flow $f$.

I would like to prove that if $R_f$ has a directed cycle with more than 2 edges, then the max flow is not unique (there is more than one max flow).

I tried approaching it in many ways in the last few days but I just get stuck every time when distinguishing between residual edges and edges that also exist in the original network.

thanks!

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ The statement isn't true, so no wonder you struggle with proving it. By the way, you can completely ignore the original graph, so you shouldn't confuse edges in the residual graph with edges in the OG $\endgroup$
    – Pål GD
    Feb 5, 2022 at 14:09
  • $\begingroup$ Does this answer your question? Proof that if the residual network of a max flow has no cycles then the max flow is unique $\endgroup$
    – John L.
    Feb 5, 2022 at 14:40
  • $\begingroup$ @PålGD why is this not true? $\endgroup$
    – dan paper
    Feb 5, 2022 at 15:29
  • $\begingroup$ @JohnL. not really. I already saw that but it just made me more confused. just to clarify, I'm trying to prove that if the residual graph has cycles than there is more than one max flow function. $\endgroup$
    – dan paper
    Feb 5, 2022 at 15:29
  • $\begingroup$ @danpaper, I see. Can you update your question to include the meaning of "$R_f$ has cycles"? What is a cycle in $R_f$? $\endgroup$
    – John L.
    Feb 5, 2022 at 15:37

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.