$ \newcommand{\overrightharpoon}[1]{\overrightarrow{#1}} \newcommand{\overleftharpoon}[1]{\overleftarrow{#1}} $

A directed graph, also called a digraph, is a graph in which the edges have a direction. This is usually indicated with an arrow on the edge; more formally, if $v$ and $w$ are vertices, an edge is an unordered pair $\{v,w\}$, while a directed edge, called an arc, is an ordered pair $(v,w)$ or $(w,v)$. The arc $(v,w)$ is drawn as an arrow from $v$ to $w$. If a graph contains both arcs $(v,w)$ and $(w,v)$, this is not a "multiple edge'', as the arcs are distinct. It is possible to have multiple arcs, namely, an arc $(v,w)$ may be included multiple times in the multiset of arcs. As before, a digraph is called simple if there are no loops or multiple arcs.

We denote by $E\strut_v^-$ the set of all arcs of the form $(w,v)$, and by $E_v^+$ the set of arcs of the form $(v,w)$. The indegree of $v$, denoted $\d^-(v)$, is the number of arcs in $E\strut_v^-$, and the outdegree, $\d^+(v)$, is the number of arcs in $E_v^+$. If the vertices are $v_1,v_2,\ldots,v_n$, the degrees are usually denoted $d^-_1,d^-_2,\ldots,d^-_n$ and $d^+_1,d^+_2,\ldots,d^+_n$. Note that both $\sum_{i=0}^n \d^-_i$ and $\sum_{i=0}^n \d^+_i$ count the number of arcs exactly once, and of course $\sum_{i=0}^n \d^-_i=\sum_{i=0}^n \d^+_i$. A walk in a digraph is a sequence $v_1,e_1,v_2,e_2,\ldots,v_{k-1},e_{k-1},v_k$ such that $e_k=(v_i,v_{i+1})$; if $v_1=v_k$, it is a closed walk or a circuit. A path in a digraph is a walk in which all vertices are distinct. It is not hard to show that, as for graphs, if there is a walk from $v$ to $w$ then there is a path from $v$ to $w$.

Many of the topics we have considered for graphs have analogues in digraphs, but there are many new topics as well. We will look at one particularly important result in the latter category.

Definition 5.11.1 A network is a digraph with a designated source $s$ and target $t\not=s$ . In addition, each arc $e$ has a positive capacity, $c(e)$.

Networks can be used to model transport through a physical network, of a physical quantity like oil or electricity, or of something more abstract, like information.

Definition 5.11.2 A flow in a network is a function $f$ from the arcs of the digraph to $\R$, with $0\le f(e)\le c(e)$ for all $e$, and such that $$\sum_{e\in E_v^+}f(e)=\sum_{e\in E_v^-}f(e), $$ for all $v$ other than $s$ and $t$.

We wish to assign a value to a flow, equal to the net flow out of the source. Since the substance being transported cannot "collect'' or "originate'' at any vertex other than $s$ and $t$, it seems reasonable that this value should also be the net flow into the target.

Before we prove this, we introduce some new notation. Suppose that $U$ is a set of vertices in a network, with $s\in U$ and $t\notin U$. Let $\overrightharpoon U$ be the set of arcs $(v,w)$ with $v\in U$, $w\notin U$, and $\overleftharpoon U$ be the set of arcs $(v,w)$ with $v\notin U$, $w\in U$.

Theorem 5.11.3 For any flow $f$ in a network, the net flow out of the source is equal to the net flow into the target, namely, $$\sum_{e\in E_s^+} f(e)-\sum_{e\in E_s^-}f(e)= \sum_{e\in E_t^-} f(e)-\sum_{e\in E_t^+}f(e).$$

Proof.
We will show first that for any $U$ with $s\in U$ and $t\notin U$, $$\sum_{e\in E_s^+} f(e)-\sum_{e\in E_s^-}f(e)= \sum_{e\in\overrightharpoon U} f(e)-\sum_{e\in\overleftharpoon U}f(e).$$

Consider the following: $$S=\sum_{v\in U}\left(\sum_{e\in E_v^+}f(e)-\sum_{e\in E_v^-}f(e)\right).$$ The quantity $$\sum_{e\in E_v^+}f(e)-\sum_{e\in E_v^-}f(e)$$ is zero except when $v=s$, by the definition of a flow. Thus, the entire sum $S$ has value $$\sum_{e\in E_s^+} f(e)-\sum_{e\in E_s^-}f(e).$$ On the other hand, we can write the sum $S$ as $$ \sum_{v\in U}\sum_{e\in E_v^+}f(e)- \sum_{v\in U}\sum_{e\in E_v^-}f(e). $$ Every arc $e=(x,y)$ with both $x$ and $y$ in $U$ appears in both sums, that is, in $$\sum_{v\in U}\sum_{e\in E_v^+}f(e),$$ when $v=x$, and in $$\sum_{v\in U}\sum_{e\in E_v^-}f(e),$$ when $v=y$, and so the flow in such arcs contributes $0$ to the overall value. Thus, only arcs with exactly one endpoint in $U$ make a non-zero contribution, so the entire sum reduces to $$\sum_{e\in\overrightharpoon U} f(e)-\sum_{e\in\overleftharpoon U}f(e).$$ Thus $$\sum_{e=(s,v)} f(e)-\sum_{e=(v,s)}f(e)=S= \sum_{e\in\overrightharpoon U} f(e)-\sum_{e\in\overleftharpoon U}f(e),$$ as desired.

Now let $U$ consist of all vertices except $t$. Then $$ \sum_{e\in E_s^+} f(e)-\sum_{e\in E_s^-}f(e)= \sum_{e\in\overrightharpoon U} f(e)-\sum_{e\in\overleftharpoon U}f(e)= \sum_{e\in E_t^-} f(e)-\sum_{e\in E_t^+}f(e), $$ finishing the proof.

$\square$

Definition 5.11.4 The value of a flow, denoted $\val(f)$, is $\sum_{e\in E_s^+} f(e)-\sum_{e\in E_s^-}f(e)$. A maximum flow in a network is any flow $f$ whose value is the maximum among all flows.

We next seek to formalize the notion of a "bottleneck'', with the goal of showing that the maximum flow is equal to the amount that can pass through the smallest bottleneck.

Definition 5.11.5 A cut in a network is a set $C$ of arcs with the property that every path from $s$ to $t$ uses an arc in $C$, that is, if the arcs in $C$ are removed from the network there is no path from $s$ to $t$. The capacity of a cut, denoted $c(C)$, is $$\sum_{e\in C} c(e).$$ A minimum cut is one with minimum capacity. A cut $C$ is minimal if no cut is properly contained in $C$.

Note that a minimum cut is a minimal cut. Clearly, if $U$ is a set of vertices containing $s$ but not $t$, then $\overrightharpoon U$ is a cut.

Lemma 5.11.6 Suppose $C$ is a minimal cut. Then there is a set $U$ containing $s$ but not $t$ such that $C=\overrightharpoon U$.

Proof.
Let $U$ be the set of vertices $v$ such that there is a path from $s$ to $v$ using no arc in $C$.

Suppose that $e=(v,w)\in C$. Since $C$ is minimal, there is a path $P$ from $s$ to $t$ using $e$ but no other arc in $C$. Thus, there is a path from $s$ to $v$ using no arc of $C$, so $v\in U$. If there is a path from $s$ to $w$ using no arc of $C$, then this path followed by the portion of $P$ that begins with $w$ is a walk from $s$ to $t$ using no arc in $C$. This implies there is a path from $s$ to $t$ using no arc in $C$, a contradiction. Thus $w\notin U$ and so $e\in \overrightharpoon U$. Hence, $C\subseteq \overrightharpoon U$.

Suppose that $e=(v,w)\in \overrightharpoon U$. Then $v\in U$ and $w\notin U$, so every path from $s$ to $w$ uses an arc in $C$. Since $v\in U$, there is a path from $s$ to $v$ using no arc of $C$, and this path followed by $e$ is a path from $s$ to $w$. Hence the arc $e$ must be in $C$, so $\overrightharpoon U\subseteq C$.

We have now shown that $C=\overrightharpoon U$.

$\square$

Now we can prove a version of the important max-flow, min cut theorem.

Theorem 5.11.7 Suppose in a network all arc capacities are integers. Then the value of a maximum flow is equal to the capacity of a minimum cut. Moreover, there is a maximum flow $f$ for which all $f(e)$ are integers.

Proof.
First we show that for any flow $f$ and cut $C$, $\val(f)\le c(C)$. It suffices to show this this for a minimum cut $C$, and by lemma 5.11.6 we know that $C=\overrightharpoon U$ for some $U$. Using the proof of theorem 5.11.3 we have: $$ \val(f) = \sum_{e\in\overrightharpoon U} f(e)-\sum_{e\in\overleftharpoon U}f(e) \le \sum_{e\in\overrightharpoon U} f(e) \le \sum_{e\in\overrightharpoon U} c(e) = c(\overrightharpoon U). $$ Now if we find a flow $f$ and cut $C$ with $\val(f)=c(C)$, it follows that $f$ is a maximum flow and $C$ is a minimum cut. We present an algorithm that will produce such an $f$ and $C$.

Given a flow $f$, which may initially be the zero flow, $f(e)=0$ for all arcs $e$, do the following:

    0. Let $U=\{s\}$.

    Repeat the next two steps until no new vertices are added to $U$.

    1. If there is an arc $e=(v,w)$ with $v\in U$ and $w\notin U$, and $f(e)< c(e)$, add $w$ to $U$.

    2. If there is an arc $e=(v,w)$ with $v\notin U$ and $w\in U$, and $f(e)>0$, add $v$ to $U$.

When this terminates, either $t\in U$ or $t\notin U$. If $t\in U$, there is a sequence of distinct vertices $s=v_1,v_2,v_3,\ldots,v_k=t$ such that for each $i$, $1\le i< k$, either $e=(v_i,v_{i+1})$ is an arc with $f(e)< c(e)$ or $e=(v_{i+1},v_i)$ is an arc with $f(e)>0$. Update the flow by adding $1$ to $f(e)$ for each of the former, and subtracting $1$ from $f(e)$ for each of the latter. This new flow $f'$ is still a flow: In the first case, since $f(e)< c(e)$, $f'(e)\le c(e)$, and in the second case, since $f(e)>0$, $f'(e)\ge 0$. It is straightforward to check that for each vertex $v_i$, $1< i< k$, that $$\sum_{e\in E_{v_i}^+}f'(e)=\sum_{e\in E_{v_i}^-}f'(e). $$ In addition, $\val(f')=\val(f)+1$. Now rename $f'$ to $f$ and repeat the algorithm.

Eventually, the algorithm terminates with $t\notin U$ and flow $f$. This implies that for each $e=(v,w)$ with $v\in U$ and $w\notin U$, $f(e)=c(e)$, and for each $e=(v,w)$ with $v\notin U$ and $w\in U$, $f(e)=0$. The capacity of the cut $\overrightharpoon U$ is $$\sum_{e\in\overrightharpoon U} c(e).$$ The value of the flow $f$ is $$ \sum_{e\in\overrightharpoon U} f(e)-\sum_{e\in\overleftharpoon U}f(e)= \sum_{e\in\overrightharpoon U} c(e)-\sum_{e\in\overleftharpoon U}0= \sum_{e\in\overrightharpoon U} c(e). $$ Thus we have found a flow $f$ and cut $\overrightharpoon U$ such that $$ \val(f) = c(\overrightharpoon U), $$ as desired.

$\square$

The max-flow, min-cut theorem is true when the capacities are any positive real numbers, though of course the maximum value of a flow will not necessarily be an integer in this case. It is somewhat more difficult to prove, requiring a proof involving limits.

We have already proved that in a bipartite graph, the size of a maximum matching is equal to the size of a minimum vertex cover, theorem 4.5.6. This turns out to be essentially a special case of the max-flow, min-cut theorem.

Corollary 5.11.8 In a bipartite graph $G$, the size of a maximum matching is the same as the size of a minimum vertex cover.

Proof.
Suppose the parts of $G$ are $X=\{x_1,x_2,\ldots,x_k\}$ and $Y=\{y_1,y_2,\ldots,y_l\}$. Create a network as follows: introduce two new vertices $s$ and $t$ and arcs $(s,x_i)$ for all $i$ and $(y_i,t)$ for all $i$. For each edge $\{x_i,y_j\}$ in $G$, let $(x_i,y_j)$ be an arc. Let $c(e)=1$ for all arcs $e$. Now the value of a maximum flow is equal to the capacity of a minimum cut.

Let $C$ be a minimum cut. If $(x_i,y_j)$ is an arc of $C$, replace it by arc $(s,x_i)$. This is still a cut, since any path from $s$ to $t$ including $(x_i,y_j)$ must include $(s,x_i)$. Thus, we may suppose that $C$ contains only arcs of the form $(s,x_i)$ and $(y_i,t)$. Now it is easy to see that $$K=\{x_i\vert (s,x_i)\in C\}\cup\{y_i\vert (y_i,t)\in C\}$$ is a vertex cover of $G$ with the same size as $C$.

Let $f$ be a maximum flow such that $f(e)$ is an integer for all $e$, which is possible by the max-flow, min-cut theorem. Consider the set of edges $$M=\{\{x_i,y_j\}\vert f((x_i,y_j))=1\}.$$ If $\{x_i,y_j\}$ and $\{x_i,y_m\}$ are both in this set, then the flow out of vertex $x_i$ is at least 2, but there is only one arc into $x_i$, $(s,x_i)$, with capacity 1, contradicting the definition of a flow. Likewise, if $\{x_i,y_j\}$ and $\{x_m,y_j\}$ are both in this set, then the flow into vertex $y_j$ is at least 2, but there is only one arc out of $y_j$, $(y_j,t)$, with capacity 1, also a contradiction. Thus $M$ is a matching. Moreover, if $U=\{s,x_1,\ldots,x_k\}$ then the value of the flow is $$ \sum_{e\in\overrightharpoon U}f(e)-\sum_{e\in\overleftharpoon U}f(e)= \sum_{e\in\overrightharpoon U}f(e)=|M|\cdot1=|M|. $$ Thus $|M|=\val(f)=c(C)=|K|$, so we have found a matching and a vertex cover with the same size. This implies that $M$ is a maximum matching and $K$ is a minimum vertex cover.

$\square$

Exercises 5.11

Ex 5.11.1 Connectivity in digraphs turns out to be a little more complicated than connectivity in graphs. A digraph is connected if the underlying graph is connected. (The underlying graph of a digraph is produced by removing the orientation of the arcs to produce edges, that is, replacing each arc $(v,w)$ by an edge $\{v,w\}$. Even if the digraph is simple, the underlying graph may have multiple edges.) A digraph is strongly connected if for every vertices $v$ and $w$ there is a walk from $v$ to $w$. Give an example of a digraph that is connected but not strongly connected.

Ex 5.11.2 A digraph has an Euler circuit if there is a closed walk that uses every arc exactly once. Show that a digraph with no vertices of degree 0 has an Euler circuit if and only if it is connected and $\d^+(v)=\d^-(v)$ for all vertices $v$.

Ex 5.11.3 A tournament is an oriented complete graph. That is, it is a digraph on $n$ vertices, containing exactly one of the arcs $(v,w)$ and $(w,v)$ for every pair of vertices. A Hamilton path is a walk that uses every vertex exactly once. Show that every tournament has a Hamilton path.

Ex 5.11.4 Interpret a tournament as follows: the vertices are players. If $(v,w)$ is an arc, player $v$ beat $w$. Say that $v$ is a champion if for every other player $w$, either $v$ beat $w$ or $v$ beat a player who beat $w$. Show that a player with the maximum number of wins is a champion. Find a 5-vertex tournament in which every player is a champion.