How to find a max flow in a flow network

Question

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:

(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!!!

Answer 1

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.