Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
The max-flow min-cut theorem guarantees that the min-cut of a directed network equals the maximum flow. And we can compute $S$ and $T$, are disjoint subsets containing source node and sink node respectively from the residual graph.
What will be $S$ and $T$ if the max-flow from source to sink is 0, that is, there is no directed path from $s$ to $t$? Is $S$ going to be the singleton set {s} or its the empty set $\phi$ and $T$ be the vertex set $V$?
No, your gut feeling is not correct.
Consider the following flow network with source $s$ and sink $t$, where the capacity of every edge is 1. The max-flow from source to sink is 0. The s-t cut $(\{s,A\}, \{B,t\})$ is a minimum cut since the only connecting edge $(B, A)$ goes from sink side to source side.
$$ s \longrightarrow A \longleftarrow B \longrightarrow t$$
You could learn several lessons from this simple problem. One is that source and sink are symmetric in some strong sense. It looks like your gut feeling does not respect this symmetry. Another lesson is that a few simple examples should be included in your repository. Always try constructing some simple or extreme examples when you want to check a proposition of unknown truth value.
