0
$\begingroup$

I'm trying too many days to find an answer for this question with no success,

so I hope you can help me.

Let's say I have the following flow network:

enter image description here

(The denotea/brepresents anaunits flow on edge of capacityb)

  1. How can you find out whether it's the maximum flow or not?

  2. If not, who can you find the maximum flow?

I'm kind of desperated so I'll be happy if you can help me,. thanks in advance!!!

$\endgroup$
  • 1
    $\begingroup$ Is there an augmenting path? $\endgroup$ – Casteels May 13 '14 at 9:16
  • $\begingroup$ @Casteels What do you mean? $\endgroup$ – Billie May 13 '14 at 9:17
  • $\begingroup$ @Billie What flow-related concepts are you familiar with? Do you know what residual networks, residual capacities and augmenting paths are? If not, I would recommend searching for it. There is a basic info on these here, here or here. $\endgroup$ – dtldarek May 13 '14 at 9:51
1
$\begingroup$

An $(s,t)$-augmenting path from $s$ to $t$ is a path $P$ starting at $s$ and ending at $t$ in which the forward arcs are not at capacity (i.e., $a<b$) and the backward arcs have non-zero flow ($a>0$). Note that on such a path $P$, you can increase flow by some amount by adding that amount to the forward arcs on $P$ and subtracting it from the backward arcs on $P$.

Theorem: An $(s,t)$-flow is maximum if and only if there are no augmenting $(s,t)$-paths.

In your case, there is an $(s,t)$-augmenting path and you can increase the total flow by $1$ along it to get an $(s,t)$-flow of value 12.

The slick method to determine the value of a maximum $(s,t)$-flow is to look at $(s,t)$-cuts. An $(s,t)$-cut is a set $S$ of vertices with $s\in S$ and $t\not\in S$. The value of the cut is the sum of the capacities of all arcs going leaving $S$ and going into $V\setminus S$. For example, $S=\{s,a,b\}$ is an $(s,t)$-cut with value $12$.

Theorem (Max-flow min-cut Theorem): The value of a maximum $(s,t)$-flow equals the smallest possible value of an $(s,t)$-cut.

This means that if you can find an $(s,t)$-cut with a value that equals the current value of the $(s,t)$-flow, then the flow is definitely maximum. Since we've found an $(s,t)$-cut with value $12$, and you also have a flow of value $12$ (after augmentation), you may conclude that your flow is maximum.

By the way, the above two theorems are non-trivial. I expect your teacher will get to them soon enough if they haven't done so already.

| cite | improve this answer | |
$\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.