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 different problems.

Example 1
Joe the plumber has made an interesting offer. 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
…show more content…
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 first view, we can detect rules that must be satisfied by a flow described as in the second view. To state these rules easily, we need to define 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 flow from A to B, i.e., the sum of the flows in the edges directed from vertices in A to vertices in B. Let f (B, A) be the amount of flow from B to A. Then the net flow F (A) from A is defined 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 flow moving from the source to the sink in the graph. Our objective is to find a flow for which F ({s}) is maximum.
Since every unit of flow

Related Documents