MATHEMATICS

Network Flows

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

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 at maximum flow. He has a good reputation, so you are sure the network he builds will not leak and will cost what he promises, but he is no mathematician. Will the network really deliver as much water per minute as he claims?

408

Chapter 23 Network Flows 409

Figure 1. A plumber’s nightmare.

Example 2 We want to block access to the sea from inland town s on river R. We can do this by dropping mines in the river, but because the river spreads out in a wide delta with several outlets, the number of mines required depends on where we drop them. The number of mines required in a channel ranges from a high of 20 mines in R to a low of 1 in some channels, as shown in Figure 2. In that figure, each channel is shown with a number indicating how many mines will block it. What is the smallest number of mines needed to block off s’s access to the sea, and where should the mines be placed?

Figure 2. Delta system of river R and numbers of mines needed to close channels.

Example 3 At Major University, Professor Johnson is asked to hire graders for 100 sections spread among 30 different courses. Each grader may work for one, two, or three sections, with the upper bound being the grader’s choice, but the number actually assigned being Professor Johnson’s choice. Professor Johnson contacts the potential graders, learns from each both his choice of number of sections and which courses he is competent to grade, and makes a table showing this information, together with the number of sections of each course being offered. Because the real problem is too large to use as an example here, Table 1 gives a smaller example. How should the assignment of graders be made?

In this chapter, we begin with Example 1, solve Example 2 on the way to solving Example 1, and then solve Example 3 by using the theory developed. Many more kinds of problems are solved using the methods of this chapter in the book Flows in Networks by Ford and Fulkerson [4].

410 Applications of Discrete Mathematics

Course Course Course Course Max # Sec. 1 2 3 4 Wanted

Student 1 yes yes no no 3 Student 2 yes no yes yes 2 Student 3 no yes yes yes 3

# Sec. Needed 3 1 1 2

Table 1. Graders and courses.

Flow Graphs In Example 1, we have a network of pipes that can be modeled by a graph with weights on the edges. Here, the T- and Y-joints and the inlet and outlet are represented by vertices, the pipes are represented by edges, and the weight on each edge is the capacity of the corresponding pipe in gallons per minute. Moreover, in this example we have water flowing from vertex s to vertex t as labeled in Figure 1. For a general solution to the problem, let us use the following terminology.

Definition 1 Let G be a graph in which there are two designated vertices, one the source of all flow, and the other the sink, or recipient of all flow. At every other vertex, the amount of flow into the vertex equals the amount of flow out of the vertex. The flows are limited by weights, or capacities, on the edges. The edges may be undirected or directed. We designate the capacity of an edge e by c(e). We will call a graph with capacities on the edges, a source s, and a sink t, a capacitated s, t-graph.

Because we are searching for flows, we will show the flow through each edge of a capacitated s, t-graph as another number on the edge. To prevent confusion, we will designate the capacity of an edge and the amount of flow in it by a pair of numbers in parentheses on the edge, the capacity being the first number of the pair.

Example 4 Find a flow in the graph of Figure 3.

Solution: The path p = s, b, a, t extends from s to t, and seen as a sequence of pipes, the largest amount of flow that could travel along it is the minimum of the capacities of the pipes comprising it. This minimum is 2, which is c(s, b)

Chapter 23 Network Flows 411

Figure 3. A small capacitated s,t-graph.

and also c(b, a). Thus we put number pairs on each of the edges, the second entry being 2 for each edge in the path and 0 for the other two edges. The result is shown in Figure 4.

Figure 4. Graph of Figure 3 with flow along path s,b,a,t.

There are two ways we can view a flow, and Example 4 illustrates them both. One view is to trace out the path from the source to the sink of one or more units of flow. In the example, path p is such a path. The other view is to measure the total flow in each edge of the graph. This view is shown in the example by our placing the amount of flow along each edge. Since there is actually only one flow, namely the orderly procession of fluid from the source to the sink through the network, these two views must be equivalent.

