# MATHEMATICS

Example 11 Solve the problem of Example 2.

Solution: Represent the river system as a graph by assigning a vertex to the town s, to the ocean t, and to each of the intersections of the channels. Join two vertices with an undirected edge if a river channel joins the corresponding points in the river system, and give the edge a capacity equal to the number of mines it takes to block the corresponding channel. The resulting graph is shown in Figure 12. Applying Algorithm 1 with the lexicographic ordering (see Exercise 7), we obtain a maximum flow of 7 with a minimum cut consisting of edges (d, g), (e, g), (e, h), (f, h), and (f, l). Thus the solution to the problem of Example 2 is to mine the channels corresponding to these five edges with a total of 7 mines.

Figure 12. The river delta of Example 2 converted to a ca- pacitated s,t-graph.

Examples 9 and 11 point the way to the following theorem, which shows that Algorithm 1 solves our problem.

Theorem 4 The Max-flow Min-cut Theorem The maximum s, t-flow in a capacitated s, t-graph is equal to the capacity of a minimum s, t-cut. Further, Algorithm 1 finds such a maximum flow and minimum cut.

Proof: We already know from Theorem 3 that the maximum flow amount

F ({s}) ≤ c(A′, V (G) − A′)

for any minimum capacity s, t-cut (A′, V (G) − A′). It will therefore suffice to find a flow f and an s, t-cut (A, V (G) − A) such that F (A) = c(A, V (G) − A) for the flow f .

Let Algorithm 1 run to completion, producing a flow f . Let A be the set of vertices labeled in the last pass through the algorithm. Since s always has a label, and since t could not be labeled on the last pass, (A, V (G) − A) is an s, t-cut, and F (A) is the amount of flow going from s to t as described by f .

424 Applications of Discrete Mathematics

Consider an edge (a, b) with a ∈ A and b ∈ V (G) − A. Since a is labeled and b is not, we must have f(a, b) = c(a, b) by the algorithm. Next, consider an edge (b′, a′) with a′ ∈ A and b′ ∈ V (G) − A. Again, we note that a′ has a label and b′ does not; hence by the algorithm, f(b′, a′) = 0. Thus

F (A) = c(A, V (G) − A). (1) Since the maximum flow cannot be larger than c(A, V (G) − A), F (A) must be a maximum flow. The equality in (1) completes the proof of this theorem.

Complexity Given a capacitated s, t-graph G, let a be the largest edge capacity, let e be the number of edges of G, and let v be the number of vertices of G. In each search for an augmenting chain in the first half of Algorithm 1, we may have to examine nearly all of the edges, each from both ends, so each pass through that half of the algorithm takes O(e) steps. Since each augmenting chain increases the flow by at least one unit, there can be no more than a + 1 searches for an augmenting chain. The second half of Algorithm 1 requires only O(p) steps, where p is the number of edges in the augmenting chain. Thus the complexity of Algorithm is governed by the first half of the algorithm and is O(ae).

Sometimes the capacity a is many orders of magnitude larger than the number e of edges or the number v of vertices. In such a case, we would like a measure of the complexity of the algorithm that does not depend on a. Edmonds and Karp [2] have shown that, if vertices are scanned in the same order in which they receive labels, instead of using the lexicographic ordering, then the complexity is O(v5).

Assignment of Graders

Example 12 Set up Example 3 as a flow graph problem.

Solution: Referring to the table given in Example 3, represent Students 1, 2, and 3 by vertices S1, S2, and S3, and represent Courses 1, 2, 3, and 4 by vertices C1, C2, C3, and C4, respectively. Let s and t be two additional vertices. Join vertex s to S1, S2, and S3 by directed edges, and assign capacity c(s, Si) equal to the number of sections Student i is willing to grade. Join each of vertices C1, C2, C3, and C4 to vertex t by directed edges, and assign capacity c(Ci, t) equal to the number of sections of Course i being offered. For each i and j, add edge (Si, Cj) if Student i is qualified to grade for Course j (i.e., if a “yes” appears in the row for Student i and the column for Course j of Table 1). For

