Introduction to Network Flows

This page introduces the basic concepts of network flows.

Overview

A network is a special directed graph $G=(V,E)$, distinguished from an ordinary directed graph by its capacities and source and sink.

• Every edge in $E$, namely $(u, v)$, has a weight called its capacity, denoted by $c(u, v)$. When $(u,v)\notin E$, we may assume $c(u,v)=0$.

• There are two special vertices in $V$: the source (source) $s$ and the sink (sink) $t$ ($s \neq t$).

For a network $G=(V, E)$, a flow is a function from the edge set $E$ to the integers or reals that satisfies the following properties.

1. Capacity constraint: for every edge, the flow through that edge cannot exceed its capacity, that is, $0 \leq f(u,v) \leq c(u,v)$;
2. Flow conservation: except at the source and sink, the net flow at every vertex $u$ is $0$. Here, the net flow at $u$ is defined as $f(u) = \sum_{x \in V} f(u, x) - \sum_{x \in V} f(x, u)$.

For a network $G = (V, E)$ and a flow $f$ on it, define $f$'s flow value $|f|$ as $s$'s net flow $f(s)$. As a consequence of flow conservation, this is also the opposite of $t$'s net flow, namely $-f(t)$.

For a network $G = (V, E)$, if $\{S, T\}$ is a partition of $V$ (that is, $S \cup T = V$ and $S \cap T = \varnothing$), and $s \in S, t \in T$, then $\{S, T\}$ is called a cut of $G$ separating $s$ and $t$. The capacity of the $s$–$t$ cut $\{S, T\}$ is defined as $||S, T|| = \sum_{u \in S} \sum_{v \in T} c(u, v)$.

Common Problems

Common network-flow problems include, but are not limited to, the following types.

• Maximum-flow problem: for a network $G = (V, E)$, assign a flow to each edge to obtain a suitable flow $f$ and make $f$'s flow value as large as possible. Such a flow $f$ is called a maximum flow of $G$.
• Minimum-cut problem: for a network $G = (V, E)$, find a suitable $s$–$t$ cut $\{S, T\}$ and make the total capacity of $\{S, T\}$ as small as possible. This total capacity $\{S, T\}$ is called the minimum cut of $G$.
• Minimum-cost maximum-flow problem: for a network $G = (V, E)$, assign a weight $w(u, v)$ to each edge, called its cost, meaning the cost paid for sending one unit of flow through $(u, v)$. Among all possible maximum flows of $G$, the one with minimum total cost is called a minimum-cost maximum flow.

We will introduce these problems in detail in later chapters.

Example: 24 Network-Flow Problems

The 24 network-flow problems are a widely circulated problem set on the Chinese internet (LibreOJ/Luogu); they existed at least around 2010. The set introduced classic techniques for modeling other problems as network-flow problems. Due to the limitations of its era, these problems may not be the most representative network-flow problems, but they are still worth reading for readers interested in algorithm competitions.