Network Flows

One often uses graphs to model transportation networks - networks whose edges carry some sort of traffic and whose nodes act as “switches” passing traffic between different edges. The flow may be of oil or water in pipelines, electricity, or phone calls, emails in networks, or traffic in networks. Consider an example of high-way system in which the edges are highways and the nodes are interchanges; or a computer network in which the edges are the links that carry packets and the nodes are switches, or a fluid network in which edges are pipes and that carry liquid, and the nodes are junctures where pipes plugged together. The network models of this category have several ingredients: capacities on edges, including how much they can carry; source nodes in the graph, which generate traffic; and the traffic itself which is transmitted across the edges.

Networks are important for both electronic communication and for transport of goods. The problem of efficiently moving entities (such as bits, people, or products) from one place to other in an underlying network is modeled by network flow. The problem plays central role in the fields of operations research and computer science, and much emphasis has been placed on the design of efficient algorithms for solving it. Many of the basic algorithms plays important role in understanding the network flow algorithms.

The matching, we studied earlier, is a special case of flow problem - match the flow with capacity of edge so that over all flow is maximum. Assignment is a generalization of the matching problem to the wighted case.

Flow network. A flow network $G = (V, E)$ is a directed graph, with two specially marked nodes, namely a single source node $s \in V$ and single sink node $t \in V$. The $s, t$ are called internal nodes. In addition, there is a capacity function $c : V \times V \mapsto \mathbb{R}$ that maps edges to positive real numbers.

Before we proceed further, we shall make some assumptions: 1) no edge enters the source $s$, and no edge leaves $t$, and 2) there is at least one edge incident on each node. The figure  shows an example of such network, with capacity $c$ of each shown along with the edges.

Figure: A flow network.

Flow. An s-t is a function $f : V \times V \mapsto \mathbb{R}$. The value $f(u, v)$ is amount of flow in edge $(u, v)$.

A flow function is required to satisfy the following constraints:

• Capacity constraints. For all $u, v \in V$, $0 \leq f(u, v) \leq c(u, v)$,

• Skew symmetry constraint. For an edge $e = (u, v)$, there is $f(u, v) = -f(v, u)$

• Flow conservation. For all $u \in V - \{s, t\}$, we require

  $$\sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v).$$ (2.1)

  Whenever, $(u, v) \notin E$, i.e., there can be no flow from $u$ to $v$, and $f(u, v) = 0$.

The capacity constraint says that the total flow on an edge does not exceed its capacity. The skew symmetry condition says that the flow on an edge is the negative of the flow in the reverse direction. The flow conservation constraint says that the total net flow out of any vertex other than the source and sink is zero. The value of this of net flow flow from $s$ is defined as :

$$\vert f\vert = \sum_{v \in V} f(s, v)$$ (2.2)

In the maximum-flow problem the objective is to find a flow function that satisfies these three constraints, and also maximizes the total flow value $\vert f\vert$ from source $s$.

The above formulation of the network flow problem is powerful enough to capture generalization where there are many sources and sinks (single commodity flow), and where both vertices and edges have capacity constraints.

We call the non-negative quantity $f(u, v)$ the flow from vertex $u$ to vertex $v$, defined for $(s, v)$ as:

$$\vert f\vert = \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s),$$ (2.3)

that is, total flow out of a source minus the flow into the source. Typically, the value $\sum_{v \in V} f(v, s)$ will be zero as there is no flow into the source. In the maximum-flow problem we are given the flow network $G$ with source $s$ and sink $t$, and we wish to find a flow of maximum value.

Example 2.1   Consider the example in figure , where Figure (a) shows the capacities $c(u, v)$ of all edges, and figure (b) shows flows/capacities, i.e., $f(u, v)/c(u, v)$ of all edges.

Figure: (a) A flow network $G = (V, E)$, for transporting trucks, having capacity $c(u, v)$ at each edge, (b) A flow in $G$ with $\vert f\vert = 19$. Each edge is labeled as $f(u, v)/c(u, v)$.