Good morning everyone. I failed a graph theory exam last week and I would like to know how to solve some of the problems I got because I don't have any idea. One of the problems was asking for an algorithm. The problem is:
Let $R = (G,S,T,c)$ be a network, $x$ is a flow in $R$ and $(S,T)$ a cut in $R$. Write an algorithm of complexity $\mathcal O(n+m)$ which will decide if $x$ is a maximum flow and $(S,T)$ a min cut, simultaneous.
Here I tried to use Ford Fulkerson with a queue, but I think my problem was on the queue. I didn't know how to include the min cut in the Ford Fulkerson Algorithm.
What is the right algorithm for this?
Find the set of vertices $A$ $=\{u$: net flow out of $u$ is positive $\}$, and for each vertex $u \in A$ let $y(u)$ be the net flow out of $u$. To calculate the net flow of a vertex $u$, calculate the flow out of $u$ given by $\sum x(u,v); v \in N_G(u)$, and subtract from that the flow into $u$ given by $\sum x(v,u); v \in N_G(u)$.
Then $(S,T)$ is a minimum cut iff $\sum_{u \in A} y(u) = \sum_{e \in (S,t)} c(e)$, where $c(e)$ denotes the capacity of $e$.