When solving the problem of finding maximum flows through the graph, the second view is preferable for two reasons. If we are searching a very large network by hand, it may well be impossible for us to find a best set of paths from the source to the sink, especially after several paths for flow have already been found. Searching for such paths is very like searching through a maze, since flow in an edge limits, perhaps to 0, the additional flow that may pass through that edge. 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 that enters a vertex other than the source or sink must go out of that vertex, we have the following theorem.

Theorem1 Suppose G is a directed capacitated s, t-flow graph, and suppose A ⊆ V (G).

1. If s ∈ A and t �∈ A, then F (A) = F ({s}). 2. If t ∈ A and s �∈ A, then F (A) = −F ({s}). 3. If A ∩ {s, t} = ∅ or if {s, t} ⊆ A, then F (A) = 0.

Proof: These facts are evident because all of the material flowing goes out of the source, the material all goes into the sink, and none is lost or gained at any other vertex.

Although the definitions and theorem are given for directed graphs only, we can include undirected edges as follows. Although material can flow in either direction along an undirected edge, as a practical matter it will flow in only one direction (although we may not know in advance in which direction it will flow in a particular edge). Thus each undirected edge e = {a, b} can be regarded as a pair of directed edges (a, b) and (b, a) joining the ends of e. Since the flow could go either way, we assign the capacity c(e) of the edge e to both directed edges as c(a, b) and c(b, a). Further, using this device, we can designate the flow on the edge by f(a, b) or f(b, a) without ambiguity.

If, in the midst of an analysis, we discover we show flow going in both directions, it is clear that we can cancel the circulation in the two edges, leaving only that part of the flow which is actually passing through the pair of edges. For example, in Figure 5(a), we see a flow of 2 units from s to t, but f(a, b) = 4 while f(b, a) = 2. In Figure 5(b), the 2-unit circulation around the circuit a, b, a

Chapter 23 Network Flows 413

has been eliminated (the 2 units along edge (b, a) have canceled 2 of the units along edge (a, b)) leaving the simpler, but equally accurate, picture of 2 units flowing from s to t through the path s, a, b, t. In general, if both (a, b) and (b, a) carry non-zero flow, we treat the combined flow by placing a flow of 0 on the smaller flow edge and replacing the flow on the other one by |f(a, b)− f(b, a)|.

Figure 5. Flow graph illustrating cancellation of flow in a pair of oppositely directed edges.

Increasing the Flow

Example 5 Increase the flow in the graph of Figure 4.

Solution: In Figure 4 it is easy to see that the flow shown is not the largest possible. In fact, consider the path s, a, t. Since c(s, a) = 3 while f(s, a) = 0, we could get three more units of flow to vertex a by using the edge (s, a). Then one of those units could go on to t through (a, t) since c(a, t) = 3 while f(a, t) = 2, or c(a, t) − f(a, t) = 1. Thus we can get min(3, 3 − 2) = 1 unit of flow through s, a, t, producing the flow shown in Figure 6(a).

Figure 6. Steps in increasing flow.

In general, if we can find a sequence p = s, x1, x2, . . . , xn, t from the source s to the sink t in which every directed edge is directed in the same direction as the sequence (so that the sequence describes a path) and in which every edge has capacity exceeding the flow already in the edge, then we can increase the flow from s to t by simply adding flow to the path p. In such a case, the total amount of flow that can be added cannot exceed the additional amount that

414 Applications of Discrete Mathematics

can be forced through any one of the edges in p, so the total flow increase by using such a path p is

min e∈E(p)

(c(e) − f(e)).

But what if no such sequence of vertices exists?

Example 6 Increase the flow in the graph of Figure 6(a).

Solution: It is not obvious that the flow in this graph can be increased. However, we note that we could get c(s, a)−f(s, a) = 2 more units of flow from s to a, and if we had 2 more available at b, we could move them on through (b, t) to t. But let us rearrange the flow. If we erase the two units of flow in edge (b, a), then the two flowing through (s, b) become available at b to go out through (b, t). Further, the two additional units available at a can replace the two that used to go through (b, a) to a, thus allowing the flow of 2 units through (a, t) to continue. Thus we arrive at the flow shown in Figure 6(c).