Chapter 23 Network Flows 425

each such edge, let c(Si, Cj) = ∞. The problem then becomes one of finding a maximum flow in the graph of Figure 13.

Figure 13. The flow graph for the grader assignment prob- lem (Example 3).

By Theorem 4, the maximum flow in Figure 13 equals the capacity of the minimum cut. Let us look at a maximum flow as perceived under View 1 discussed early in this chapter. Each unit of flow passes from s to a vertex Si, thence to a vertex Cj , and finally to vertex t. We may regard the unit as specifying an assignment of Student i to a section of Course j. For a fixed value of i, the number of units of flow passing through Si cannot exceed c(s, Si), which is the maximum number of sections for which Student i wants to grade, so the assignment view of the units of flow cannot assign a student to more sections than he desires. Similarly, for a fixed value of j, the number of units passing through Cj cannot exceed c(Cj , t), which is the number of sections needing graders. Thus no course will be assigned too many graders. Ideally, (V (G) − {t}, {t}) will turn out to be a minimum cut. Then by Theorem 4, the maximum flow will equal to capacity of that cut, and every section of every course will be assigned a grader.

Example 13 Solve Example 3.

Solution: Applying Algorithm 1 with lexicographic ordering to the graph of Figure 13, we find the flow shown in Figure 14, where the last labels and the associated tree (in bold edges) are also shown. From Figure 14, we see that F ({s}) = c(V (G) − {t}, {t}) as we hoped, so every section will get a grader. Further, interpreting the flow, we are told to assign Student 1 to all three

426 Applications of Discrete Mathematics

sections of Course 1, Student 2 to the one section of Course 3 and one of the sections of Course 4, and Student 3 to the one section of Course 2 and to the other section of Course 4.

Figure 14. Maximum flow, associated tree, and cut for the grader assignment problem (Example 3).

The generalization of Examples 3, 12, and 13 to other assignments is straightforward. The possibilities in such assignments are that the students become fully assigned without finding graders for every section, or that, as in the case of Example 3, the sections receive enough graders but some students do not work as much as they want, or that every student gets enough work and every section receives a grader, or that some students do not get enough work while some sections are not graded. The last case is illustrated in one of the examples of Exercise 8. In every case, a maximum flow obtained by using Al- gorithm 1 will determine an assignment of as many graders to as many sections as possible.

Historical Note The 1950s were exciting years at the RAND Corporation, which had been set up after World War II to provide the government with well-founded scientific advice. Among the workers there were Lester Ford, Jr. and Ray Fulkerson, developers of the theory presented in this chapter, George Dantzig [1], one of the most important developers of linear programming, and Merrill Flood

Chapter 23 Network Flows 427

and Selmer Johnson, who worked with Fulkerson and Dantzig on the traveling salesman problem (see the “Traveling Salesman Problem” chapter in this book).

The problems which led to the theory that has been presented in this chap- ter were posed by the Air Force to Ford and Fulkerson in 1955 [4] as a problem in railway traffic flow. Their first work on it involved linear programming, but as they refined their understanding of the problem and available methods, they hit on the flow algorithm and labeling scheme we have presented here. Their development of the work was so fast that the entire theory of this chapter was published by 1957 [3].

Suggested Readings

1. G. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, N. J., 1998.

2. J. Edmonds and R. Karp, “Theoretical improvements in algorithmic effi- ciency for network flow problems”, J. ACM , Vol. 19, 1972, pp. 248–264.

3. L. Ford, Jr. and D. Fulkerson, “A simple algorithm for finding maximal network flows and an application to the Hitchcock problem”, Canadian J. Math., Vol. 9, 1957, pp. 210–218.

4. L. Ford, Jr., and D. Fulkerson, Flows in Networks, Princeton University Press, Princeton, N. J., 1962.

Exercises

In Exercises 1 and 2, one unit of flow is shown in the graph. Starting with that flow, use Algorithm 1 with the lexicographic ordering to find a maximum flow and a minimum cut in the graph.

