ABSTRACT
A network is a directed graph used to model the distribution of goods, data, or commodities, etc., from their centers of production to their destinations. For example, Figure 8.1 shows a network in which goods are produced at node s, and shipped to node t. Each directed edge has a limited capacity, being the maximum number of goods that can be shipped through that channel per time period (e.g., 3 kilobytes per second or 3 truckloads per day). The diagram indicates the capacity as a positive integer associated with each edge. The actual number of goods shipped on each edge is shown in square brackets beside the capacity. This is called the flow on that edge. It is a non-negative integer less that or equal to the capacity. Goods cannot accumulate at any node; therefore the total in-flow at each node must equal the out-flow at that node. The problem is to find the distribution of goods that maximizes the net flow from s to t.
