mth221 r2 network flows case study Essay

7726 Words Dec 12th, 2014 31 Pages
23
Network Flows

Author: versity. Arthur M. Hobbs, Department of Mathematics, Texas A&M Uni-

Prerequisites: The prerequisites for this chapter are graphs and trees. See
Sections 9.1 and 10.1 of Discrete Mathematics and Its Applications.

Introduction
In this chapter we solve three very diﬀerent problems.

Example 1
Joe the plumber has made an interesting oﬀer. He says he has lots of short pieces of varying gauges of copper pipe; they are nearly worthless to him, but for only 1/5 of the usual cost of installing a plumbing connection under your house, he will use a bunch of T- and Y-joints he picked up at a distress sale and these small pipes to build the network shown in Figure 1. He claims that it will deliver three gallons per minute
For the second reason, we need only realize that problems of this sort are likely to be programmed on a computer, and computers are much better at examining local situations than global ones.
However, using the ﬁrst view, we can detect rules that must be satisﬁed by a ﬂow described as in the second view. To state these rules easily, we need to deﬁne several terms.

412

Applications of Discrete Mathematics

Let A be a subset of V in directed graph G = (V, E), and let B = V − A.
Let c(A, B) be the sum of the capacities of the edges directed in G from vertices in A to vertices in B, and let c(B, A) be the sum of the capacities of the edges directed in G from vertices in B to vertices in A. Similarly, let f (A, B) be the amount of ﬂow from A to B, i.e., the sum of the ﬂows in the edges directed from vertices in A to vertices in B. Let f (B, A) be the amount of ﬂow from B to A. Then the net flow F (A) from A is deﬁned by
F (A) = f (A, B) − f (B, A).
For example, in Figure 4, if A = {s, b}, then f (A, B) = 2 and f (B, A) = 0.
Hence F (A) = 2. Similarly, F ({b}) = 2 − 2 = 0 and F ({s, t}) = 2 − 2 = 0, while F ({b, t}) = 2 − 2 − 2 = −2.
Note that F ({s}) is the total number of units of ﬂow moving from the source to the sink in the graph. Our objective is to ﬁnd a ﬂow for which F ({s}) is maximum.
Since every unit of ﬂow