An intermediate step can be interposed between Figures 6(a) and 6(c). This step is shown in Figure 6(b), where the flow is the same as that in Figure 6(a). What is different is a record at each vertex of a possibility of increasing flow. We may suppose that an infinite supply is always available at s, so we have labeled s with (−,∞), where the “−” indicates only that all flow begins at s. At vertex a, we see the label (+s, 2), which signifies that two units of flow could come through edge (s, a) because c(s, a) − f(s, a) = 2. At vertex b is the label (−a, 2), showing that 2 units of flow could come to b by canceling the flow on edge (b, a). The operation of cancellation is shown by the “−” attached to a in the label. Finally, t has the label (+b, 2), showing that 2 units of flow are available at t, coming from b.

Let us look at the rearrangement of Example 6 another way. Consider the “path” s, a, b, t in Figure 6(b). We increased the flow on edges (s, a) and (b, t) by two units, and we decreased the flow on edge (b, a) by the same two units. These operations are signaled by the signs attached to the first label on each vertex as described in the example. The result was the increase of flow in the graph by two units.

Since s, a, b, t is not a path in Figure 6(a) (the edge (b, a) is directed against the order of the sequence), let us give such a sequence a name of its own.

Definition 2 A chain from x0 to xn in a directed graph G is a subgraph P of G whose vertices can be placed in a sequence x0, x1, . . . , xn such that, for each i ∈ {0, 1, . . . , n − 1}, either (xi, xi+1) ∈ E(P ) or (xi+1, xi) ∈ E(P ) and no other edges are in E(P ).

Figure 7 shows an example of a chain from x0 to x5.

Chapter 23 Network Flows 415

Figure 7. A chain from x0 to x5.

Example 6 illustrates the following general principle.

Theorem 2 Suppose P with vertex sequence x0, x1, . . . , xn is a chain from the source s = x0 to the sink t = xn in a capacitated s, t-graph G, and sup- pose, for each i, either (xi, xi+1) ∈ E(P ) and c(xi, xi+1) − f(xi, xi+1) > 0, or (xi+1, xi) ∈ E(P ) and f(xi+1, xi) > 0. Let x be the smallest among the values c(xi, xi+1) − f(xi, xi+1) on edges (xi, xi+1) ∈ E(P ) and f(xi+1, xi) on edges (xi+1, xi) ∈ E(P ). Then increasing the flow by x on the edges (xi, xi+1) and decreasing it by x on the edges (xi+1, xi) of P increases F ({s}) by x.

We call a chain like that described in Theorem 2 an augmenting chain in the capacitated s, t-flow graph.

The labels on the vertices are used to find augmenting chains. Let us visualize ourselves as exploring the graph, starting at vertex s with infinitely many units of flow available to us. As we move through the graph, searching for t, we keep a record of the amounts of new flow that can reach each vertex. This record is the set of vertex labels we show in Figure 6(b).

The labels are governed by two considerations.

1. If x units of flow can reach vertex m, and if edge (m, n) exists, and if c(m, n)− f(m, n) > 0, then y = min(x, c(m, n)− f(m, n)) units can be gotten to n by following the chain from s to m already found and then pushing as much flow as possible through (m, n). (This amount of flow is the smaller of the amount available and the amount that can go through the edge.) This is signaled by placing the label (+m, y) at vertex n.

2. If x units of flow can reach vertex m, if edge (n, m) exists, and if f(n, m) > 0, then y′ = min(x, f(n, m)) units become available at n by canceling y′ units of flow from edge (n, m). The effect of the cancellation is to feed the y′ ≤ x units of flow needed at m after the cancellation by using y′ of the x units of new flow available at m, while using the y′ units that were flowing through (n, m) as the source of the new y′ units available at n.

When we label vertex n by using a label on vertex m and either edge (m, n) or edge (n, m), we say we label n from m and that we are labeling across edge (m, n) or (n, m).

We interpret the labels backwards to describe the augmenting chain. The first label on each vertex names the vertex preceding it on the chain from s found during the labeling process. For example, consider the labels on the flow

Order now and get 10% discount on all orders above $50 now!!The professional are ready and willing handle your assignment.

ORDER NOW »»