Ferkans — Interactive Telecom Tutor

From Single-Hop to Multi-Hop: Why Graphs?

Every channel model we have studied so far — the DMC, the Gaussian channel, the MAC, the BC, the wiretap channel — has been a single-hop model. The transmitter sends directly to the receiver (and possibly to an eavesdropper), with no intermediate nodes. But real communication networks are multi-hop: data travels through routers, relays, and switches before reaching its destination.

Before tackling noisy multi-hop networks (Chapters 22–23), we start with the simplest version of the problem: noiseless networks where each link has a fixed integer capacity. The question is purely combinatorial: how much information can flow from source to destination through a graph? The answer is one of the most beautiful results in combinatorial optimization — the max-flow min-cut theorem — and it sets the stage for the surprising discovery that coding at intermediate nodes can strictly outperform routing.

Definition:
Communication Network as a Directed Graph

A communication network is a directed graph $G = (V, E)$ where:

$V$ is the set of nodes (routers, relays, terminals)
$E \subseteq V \times V$ is the set of directed edges (communication links)
Each edge $e \in E$ has a capacity $c(e) \in \mathbb{Z}_{>0}$ (the maximum number of symbols per time unit that can be transmitted over the link)
There is a designated source node $s \in V$ and a designated sink node $t \in V$

A flow from $s$ to $t$ is an assignment $f: E \to \mathbb{R}_{\geq 0}$ satisfying:

Capacity constraint: $0 \leq f(e) \leq c(e)$ for all $e \in E$
Flow conservation: for every node $v \neq s, t$ , $\sum_{e \in \text{in}(v)} f(e) = \sum_{e \in \text{out}(v)} f(e)$

The value of the flow is $|f| = \sum_{e \in \text{out}(s)} f(e) - \sum_{e \in \text{in}(s)} f(e)$ .

Network flow

An assignment of non-negative values to edges of a directed graph, satisfying capacity constraints and flow conservation at all non-terminal nodes. The flow value is the net flow leaving the source.

Definition:
Cut and Minimum Cut

An $s$ - $t$ cut in $G$ is a partition of $V$ into two sets $(S, S^c)$ with $s \in S$ and $t \in S^c$ . The capacity of the cut is $\text{cap}(S, S^c) = \sum_{\substack{e = (u,v) \in E \\ u \in S,\, v \in S^c}} c(e).$

The minimum cut is $\text{mincut}(s, t) = \min_{S:\, s \in S,\, t \notin S} \text{cap}(S, S^c)$ .

Intuitively, a cut is a "bottleneck" — removing all edges across the cut disconnects $s$ from $t$ . The minimum cut identifies the tightest bottleneck in the network.

Minimum cut

The minimum total capacity of edges whose removal disconnects the source from the sink in a directed graph. Represents the fundamental bottleneck of the network.

Theorem: Max-Flow Min-Cut Theorem (Ford–Fulkerson)

For any directed graph $G = (V, E)$ with integer edge capacities, source $s$ , and sink $t$ : $\text{maxflow}(s, t) = \text{mincut}(s, t).$

The maximum flow from $s$ to $t$ equals the minimum cut capacity separating $s$ from $t$ .

The inequality $\text{maxflow} \leq \text{mincut}$ is immediate: any flow must pass through every cut, so the flow cannot exceed the capacity of any cut — in particular, the minimum cut. The remarkable part is the reverse inequality: there is always a flow that saturates the minimum cut. No matter how complex the network topology, the bottleneck is always achieved, never just approached.

This is the graph-theoretic analogue of Shannon's channel coding theorem: the max-flow min-cut theorem tells us the capacity of a noiseless network, just as Shannon's theorem tells us the capacity of a noisy channel.

Proof

Weak inequality: $\text{maxflow} \leq \text{mincut}$

Let $f$ be any flow and $(S, S^c)$ any $s$ - $t$ cut. By flow conservation: $|f| = \sum_{e \in \text{out}(S)} f(e) - \sum_{e \in \text{in}(S)} f(e) \leq \sum_{e \in \text{out}(S)} c(e) = \text{cap}(S, S^c).$

Since this holds for all flows and all cuts: $\text{maxflow} \leq \text{mincut}$ .

Strong inequality via augmenting paths

The Ford–Fulkerson algorithm finds the maximum flow by iteratively finding augmenting paths in the residual graph. Starting with $f = 0$ :

Construct the residual graph $G_f$ : for each edge $e = (u,v)$ with $f(e) < c(e)$ , include a forward edge with residual capacity $c(e) - f(e)$ ; for each edge with $f(e) > 0$ , include a backward edge with capacity $f(e)$ .
Find a path from $s$ to $t$ in $G_f$ (an augmenting path).
Push flow along this path (the minimum residual capacity along the path).
Repeat until no augmenting path exists.

Termination and optimality

When no augmenting path exists, the set $S$ of nodes reachable from $s$ in $G_f$ defines a cut $(S, S^c)$ with $s \in S$ and $t \in S^c$ . Every edge from $S$ to $S^c$ in the original graph is saturated ( $f(e) = c(e)$ ), so $|f| = \text{cap}(S, S^c)$ .

This gives $\text{maxflow} = |f| = \text{cap}(S, S^c) \geq \text{mincut}$ .

Combined with the weak inequality: $\text{maxflow} = \text{mincut}$ . $\blacksquare$

Historical Note: Ford and Fulkerson (1956)

1956

The max-flow min-cut theorem was proved by L. R. Ford Jr. and D. R. Fulkerson in 1956, motivated by Cold War-era problems in operations research — specifically, the question of how to disrupt Soviet railway networks most efficiently. The "dual" nature of the theorem (the maximum amount you can ship equals the minimum cost of disruption) has a striking military interpretation: the optimal attack on a supply network targets exactly the minimum cut.

