Network Flows

Context

A flow network is a directed graph in which each edge can represent a conduit, a channel, or a pipe through which a substance can flow. So, a flow network can model an oil or a water distribution network. It can also be used for modeling supply and demand scenarios, for representing traffic congestion, and can essentially be used in a host of other situations that conform to the notion of flowing material.

For each problem, a flow network may be defined with a little variation. Typically, some numeric values are associated with each edge or vertex of the network.

The apparatus

In this lesson, we introduce two problems: the max-flow problem and the min-cut problem. However, to describe these, we need to first introduce some terminologies.

• A flow network is a directed graph $G=(V,E)$ where each edge has an associated numeric value called the capacity of that edge. The capacity of an edge $e$ is denoted $C(e)$. When an edge is represented as an ordered pair $(u,v)$, its capacity is denoted $C(u,v)$. The capacity $C(e)$ of an edge $e$ represents the capacity of the physical channel represented by $e$ through which material can flow. We assume that $C(e) \geq 0$ for each edge $e$.

  We may wonder why we aren’t continuing to use the expression “weighted, directed graphs” instead of flow networks. The short answer to this is that it’s tradition.

• We assume that a flow network has a single source vertex from which the material flows and a single sink vertex into which the material flows. The vertices that are designated as the source and sink vertices are denoted $s$ and $t$, respectively.

• We refer to all vertices other than the source and sink as intermediate vertices.

An example of a flow network is shown below, where the edge labels represent the capacities.

What’s a flow?

The flow in a network is best expressed as a function $f$ that assigns a numeric quantity to each edge. For a given flow function $f$, the flow along an edge $e$ or $(u,v)$ is denoted $f(e)$ or $f(u,v)$, respectively.

Note: The flow in a flow network is not an inherent part of the definition of the network since different amounts of material can flow through it at different times. So, many functions can serve as legitimate flow functions for a particular flow network.

For a function $f$ to meaningfully express the concept of a flow, we impose the following constraints:

1. We make the commonsensical assumption that the flow along each edge $e$ is nonnegative and that it is bounded by that edge’s capacity:

   $$\begin{array}{r}{\displaystyle f}\end{array}$$ ...