Directed Graphs and Network Flows

Let $D$ have vertices $p,q,r,s$ and arcs $p\to q$, $q \to r$, $r \to p$, $p \to r$, $s \to p$ — $|A|=5$ arcs. Reading off each vertex: $d^+(p)=2$ (to $q$ and $r$), $d^+(q)=1$, $d^+(r)=1$, $d^+(s)=1$, summing to $5=|A|$; and $d^-(p)=2$ (from $r$ and $s$), $d^-(q)=1$, $d^-(r)=2$, $d^-(s)=0$, also summing to $5$. Vertex $p$ touches $4$ arcs in all, $2$ leaving and $2$ entering.

Four teams play a round robin with results $1\to 2$, $1 \to 3$, $2 \to 3$, $2 \to 4$, $3 \to 4$, $4 \to 1$ (an arrow points from winner to loser). This uses every one of the $\binom{4}{2}=6$ pairs exactly once, so it is a genuine tournament. The score of a team is its out-degree (wins): $d^+(1)=2$, $d^+(2)=2$, $d^+(3)=1$, $d^+(4)=1$. The score sequence $(2,2,1,1)$ sums to $6=\binom{4}{2}$, as it must: every game contributes exactly one win.

Does the tournament above have a Hamiltonian path — a directed path visiting all $4$ teams, each exactly once, always moving winner-to-loser? Try $4 \to 1 \to 2 \to 3$: it uses the arcs $4\to1$, $1\to2$, $2\to3$, all present, and visits every team exactly once. So yes — and in fact every tournament has a Hamiltonian path, however its games fall, unlike a general digraph (contrast Topic 6's search for Hamiltonian cycles in undirected graphs, which can fail outright).

Let $D_2$ have vertices $a,b,c,d,e$ and arcs $a\to b$, $b \to c$, $c \to a$, $c \to d$, $d \to e$, $e \to d$ — a $3$-cycle on $a,b,c$ feeding into a $2$-cycle on $d,e$. Inside the $3$-cycle, $a \to b \to c \to a$ gives a path from $a$ to $c$ and the single arc $c \to a$ gives one back, so $a$ and $c$ are mutually reachable, and likewise every pair in $\{a,b,c\}$; the same argument makes $d$ and $e$ mutually reachable via their $2$-cycle. So $D_2$ has (at least) two strongly connected components, $\{a,b,c\}$ and $\{d,e\}$.

Is there a directed path from $d$ back to $a$ in $D_2$? Every arc leaving $\{d,e\}$ stays inside $\{d,e\}$ ($d\to e$ and $e \to d$ are the only arcs with tail in $\{d,e\}$), so no walk starting at $d$ can ever reach $a$, $b$ or $c$. Hence $D_2$ is NOT strongly connected, and $\{a,b,c\}$, $\{d,e\}$ really are two separate SCCs, not one — confirming the only arc joining them, $c \to d$, runs one way.

Collapsing $\{a,b,c\}$ to a single vertex and $\{d,e\}$ to another leaves exactly one arc between them, $\{a,b,c\} \to \{d,e\}$ (coming from $c \to d$), and no arc the other way. A digraph on $2$ vertices with only one of the two possible arcs present has no directed cycle, so the condensation is a DAG, and $\{a,b,c\}, \{d,e\}$ is already a valid topological order of it (Topic 5).

Network $N_1$ has source $s$, sink $t$, and vertices $a,b,c$ in between, with capacities $c(s,a)=5$, $c(s,b)=3$, $c(a,b)=2$, $c(a,c)=3$, $c(b,c)=1$, $c(b,t)=4$, $c(c,t)=5$ — $7$ arcs in all. This network, and no other, is used for the rest of this topic.

Try $f(s,a)=5$, $f(s,b)=3$, $f(a,b)=2$, $f(a,c)=3$, $f(b,c)=1$, $f(b,t)=4$, $f(c,t)=4$. Every value is within its arc's capacity. Check conservation: at $a$, in $=5$, out $=f(a,b)+f(a,c)=2+3=5$; at $b$, in $=f(s,b)+f(a,b)=3+2=5$, out $=f(b,c)+f(b,t)=1+4=5$; at $c$, in $=f(a,c)+f(b,c)=3+1=4$, out $=f(c,t)=4$. All three balance, so $f$ is a valid flow, with value $|f| = f(s,a)+f(s,b) = 5+3=8$.

A flow need not use every arc: send $f(s,a)=3$, $f(a,c)=3$, $f(c,t)=3$, and $f(s,b)=f(a,b)=f(b,c)=f(b,t)=0$. Conservation holds trivially at $b$ ($0=0$) and at $a$ and $c$ ($3=3$ each), so this is a valid flow too, with value $|f| = f(s,a) = 3$ — smaller than the value-$8$ flow above. Flows are not unique, which raises the question the next two sections answer: how do you know when a flow is as large as possible?

Take $S=\{s\}$, $T=\{a,b,c,t\}$. The only arcs leaving $S$ are $s\to a$ and $s \to b$, so $\operatorname{cap}(S,T) = c(s,a)+c(s,b) = 5+3=8$. By weak duality, NO flow in $N_1$ can have value above $8$ — and the flow of value $8$ found in the last section meets this bound exactly, so that flow is already maximum, and $(\{s\}, \{a,b,c,t\})$ is a minimum cut.

Take $S=\{s,a,b\}$, $T=\{c,t\}$ instead. Arcs $s\to a$, $s \to b$ and $a \to b$ are internal to $S$ and do not count; the arcs leaving $S$ are $a \to c$, $b \to c$ and $b \to t$, giving $\operatorname{cap}(S,T) = 3+1+4=8$ — the SAME capacity as the first cut. A minimum cut need not be unique: $N_1$ has (at least) two different cuts, both achieving capacity $8$, matching the max flow value found earlier.

Take $S=\{s,b\}$, $T=\{a,c,t\}$. The arcs leaving $S$ are $s \to a$ (since $a \in T$), $b \to c$ and $b \to t$, giving $\operatorname{cap}(S,T) = 5+1+4=10$. Since $10 > 8$, this cut is valid but NOT minimum — weak duality still holds ($8 \le 10$), it just is not tight for this particular $S$.

Network $N_2$ has $s,a,b,t$ with every arc capacity $1$: $s\to a$, $s \to b$, $a \to b$, $a \to t$, $b \to t$. Push $1$ unit along $s \to a \to b \to t$ (bottleneck $\min(1,1,1)=1$): now $f(s,a)=f(a,b)=f(b,t)=1$, each saturated. The residual graph still has $s \to b$ (capacity $1$, unused) and $a \to t$ (capacity $1$, unused) — but also, since $f(a,b)=1>0$, a BACKWARD arc $b \to a$ of residual capacity $1$. The augmenting path $s \to b \to a \to t$ uses exactly that backward arc, pushing $1$ more unit.

Pushing $1$ unit along $s \to b \to a \to t$ sets $f(s,b)=1$ and $f(a,t)=1$ directly, while traveling the backward arc $b \to a$ DECREASES $f(a,b)$ by $1$, from $1$ down to $0$. The final flow is $f(s,a)=1$, $f(s,b)=1$, $f(a,b)=0$, $f(a,t)=1$, $f(b,t)=1$ — every arc still within capacity, conservation holds at $a$ ($1=0+1$) and at $b$ ($1+0=1$) — with value $|f|=f(s,a)+f(s,b)=2$. This matches the cut $\{s\}$, of capacity $c(s,a)+c(s,b)=1+1=2$, so $2$ is in fact the maximum.

Run Ford-Fulkerson on $N_1$ from scratch. Path $s\text{-}a\text{-}c\text{-}t$: bottleneck $\min(5,3,5)=3$, pushing $f(s,a)=3,f(a,c)=3,f(c,t)=3$. Path $s\text{-}b\text{-}c\text{-}t$: residual $c(b,c)-0=1$ is the bottleneck, pushing $f(s,b)=1,f(b,c)=1,f(c,t)=4$. Path $s\text{-}b\text{-}t$: residual $c(s,b)-1=2$ and $c(b,t)=4$ give bottleneck $2$, pushing $f(s,b)=3,f(b,t)=2$. Path $s\text{-}a\text{-}b\text{-}t$: residual $c(s,a)-3=2$, $c(a,b)=2$, $c(b,t)-2=2$ give bottleneck $2$, pushing $f(s,a)=5,f(a,b)=2,f(b,t)=4$. Every arc is now saturated except $c \to t$ ($4$ of $5$), and no augmenting path remains: $s$'s two arcs are both saturated and nothing enters $s$, so the set reachable from $s$ in the residual graph is just $\{s\}$. The final value is $f(s,a)+f(s,b)=5+3=8$, exactly the cut $\{s\}$'s capacity found earlier.