13.1: Basic Notation and Terminology

A directed graph in which for each pair of vertices x,y at most one of the directed edges \((x,y)\) and \((y,x)\) between them is present is called an oriented graph. The basic setup for a network flow problem begins with an oriented graph \(G\), called a network, in which we have two special vertices called the source and the sink. We use the letter \(S\) to denote the source, while the letter \(T\) is used to denote the sink (terminus). All edges incident with the source are oriented away from the source, while all edges incident with the sink are oriented with the sink. Furthermore, on each edge, we have a non-negative capacity, which functions as a constraint on how much can be transmitted via the edge. The capacity of the edge \(e=(x,y)\) is denoted \(c(e)\) or by \(c(x,y)\). In a computer program, the nodes of a network may be identified with integer keys, but in this text, we will typically use letters in labeling the nodes of a network. This helps to distinguish nodes from capacities in diagrams of networks. We illustrate a network in Figure 13.1. The numbers associated with the edges are their capacities, so, for instance, \(c(E,B)=24\) and \(c(A,T)=56\).

Figure 13.1. A Network

A flow \(ϕ\) in a network is a function which assigns to each directed edge \(e=(x,y)\) a non-negative value \(ϕ(e)=ϕ(x,y)≤c(x,y)\) so that the following conservation laws hold:

1. \(\sum_{x}ϕ(S,x)= \sum_{x}ϕ(x,T)\), i.e., the amount leaving the source is equal to the amount arriving at the sink. This quantity is called the value of the flow \(ϕ\).
2. For every vertex \(y\) which is neither the source nor the sink the amount leaving \(y\) is equal to the amount entering \(y\). That is, \(\sum_{x}ϕ(x,y)= \sum_{x}ϕ(y,x)\).

We illustrate a flow in a network in Figure 13.2.

Figure 13.2. A Network Flow

In this figure, the numbers associated with each edge are its capacity and the amount of flow that \(ϕ\) places on that edge. For example, the edge \((E,D)\) has capacity 20 and currently carries a flow of 8. (Since \(ϕ(x,y)≤c(x,y)\), it is always easy to determine which number is the capacity and which is the flow.) The value of this flow is \(30=ϕ(S,F)+ϕ(S,B)+ϕ(S,E)=ϕ(A,T)+ϕ(C,T)\). To see that the second conservation law holds at, for example, vertex \(B\), note that the flow into \(B\) is \(ϕ(S,B)+ϕ(E,B)+ϕ(D,B)=20\) and the flow out of \(B\) is \(ϕ(B,F)+ϕ(B,A)+ϕ(B,C)=20\).

Given a network, it is very easy to find a flow. We simply assign \(ϕ(e)=0\) for every edge \(e\). It is very easy to underestimate the importance of this observation, actually. Network flow problems are a special case of a more general class of optimization problems known as linear programs, and in general, it may be very difficult to find a feasible solution to a linear programming problem. In fact, conceptually, finding a feasible solution—any solution—is just as hard as finding an optimal solution.