# 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

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

*…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 ﬁ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

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