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 \(\bfG\), 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 . The numbers associated with the edges are their capacities, so, for instance, \(c(E,B)=24\) and \(c(A,T)=56\).

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

1. \(\sum_{x} \phi(S,x)= \sum_{x} \phi(x,T)\), , the amount leaving the source is equal to the amount arriving at the sink. This quantity is called the value of the flow \(\phi\).

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}\phi(x,y)= \sum_{x}\phi(y,x)\).

We illustrate a flow in a network in .

In this figure, the numbers associated with each edge are its capacity and the amount of flow that \(\phi\) places on that edge. For example, the edge \((E,D)\) has capacity \(20\) and currently carries a flow of \(8\). (Since \(\phi(x,y)\leq 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 = \phi(S,F)+\phi(S,B)+\phi(S,E)=\phi(A,T)+\phi(C,T)\). To see that the second conservation law holds at, for example, vertex \(B\), note that the flow into \(B\) is \(\phi(S,B)+\phi(E,B)+\phi(D,B) = 20\) and the flow out of \(B\) is \(\phi(B,F)+\phi(B,A)+\phi(B,C)=20\).

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.