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!

$\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
    Commented 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.
    Commented Feb 5, 2022 at 14:40
  • $\begingroup$ @PålGD why is this not true? $\endgroup$
    – dan paper
    Commented 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
    Commented 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.
    Commented Feb 5, 2022 at 15:37

0

Your Answer

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