1.

428 Applications of Discrete Mathematics

2.

3. Using the graph and capacities of Exercise 1, find a maximum flow and minimum cut using Algorithm 1, but this time use the Edmonds and Karp ordering in which vertices are scanned in the same order in which they receive labels, instead of using the lexicographic ordering.

4. Using the graph and capacities of Exercise 2, find a maximum flow and minimum cut using Algorithm 1, but this time use the Edmonds and Karp ordering in which vertices are scanned in the same order in which they receive labels, instead of using the lexicographic ordering.

In Exercises 5 and 6, find a maximum flow and a minimum cut in the undi- rected graph by using Algorithm 1 with the lexicographic ordering.

5.

6.

7. Apply Algorithm 1 with the lexicographic ordering to the graph shown in Figure 12.

8. For each of the following tables, find a maximal assignment of graders to sections of courses, as in Example 3.

Chapter 23 Network Flows 429

(a)

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

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

# Sec. Needed 4 1 1

(b)

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

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

# Sec. Needed 2 2 2 1

��9. An undirected graph G is bipartite if V (G) is the disjoint union of two nonempty sets V1 and V2 such that every edge of G joins a vertex of V1 with a vertex of V2. A matching in graph G is a set M of edges of G such that no two of the edges in M meet the same vertex of G. A covering of graph G is a set C of vertices of G such that every edge of G has at least one end in C. Prove König’s Theorem: If G is an undirected bipartite graph, then the maximum number of edges possible in a matching in G equals the minimum number of vertices possible in a covering of G. Hint: use a source and sink connected to different subsets of V (G) by edges of capacity 1.

��10. (This problem requires information from the beginning of the chapter “Net- work Survivability”.) Recall from that chapter that a block is a graph with- out cut vertices and that a graph is 2-connected if it is a block with at least two edges. Show that an undirected graph G with at least three vertices is 2-connected if and only if, for any two distinct vertices v and w of G, there are two simple paths joining v and w which have only the vertices v and w in common. Note: This is the 2- connected case of Menger’s theorem. Hint: Replace each vertex x of G other than v and w by two new ver- tices x1 and x2 and a directed edge (x1, x2). For each edge {x, y} of G, add edges (x2, y1) and (y2, x1), treating v and w suitably. Assign appropriate capacities and use Algorithm 1 and Theorem 4.

430 Applications of Discrete Mathematics

11. In the new factory of the Sampson Manufacturing Company, the workers are to be assigned to machines. One worker will use just one machine on the job. Each worker has stated in his job application which types of machines he is competent to operate, and the company knows how many of each type of machine they have to be manned. Describe how the problem of making the assignments can be solved by using a flow graph.

12. The Computer Information Company (CIC) sells information to computer owners who call in by modem. Due to the quality of their service, their telephone lines are very busy. But it turns out that their customers are not always able to get through to them, even when the company has idle lines coming in. It is obvious that the problem lies with the telephone network, but where is the bottleneck? Investigating the problem, the company finds that any call coming out of a switching center owned by the telephone company can reach the next switching center; the problem seems to be that some switching centers do not have enough capacity to handle all of the calls for CIC that come to them. Data from the telephone company tells CIC how many calls are coming into each switching center from local users of CIC and what the pass-through capacity of each switching center is. Many calls pass through several switching centers on their way to the CIC office. How can CIC determine which switching centers are blocking their calls (thus helping CIC management decide where they might build a subsidiary CIC station to reduce the pass-through load on the inadequate switches)? Hint: Try a flow from CIC to the users, connect a single sink to the switches with edges whose capacities are the number of local users attached to the switches, and replace switches in the telephone network by weighted directed edges.

Computer Projects

1. Write a computer program to find a maximum flow and a minimum cut in a directed capacitated s, t-graph.

2. Write a computer program to find a maximum matching in a bipartite graph. (See Exercise 9 and its solution for the necessary ideas and defini- tions.)