The theorem has since become one of the cornerstones of combinatorial optimization, with applications far beyond communication networks: airline scheduling, image segmentation, baseball elimination, and bipartite matching all reduce to max-flow problems.

Example: Max-Flow in a Diamond Network

Consider the diamond network with source $s$ , two relay nodes $r_1, r_2$ , and sink $t$ . The edges and capacities are:

$s \to r_1$ : capacity 3
$s \to r_2$ : capacity 2
$r_1 \to t$ : capacity 2
$r_2 \to t$ : capacity 3
$r_1 \to r_2$ : capacity 1

Find the max-flow and a minimum cut.

Solution

Find the max-flow

Path 1: $s \to r_1 \to t$ with flow 2 (limited by $r_1 \to t$ capacity).

Path 2: $s \to r_2 \to t$ with flow 2 (limited by $s \to r_2$ capacity).

Path 3: $s \to r_1 \to r_2 \to t$ with flow 1 (limited by $r_1 \to r_2$ and remaining capacity on $s \to r_1$ ).

Total flow: $2 + 2 + 1 = 5$ .

Verify with minimum cut

Cut $S = \{s\}$ , $S^c = \{r_1, r_2, t\}$ : capacity $= 3 + 2 = 5$ .

Cut $S = \{s, r_1\}$ , $S^c = \{r_2, t\}$ : capacity $= 2 + 2 + 1 = 5$ .

Cut $S = \{s, r_2\}$ , $S^c = \{r_1, t\}$ : capacity $= 3 + 3 = 6$ .

Cut $S = \{s, r_1, r_2\}$ , $S^c = \{t\}$ : capacity $= 2 + 3 = 5$ .

Minimum cut = 5 = max-flow. Multiple minimum cuts exist — the bottleneck is not unique.

Ford–Fulkerson Algorithm

Complexity:

O(|V| \cdot |E|^2)

for the Edmonds–Karp (BFS) variant. Faster algorithms exist: Dinic's algorithm achieves

O(|V|^2 |E|)

.

Input: Directed graph

G = (V, E)

, capacities

c(e)

, source

s

, sink

t

Output: Maximum flow

f

1. Initialize

f(e) \leftarrow 0

for all

e \in E

2. while there exists an augmenting path

P

from

s

to

t

in

G_f

:

a.

\delta \leftarrow \min_{e \in P} c_f(e)

(bottleneck of the path)

b. for each edge

e = (u,v) \in P

:

- If

e

is a forward edge:

f(e) \leftarrow f(e) + \delta

- If

e

is a backward edge:

f(v,u) \leftarrow f(v,u) - \delta

3. return

f

Complexity:

O(|E| \cdot \text{maxflow})

with DFS path selection.

With BFS (Edmonds–Karp):

O(|V| \cdot |E|^2)

.

For unit-capacity graphs, the complexity simplifies to $O(|E| \sqrt{|V|})$ using Hopcroft–Karp-style blocking flows.

Quick Check

In a directed graph, every edge from $S$ to $S^c$ in a minimum cut is saturated by the max-flow. What about edges from $S^c$ to $S$ ?

They carry zero flow — if they carried positive flow, we could cancel it and increase the net flow

They are also saturated

It depends on the network topology

Correction:

They carry zero flow — if they carried positive flow, we could cancel it and increase the net flow

In the max-flow, edges from $S^c$ to $S$ in a minimum cut carry zero flow. If any carried positive flow $f(e) > 0$ , reducing that flow would increase the net flow from $S$ to $S^c$ without violating any capacity constraint, contradicting the optimality of the max-flow.

Common Mistake: Applying Max-Flow to Undirected Graphs Without Care

Mistake:

Treating an undirected edge as a single directed edge with capacity $c$ when computing max-flow.

Correction:

An undirected edge $(u, v)$ with capacity $c$ should be modeled as two directed edges: $u \to v$ and $v \to u$ , each with capacity $c$ . The flow on the two directed edges can differ, but the net flow on the undirected edge is $f(u,v) - f(v,u)$ , which must satisfy $|f(u,v) - f(v,u)| \leq c$ .

Key Takeaway

The max-flow min-cut theorem establishes that the capacity of a noiseless network for unicast (one source, one sink) equals the minimum cut. This is achievable by routing alone — no coding at intermediate nodes is needed. The surprise comes in the next section: for multicast (one source, multiple sinks), routing is no longer sufficient, and coding at intermediate nodes can strictly increase the achievable rate.

Max-Flow Min-Cut: Augmenting Paths and Bottlenecks

Animates the Ford–Fulkerson algorithm on a diamond network: augmenting paths are found one by one, flow increases, and the minimum cut is revealed as the fundamental bottleneck.

Max-Flow Min-Cut for Single Unicast

From Single-Hop to Multi-Hop: Why Graphs?

Definition: Communication Network as a Directed Graph

Network flow

Definition: Cut and Minimum Cut

Minimum cut

Theorem: Max-Flow Min-Cut Theorem (Ford–Fulkerson)

Weak inequality: $\text{maxflow} \leq \text{mincut}$

Strong inequality via augmenting paths

Termination and optimality

Historical Note: Ford and Fulkerson (1956)

Example: Max-Flow in a Diamond Network

Find the max-flow

Verify with minimum cut

Ford–Fulkerson Algorithm

Quick Check

Common Mistake: Applying Max-Flow to Undirected Graphs Without Care

Key Takeaway

Max-Flow Min-Cut: Augmenting Paths and Bottlenecks

Definition:
Communication Network as a Directed Graph

Definition:
Cut and Minimum Cut