CHAPTER 23

Graphs.
Combinatorial Optimization

Many problems in electrical engineering, civil engineering, operations research, industrial engineering, management, logistics, marketing, and economics can be modeled by graphs and directed graphs, called digraphs. This is not surprising as they allow us to model networks, such as roads and cables, where the nodes may be cities or computers. The task then is to find the shortest path through the network or the best way to connect computers. Indeed, many researchers who made contributions to combinatorial optimization and graphs, and whose names lend themselves to fundamental algorithms in this chapter, such as Fulkerson, Kruskal, Moore, and Prim, all worked at Bell Laboratories in New Jersey, the major R&D facilities of the huge telephone and telecommunication company AT&T. As such, they were interested in methods of optimally building computer networks and telephone networks. The field has progressed into looking for more and more efficient algorithms for very large problems.

Combinatorial optimization deals with optimization problems that are of a pronounced discrete or combinatorial nature. Often the problems are very large and so a direct search may not be possible. Just like in linear programming (Chap. 22), the computer is an indispensible tool and makes solving large-scale modeling problems possible. Because the area has a distinct flavor, different from ODEs, linear algebra, and other areas, we start with the basics and gradually introduce algorithms for shortest path problems (Secs. 22.2, 22.3), shortest spanning trees (Secs. 23.4, 23.5), flow problems in networks (Secs. 23.6, 23.7), and assignment problems (Sec. 23.8).

Prerequisite: none.

References and Answers to Problems: App. 1 Part F, App. 2.

23.1 Graphs and Digraphs

Roughly, a graph consists of points, called vertices, and lines connecting them, called edges. For example, these may be four cities and five highways connecting them, as in Fig. 477. Or the points may represent some people, and we connect by an edge those who do business with each other. Or the vertices may represent computers in a network and the edge connections between them. Let us now give a formal definition.

Fig. 477. Graph consisting of 4 vertices and 5 edges

Fig. 478. Isolated vertex, loop, double edge. (Excluded by definition.)

We denote vertices by letters, u, ν, … or ν₁, ν₂, … or simply by numbers 1, 2, … (as in Fig. 477). We denote edges by e₁, e₂, … or by their two endpoints; for instance, e₁ = (1, 4), e₂ = (1, 2) in Fig. 477.

An edge (ν_i, ν_j) is called incident with the vertex ν_i (and conversely); similarly, (ν_i, ν_j) is incident with ν_j. The number of edges incident with a vertex ν is called the degree of ν. Two vertices are called adjacent in G if they are connected by an edge in G (that is, if they are the two endpoints of some edge in G).

We meet graphs in different fields under different names: as “networks” in electrical engineering, “structures” in civil engineering, “molecular structures” in chemistry, “organizational structures” in economics, “sociograms,” “road maps,” “telecommunication networks,” and so on.

Digraphs (Directed Graphs)

Nets of one-way streets, pipeline networks, sequences of jobs in construction work, flows of computation in a computer, producer–consumer relations, and many other applications suggest the idea of a “digraph” (= directed graph), in which each edge has a direction (indicated by an arrow, as in Fig. 479).

Fig. 479. Digraph

Two edges connecting the same two points i, j are now permitted, provided they have opposite directions, that is, they are (i, j) and (i, j) Example. (1, 4) and (4, 1) in Fig. 479.

A subgraph or subdigraph of a given graph or digraph G = (V, E), respectively, is a graph or digraph obtained by deleting some of the edges and vertices of G, retaining the other edges of G (together with their pairs of endpoints). For instance, e₁, e₃ (together with the vertices 1, 2, 4) form a subgraph in Fig. 477, and e₃, e₄, e₅ (together with the vertices 1, 3, 4) form a subdigraph in Fig. 479.

Computer Representation of Graphs and Digraphs

Drawings of graphs are useful to people in explaining or illustrating specific situations. Here one should be aware that a graph may be sketched in various ways; see Fig. 480. For handling graphs and digraphs in computers, one uses matrices or lists as appropriate data structures, as follows.

Fig. 480. Different sketches of the same graph

Adjacency Matrix of a Graph G: Matrix A = [a_ij] with entries

Thus a_ij = 1 if and only if two vertices i and j are adjacent in G. Here, by definition, no vertex is considered to be adjacent to itself; thus, a_ii = 0. A is symmetric, a_ij = a_ji. (Why?)

The adjacency matrix of a graph is generally much smaller than the so-called incidence matrix (see Prob. 18) and is preferred over the latter if one decides to store a graph in a computer in matrix form.

Adjacency Matrix of a Digraph G: Matrix A = [a_ij] with entries

This matrix A need not be symmetric. (Why?)

Lists. The vertex incidence list of a graph shows, for each vertex, the incident edges. The edge incidence list shows for each edge its two endpoints. Similarly for a digraph; in the vertex list, outgoing edges then get a minus sign, and in the edge list we now have ordered pairs of vertices.

Sparse graphs are graphs with few edges (far fewer than the maximum possible number n(n − 1)/2, where n is the number of vertices). For these graphs, matrices are not efficient. Lists then have the advantage of requiring much less storage and being easier to handle; they can be ordered, sorted, or manipulated in various other ways directly within the computer. For instance, in tracing a “walk” (a connected sequence of edges with pairwise common endpoints), one can easily go back and forth between the two lists just discussed, instead of scanning a large column of a matrix for a single 1.

Computer science has developed more refined lists, which, in addition to the actual content, contain “pointers” indicating the preceding item or the next item to be scanned or both items (in the case of a “walk”: the preceding edge or the subsequent one). For details, see Refs. [E16] and [F7].

This section was devoted to basic concepts and notations needed throughout this chapter, in which we shall discuss some of the most important classes of combinatorial optimization problems. This will at the same time help us to become more and more familiar with graphs and digraphs.

23.2 Shortest Path Problems. Complexity

The rest of this chapter is devoted to the most important classes of problems of combinatorial optimization that can be represented by graphs and digraphs. We selected these problems because of their importance in applications, and present their solutions in algorithmic form. Although basic ideas and algorithms will be explained and illustrated by small graphs, you should keep in mind that real-life problems may often involve many thousands or even millions of vertices and edges. Think of computer networks, telephone networks, electric power grids, worldwide air travel, and companies that have offices and stores in all larger cities. You can also think of other ideas for networks related to the Internet, such as electronic commerce (networks of buyers and sellers of goods over the Internet) and social networks and related websites, such as Facebook. Hence reliable and efficient systematic methods are an absolute necessity—solutions by trial and error would no longer work, even if “nearly optimal” solutions were acceptable.

We begin with shortest path problems, as they arise, for instance, in designing shortest (or least expensive, or fastest) routes for a traveling salesman, for a cargo ship, etc. Let us first explain what we mean by a path.

In a graph G = (V, E) we can walk from a vertex ν₁ along some edges to some other vertex ν_k. Here we can

1. make no restrictions, or
2. require that each edge of G be traversed at most once, or
3. require that each vertex be visited at most once.

In case (A) we call this a walk. Thus a walk from ν₁ to ν_k is of the form

where some of these edges or vertices may be the same. In case (B), where each edge may occur at most once, we call the walk a trail. Finally, in case (C), where each vertex may occur at most once (and thus each edge automatically occurs at most once), we call the trail a path.

We admit that a walk, trail, or path may end at the vertex it started from, in which case we call it closed; then ν_k = ν₁ in (1).

A closed path is called a cycle. A cycle has at least three edges (because we do not have double edges; see Sec. 23.1). Figure 481 illustrates all these concepts.

Fig. 481. Walk, trail, path, cycle

Shortest Path

To define the concept of a shortest path, we assume that G = (V, E) is a weighted graph, that is, each edge (ν_i, ν_j) in G has a given weight or length l_ij > 0. Then a shortest path ν₁ → ν_k (with fixed ν₁ and ν_k) is a path (1) such that the sum of the lengths of its edges

(l₁₂ = length of (ν₁, ν₂) etc.) is minimum (as small as possible among all paths from ν₁ to ν_k). Similarly, a longest path ν₁ → ν_k is one for which that sum is maximum.

Shortest (and longest) path problems are among the most important optimization problems. Here, “length” l_ij (often also called “cost” or “weight”) can be an actual length measured in miles or travel time or fuel expenses, but it may also be something entirely different.

For instance, the traveling salesman problem requires the determination of a shortest Hamiltonian¹ cycle in a graph, that is, a cycle that contains all the vertices of the graph.

In more detail, the traveling salesman problem in its most basic and intuitive form can be stated as follows. You have a salesman who has to drive by car to his customers. He has to drive to n cities. He can start at any city and after completion of the trip he has to return to that city. Furthermore, he can only visit each city once. All the cities are linked by roads to each other, so any city can be visited from any other city directly, that is, if he wants to go from one city to another city, there is only one direct road connecting those two cities. He has to find the optimal route, that is, the route with the shortest total mileage for the overall trip. This is a classic problem in combinatorial optimization and comes up in many different versions and applications. The maximum number of possible paths to be examined in the process of selecting the optimal path for n cities is (n − 1)!/2, because, after you pick the first city, you have n − 1 choices for the second city, n − 2 choices for the third city, etc. You get a total of (n − 1)! (see Sec. 24.4). However, since the mileage does not depend on the direction of the tour (e.g., for n = 4 (four cities 1, 2, 3, 4), the tour 1–2–3–4–1 has the same mileage as 1–4–3–2–1, etc., so that we counted all the tours twice!), the final answer is (n − 1)!/2. Even for a small number of cities, say n = 15, the maximum number of possible paths is very large. Use your calculator or CAS to see for yourself! This means that this is a very difficult problem for larger n and typical of problems in combinatorial optimization, in that you want a discrete solution but where it might become nearly impossible to explicitly search through all the possibilities and therefore some heuristics (rules of thumbs, shortcuts) might be used, and a less than optimal answer suffices.

A variation of the traveling salesman problem is the following. By choosing the “most profitable” route ν₁ → ν_k, a salesman may want to maximize ∑l_ij, where l_ij is his expected commission minus his travel expenses for going from town i to town j.

In an investment problem, i may be the day an investment is made, j the day it matures, and l_ij the resulting profit, and one gets a graph by considering the various possibilities of investing and reinvesting over a given period of time.

Shortest Path If All Edges Have Length l = 1

Obviously, if all edges have length l, then a shortest path ν₁ → ν_k is one that has the smallest number of edges among all paths ν₁ → ν_k in a given graph G. For this problem we discuss a BFS algorithm. BFS stands for Breadth First Search. This means that in each step the algorithm visits all neighboring (all adjacent) vertices of a vertex reached, as opposed to a DFS algorithm (Depth First Search algorithm), which makes a long trail (as in a maze). This widely used BFS algorithm is shown in Table 23.1.

We want to find a shortest path in G from a vertex s (start) to a vertex t (terminal). To guarantee that there is a path from s to t, we make sure that G does not consist of separate portions. Thus we assume that G is connected, that is, for any two vertices ν and w there is a path ν → w in G. (Recall that a vertex ν is called adjacent to a vertex u if there is an edge (u, ν) in G.)

Table 23.1 Moore's² BFS for Shortest Path (All Lengths One)

Proceedings of the International Symposium for Switching Theory, Part II. pp. 285–292. Cambridge: Harvard University Press, 1959.

Fig. 482. Example 1, given graph and result of labeling

Complexity of an Algorithm

Complexity of Moore's algorithm. To find the vertices to be labeled 1, we have to scan all edges incident with s. Next, when i = 1, we have to scan all edges incident with vertices labeled 1, etc. Hence each edge is scanned twice. These are 2m operations (m = number of edges of G). This is a function c(m). Whether it is 2m or 5m + 3 or 12m is not so essential; it is essential that c(m) is proportional to m (not m², for example); it is of the “order” m. We write for any function am + b simply O(m), for any function am² + bm + d simply O(m²), and so on; here, O suggests order. The underlying idea and practical aspect are as follows.

In judging an algorithm, we are mostly interested in its behavior for very large problems (large m in the present case), since these are going to determine the limits of the applicability of the algorithm. Thus, the essential item is the fastest growing term (am² in am² + bm + d, etc.) since it will overwhelm the others when m is large enough. Also, a constant factor in this term is not very essential; for instance, the difference between two algorithms of orders, say, 5m² and 8m² is generally not very essential and can be made irrelevant by a modest increase in the speed of computers. However, it does make a great practical difference whether an algorithm is of order m or m² or of a still higher power m^p And the biggest difference occurs between these “polynomial orders” and “exponential orders,” such as 2^m.

For instance, on a computer that does 10⁹ operations per second, a problem of size m = 50 will take 0.3 sec with an algorithm that requires m⁵ operations, but 13 days with an algorithm that requires 2^m operations. But this is not our only reason for regarding polynomial orders as good and exponential orders as bad. Another reason is the gain in using a faster computer. For example, let two algorithms be O(m) and 0(m²). Then, since 1000 = 31.6², an increase in speed by a factor 1000 has the effect that per hour we can do problems 1000 and 31.6 times as big, respectively. But since 1000 = 2^9.97, with an algorithm that is O(2^m), all we gain is a relatively modest increase of 10 in problem size because 2^9.97 · 2^m = 2^m+9.97.

The symbol O is quite practical and commonly used whenever the order of growth is essential, but not the specific form of a function. Thus if a function g(m) is of the form

we say that g(m) is of the order h(m) and write

For instance,

We want an algorithm to be “efficient,” that is, “good” with respect to

1. Time (number c(m) of computer operations), or
2. Space (storage needed in the internal memory)

or both. Here c suggests “complexity” of . Two popular choices for c are

(Worst case) c(m) = longest time takes for a problem of size m,

Average case) c(m) = average time takes for a problem of size m.

In problems on graphs, the “size” will often be m (number of edges) or n (number of vertices). For Moore's algorithm, c(m) = 2m in both cases. Hence the complexity of Moore's algorithm is of order O(m).

For a “good” algorithm , we want that c(m) does not grow too fast. Accordingly, we call efficient if c(m) = O(m^k) for some integer k 0; that is, c may contain only powers of m (or functions that grow even more slowly, such as ln m), but no exponential functions. Furthermore, we call polynomially bounded if is efficient when we choose the “worst case” c(m). These conventional concepts have intuitive appeal, as our discussion shows.

Complexity should be investigated for every algorithm, so that one can also compare different algorithms for the same task. This may often exceed the level in this chapter; accordingly, we shall confine ourselves to a few occasional comments in this direction.

23.3 Bellman's Principle. Dijkstra's Algorithm

We continue our discussion of the shortest path problem in a graph G. The last section concerned the special case that all edges had length 1. But in most applications the edges (i, j) will have any lengths l_ij > 0, and we now turn to this general case, which is of greater practical importance. We write l_ij = ∞ for any edge (i, j) that does not exist in G (setting ∞ + a = ∞ for any number a, as usual).

We consider the problem of finding shortest paths from a given vertex, denoted by 1 and called the origin, to all other vertices 2, 3, … n of G. We let L_j denote the length of a shortest path P_j: 1 → j in G.

Fig. 486. Paths P and P_i in Bellman's minimality principle

From Bellman's principle we can derive basic equations as follows. For fixed j we may obtain various paths 1 → j by taking shortest paths P_i for various i for which there is in G an edge (i, j), and add (i, j) to the corresponding P_i. These paths obviously have lengths L_i + l_ij (L_i = length of P_i). We can now take the minimum over i, that is, pick an i for which L_i + l_ij is smallest. By the Bellman principle, this gives a shortest path 1 → j. It has the length

These are the Bellman equations. Since l_ii = 0 by definition, instead of min_i≠j we can simply write min_i. These equations suggest the idea of one of the best-known algorithms for the shortest path problem, as follows.

Dijkstra's Algorithm for Shortest Paths

Dijkstra's⁴algorithm is shown in Table 23.2, where a connected graphG is a graph in which, for any two vertices ν and w in G, there is a path ν → ω. The algorithm is a labeling procedure. At each stage of the computation, each vertex ν gets a label, either

or

We denote by and the sets of vertices with a permanent label and with a temporary label, respectively. The algorithm has an initial step in which vertex 1 gets the permanent label L₁ = 0 and the other vertices get temporary labels, and then the algorithm alternates between Steps 2 and 3. In Step 2 the idea is to pick k “minimally.” In Step 3 the idea is that the upper bounds will in general improve (decrease) and must be updated accordingly. Namely, the new temporary label of vertex j will be the old one if there is no improvement or it will be L_k + l_kj if there is.

Table 23.2 Dijkstra's Algorithm for Shortest Paths

Fig. 487. Example 1

Complexity. Dijkstra's algorithm is O(n²).

23.4 Shortest Spanning Trees: Greedy Algorithm

So far we have discussed shortest path problems. We now turn to a particularly important kind of graph, called a tree, along with related optimization problems that arise quite often in practice.

By definition, a tree T is a graph that is connected and has no cycles. “Connected” was defined in Sec. 23.3; it means that there is a path from any vertex in T to any other vertex in T. A cycle is a path s → t of at least three edges that is closed (t = s); see also Sec. 23.2. Figure 489a shows an example.

A spanning tree T in a given connected graph G = (V, E) is a tree containing all the n vertices of G. See Fig. 489b. Such a tree has n − 1 edges. (Proof?)

A shortest spanning tree T in a connected graph G (whose edges (i, j) have lengths l_ij > 0) is a spanning tree for which ∑l_ij (sum over all edges of T) is minimum compared to ∑l_ij for any other spanning tree in G.

Fig. 489. Example of (a) a cycle, (b) a spanning tree in a graph

Trees are among the most important types of graphs, and they occur in various applications. Familiar examples are family trees and organization charts. Trees can be used to exhibit, organize, or analyze electrical networks, producer–consumer and other business relations, information in database systems, syntactic structure of computer programs, etc. We mention a few specific applications that need no lengthy additional explanations.

The set of shortest paths from vertex 1 to the vertices 2, …, n in the last section forms a spanning tree.

Railway lines connecting a number of cities (the vertices) can be set up in the form of a spanning tree, the “length” of a line (edge) being the construction cost, and one wants to minimize the total construction cost. Similarly for bus lines, where “length” may be the average annual operating cost. Or for steamship lines (freight lines), where “length” may be profit and the goal is the maximization of total profit. Or in a network of telephone lines between some cities, a shortest spanning tree may simply represent a selection of lines that connect all the cities at minimal cost. In addition to these examples we could mention others from distribution networks, and so on.

We shall now discuss a simple algorithm for the problem of finding a shortest spanning tree. This algorithm (Table 23.3) is particularly suitable for sparse graphs (graphs with very few edges; see Sec. 23.1).

Table 23.3 Kruskal's⁵Greedy Algorithm for Shortest Spanning Trees

Proceedings of the American Mathematical Society 7 (1956), 48–50.

The efficiency of Kruskal's method is greatly increased by double labeling of vertices.

Double Labeling of Vertices. Each vertex i carries a double label (r_i, p_i), where

This simplifies rejecting.

Rejecting. If (i, j) is next in the list to be considered, reject (i, j) if r_i = r_j (that is, i and j are in the same subtree, so that they are already joined by edges and (i, j) would thus create a cycle). If r_i ≠ r_j, include (i, j) in T.

If there are several choices for r_i, choose the smallest. If subtrees merge (become a single tree), retain the smallest root as the root of the new subtree.

For Example 1 the double-label list is shown in Table 23.5. In storing it, at each instant one may retain only the latest double label. We show all double labels in order to exhibit the process in all its stages. Labels that remain unchanged are not listed again. Underscored are the two 1’s that are the common root of vertices 2 and 3, the reason for rejecting the edge (2, 3). By reading for each vertex the latest label we can read from this list that 1 is the vertex we have chosen as a root and the tree is as shown in the last part of Fig. 491.

Fig. 491. Choice process in Example 1

Table 23.5 List of Double Labels in Example 1

This is made possible by the predecessor label that each vertex carries. Also, for accepting or rejecting an edge we have to make only one comparison (the roots of the two endpoints of the edge).

Ordering is the more expensive part of the algorithm. It is a standard process in data processing for which various methods have been suggested (see Sorting in Ref. [E25] listed in App. 1). For a complete list of m edges, an algorithm would be O(m log₂ m), but since the n − 1 edges of the tree are most likely to be found earlier, by inspecting the q (< m) topmost edges, for such a list of q edges one would have O(q log₂ m).

23.5 Shortest Spanning Trees:
Prim's Algorithm

Prim's⁶ algorithm, shown in Table 23.6, is another popular algorithm for the shortest spanning tree problem (see Sec. 23.4). This algorithm avoids ordering edges and gives a tree T at each stage, a property that Kruskal's algorithm in the last section did not have (look back at Fig. 491 if you did not notice it).

In Prim's algorithm, starting from any single vertex, which we call 1, we “grow” the tree T by adding edges to it, one at a time, according to some rule (in Table 23.6) until T finally becomes a spanning tree, which is shortest.

We denote by U the set of vertices of the growing tree T and by S the set of its edges. Thus, initially U = { 1 } and S = Ø; at the end U = V, the vertex set of the given graph G = (V, E), whose edges (i, j) have length l_ij > 0, as before.

Thus at the beginning (Step 1) the labels

are the lengths of the edges connecting them to vertex 1 (or ∞ if there is no such edge in G). And we pick (Step 2) the shortest of these as the first edge of the growing tree T and include its other end j in U (choosing the smallest j if there are several, to make the process unique). Updating labels in Step 3 (at this stage and at any later stage) concerns each vertex k not yet in U. Vertex k has label λ_k = l_i(k),k from before. If l_jk < λ_k, this means that k is closer to the new member j just included in U than k is to its old “closest neighbor” i(k) in U. Then we update the label of k, replacing λ_k = l_i(k),k by λ_k = l_jk and setting i(k) = j. If, however, l_jk λ_k (the old label of k), we don't touch the old label. Thus the label λ_k always identifies the closest neighbor of k in U, and this is updated in Step 3 as U and the tree T grow. From the final labels we can backtrack the final tree, and from their numeric values we compute the total length (sum of the lengths of the edges) of this tree.

Prim's algorithm is useful for computer network design, cable, distribution networks, and transportation networks.

Table 23.6 Prim's Algorithm for Shortest Spanning Trees

Bell System Technical Journal 36 (1957), 1389–1401.

For an improved version of the algorithm, see Cheriton and Tarjan, SIAM Journal on Computation 5 (1976), 724–742.

Table 23.7 Labeling of Vertices in Example 1

23.6 Flows in Networks

After shortest path problems and problems for trees, as a third large area in combinatorial optimization we discuss flow problems in networks (electrical, water, communication, traffic, business connections, etc.), turning from graphs to digraphs (directed graphs; see Sec. 23.1).

By definition, a network is a digraph G = (V, E) in which each edge (i, j) has assigned to it a capacity c_ij > 0 [= maximum possible flow along (i, j)], and at one vertex, s, called the source, a flow is produced that flows along the edges of the digraph G to another vertex, t, called the target or sink, where the flow disappears.

In applications, this may be the flow of electricity in wires, of water in pipes, of cars on roads, of people in a public transportation system, of goods from a producer to consumers, of e-mail from senders to recipients over the Internet, and so on.

We denote the flow along a (directed!) edge (i, j) by f_ij and impose two conditions:

1. For each edge (i, j) in G the flow does not exceed the capacity c_ij,

2. For each vertex i, not s or t,

in a formula,

where f is the total flow (and at s the inflow is zero, whereas at t the outflow is zero). Figure 493 illustrates the notation (for some hypothetical figures).

Fig. 493. Notation in (2): inflow and outflow for a vertex i (not s or t)

Paths

By a path ν₁ → ν_k from a vertex ν₁ to a vertex ν_k in a digraph G we mean a sequence of edges

regardless of their directions in G, that forms a path as in a graph (see Sec. 23.2). Hence when we travel along this path from ν₁ to ν_k we may traverse some edge in its given direction—then we call it a forward edge of our path—or opposite to its given direction—then we call it a backward edge of our path. In other words, our path consists of one-way streets, and forward edges (backward edges) are those that we travel in the right direction (in the wrong direction). Figure 494 shows a forward edge (u, v) and a backward edge (w, v) of a path ν₁ → ν_k.

Fig. 494. Forward edge (u, v) and backward edge (w, v) of a path v₁ → v_k

Fig. 495. Edge (u, v) as forward edge in the path v₁ → v_k and as backward edge in the path x₁ → x_j

Flow Augmenting Paths

Our goal will be to maximize the flow from the source s to the target t of a given network. We shall do this by developing methods for increasing an existing flow (including the special case in which the latter is zero). The idea then is to find a path P: s → t all of whose edges are not fully used, so that we can push additional flow through P. This suggests the following concept.

Fig. 497. Flow augmenting paths in Example 1

Cut Sets

A cut set is a set of edges in a network. The underlying idea is simple and natural. If we want to find out what is flowing from s to t in a network, we may cut the network somewhere between s and t (Fig. 498 shows an example) and see what is flowing in the edges hit by the cut, because any flow from s to t must sometimes pass through some of these edges. These form what is called a cut set. [In Fig. 498, the cut set consists of the edges (2, 3), (5, 2), (4, 5).] We denote this cut set by (S, T). Here S is the set of vertices on that side of the cut on which s lies (S = {s, 2, 4} for the cut in Fig. 498) and T is the set of the other vertices (T = {3, 5, t} in Fig. 498). We say that a cut partitions the vertex set V into two parts S and T. Obviously, the corresponding cut set (S, T) consists of all the edges in the network with one end in S and the other end in T.

Fig. 498. Maximum flow in Example 1

By definition, the capacity cap (S, T) of a cut set (S, T) is the sum of the capacities of all forward edges in (S, T) (forward edges only!), that is, the edges that are directed from S to T,

Thus, cap (S, T) = 11 + 7 = 18 in Fig. 498.

Explanation. This can be seen as follows. Look at Fig. 498. Recall that for each edge in that figure, the first number denotes capacity and the second number flow. Intuitively, you can think of the edges as roads, where the capacity of the road is how many cars can actually be on the road, and the flow denotes how many cars actually are on the road. To compute capacity cap (S, T) we are only looking at the first number on the edges. Take a look and see that the cut physically cuts three edges, that is, (2, 3), (4, 5), and (5, 2). The cut concerns only forward edges that are being cut, so it concerns edges (2, 3) and (4, 5) (and does not include edge (5, 2) which is also being cut, but since it goes backwards, it does not count). Hence (2, 3) contributes 11 and (4, 5) contributes 7 to the capacity cap (S, T), for a total of 18 in Fig. 498. Hence (S, T) = 18.

The other edges (directed from T to S) are called backward edges of the cut set (S, T), and by the net flow through a cut set we mean the sum of the flows in the forward edges minus the sum of the flows in the backward edges of the cut set.

For the cut in Fig. 498 the net flow is 11 + 6 − 3 = 14. For the same cut in Fig. 496 (not indicated there), the net flow is 8 + 4 − 3 = 9. In both cases it equals the flow f. We claim that this is not just by chance, but cuts do serve the purpose for which we have introduced them:

This theorem has the following consequence, which we shall also need later in this section.

Cut sets will now bring out the full importance of augmenting paths:

The end of this proof yields another basic result (by Ford and Fulkerson, Canadian Journal of Mathematics 8 (1956), 399–404), namely, the so-called

The two basic tools in connection with networks are flow augmenting paths and cut sets. In the next section we show how flow augmenting paths can be used in an algorithm for maximum flows.

23.7 Maximum Flow: Ford–Fulkerson Algorithm

Flow augmenting paths, as discussed in the last section, are used as the basic tool in the Ford–Fulkerson⁷ algorithm in Table 23.8 in which a given flow (for instance, zero flow in all edges) is increased until it is maximum. The algorithm accomplishes the increase by a stepwise construction of flow augmenting paths, one at a time, until no further such paths can be constructed, which happens precisely when the flow is maximum.

In Step 1, an initial flow may be given. In Step 3, a vertex j can be labeled if there is an edge (i, j) with i labeled and

or if there is an edge (j, i) with i labeled and

To scan a labeled vertex i means to label every unlabeled vertex j adjacent to i that can be labeled. Before scanning a labeled vertex i, scan all the vertices that got labeled before i. This BFS (Breadth First Search) strategy was suggested by Edmonds and Karp in 1972 (Journal of the Association for Computing Machinery 19, 248–64). It has the effect that one gets shortest possible augmenting paths.

Table 23.8 Ford–Fulkerson Algorithm for Maximum Flow

Canadian Journal of Mathematics 9 (1957), 210–218

Fig. 501. Maximum flow in Example 1

23.8 Bipartite Graphs. Assignment Problems

From digraphs we return to graphs and discuss another important class of combinatorial optimization problems that arises in assignment problems of workers to jobs, jobs to machines, goods to storage, ships to piers, classes to classrooms, exams to time periods, and so on. To explain the problem, we need the following concepts.

A bipartite graph G = (V, E) is a graph in which the vertex set V is partitioned into two sets S and T (without common elements, by the definition of a partition) such that every edge of G has one end in S and the other in T. Hence there are no edges in G that have both ends in S or both ends in T. Such a graph G = (V, E) is also written G = (S, T; E).

Figure 503 shows an illustration. V consists of seven elements, three workers a, b, c, making up the set S, and four jobs 1, 2, 3, 4, making up the set T. The edges indicate that worker a can do the jobs 1 and 2, worker b the jobs 1, 2, 3, and worker c the job 4. The problem is to assign one job to each worker so that every worker gets one job to do. This suggests the next concept, as follows.

For instance, a matching in Fig. 503 is M₁ = {(a, 2), (b, 1)}. Another is M₂ = {(a, 1), (b, 3), (c, 4)}; obviously, this is of maximum cardinality.

Fig. 503. Bipartite graph in the assignment of a set S = {a, b, c} of workers to a set T = {1, 2, 3, 4} of jobs

A vertex ν is exposed (or not covered) by a matching M if ν is not an endpoint of an edge of M. This concept, which always refers to some matching, will be of interest when we begin to augment given matchings (below). If a matching leaves no vertex exposed, we call it a complete matching. Obviously, a complete matching can exist only if S and T consist of the same number of vertices.

We now want to show how one can stepwise increase the cardinality of a matching M until it becomes maximum. Central in this task is the concept of an augmenting path.

An alternating path is a path that consists alternately of edges in M and not in M (Fig. 504A). An augmenting path is an alternating path both of whose endpoints (a and b in Fig. 504B) are exposed. By dropping from the matching M the edges that are on an augmenting path P (two edges in Fig. 504B) and adding to M the other edges of P (three in the figure), we get a new matching, with one more edge than M. This is how we use an augmenting path in augmenting a given matching by one edge. We assert that this will always lead, after a number of steps, to a maximum cardinality matching. Indeed, the basic role of augmenting paths is expressed in the following theorem.

Fig. 504. Alternating and augmenting paths. Heavy edges are those belonging to a matching M

Fig. 505. Proof of the augmenting path theorem for bipartite matching

This theorem suggests the algorithm in Table 23.9 for obtaining augmenting paths, in which vertices are labeled for the purpose of backtracking paths. Such a label is in addition to the number of the vertex, which is also retained. Clearly, to get an augmenting path, one must start from an exposed vertex, and then trace an alternating path until one arrives at another exposed vertex. After Step 3 all vertices in S are labeled. In Step 4, the set T contains at least one exposed vertex, since otherwise we would have stopped at Step 1.

Table 23.9 Bipartite Maximum Cardinality Matching

CHAPTER 23 REVIEW QUESTIONS AND PROBLEMS

1. What is a graph, a digraph, a cycle, a tree?
2. State some typical problems that can be modeled and solved by graphs or digraphs.
3. State from memory how graphs can be handled on computers.
4. What is a shortest path problem? Give applications.
5. What situations can be handled in terms of the traveling salesman problem?
6. Give typical applications involving spanning trees.
7. What are the basic ideas and concepts in handling flows?
8. What is combinatorial optimization? Which sections of this chapter involved it? Explain details.
9. Define bipartite graphs and describe some typical applications of them.
10. What is BFS? DFS? In what connection did these concepts occur?

11–16 MATRICES FOR GRAPHS AND DIGRAPHS

Find the adjacency matrix of:

• 11.
• 12.
• 13.

14–16 Sketch the graph whose adjacency matrix is:

• 14.
• 15.
• 16.
• 17. Vertex incidence list. Make it for the graph in Prob. 15.
• 18. Find a shortest path and its length by Moore's BFS algorithm, assuming that all the edges have length 1.

  

• 19. Find shortest paths by Dijkstra's algorithm.

  

• 20. Find a shortest spanning tree.

  

• 21. Company A has offices in Chicago, Los Angeles, and New York; Company B in Boston and New York; Company C in Chicago, Dallas, and Los Angeles. Represent this by a bipartite graph.
• 22. Find flow augmenting paths and the maximum flow.

  

• 23. Using augmenting paths, find a maximum cardinality matching.

  

• 24. Find an augmenting path,

  

SUMMARY OF CHAPTER 23

Graphs. Combinatorial Optimization

Combinatorial optimization concerns optimization problems of a discrete or combinatorial structure. It uses graphs and digraphs (Sec. 23.1) as basic tools.

A graph G = (V, E) consists of a set V of vertices ν₁, ν₂, …, ν_n (often simply denoted by 1, 2, …, n) and a set E of edges e₁, e₂, …, e_m, each of which connects two vertices. We also write (i, j) for an edge with vertices i and j as endpoints. A digraph (= directed graph) is a graph in which each edge has a direction (indicated by an arrow). For handling graphs and digraphs in computers, one can use matrices or lists (Sec. 23.1).

This chapter is devoted to important classes of optimization problems for graphs and digraphs that all arise from practical applications, and corresponding algorithms, as follows.

In a shortest path problem (Sec. 23.2) we determine a path of minimum length (consisting of edges) from a vertex s to a vertex t in a graph whose edges (i, j) have a “length” l_ij > 0, which may be an actual length or a travel time or cost or an electrical resistance [if (i, j) is a wire in a net], and so on. Dijkstra's algorithm (Sec. 23.3) or, when all l_ij = 1, Moore's algorithm (Sec. 23.2) are suitable for these problems.

A tree is a graph that is connected and has no cycles (no closed paths). Trees are very important in practice. A spanning tree in a graph G is a tree containing all the vertices of G. If the edges of G have lengths, we can determine a shortest spanning tree, for which the sum of the lengths of all its edges is minimum, by Kruskal's algorithm or Prim's algorithm (Secs. 23.4, 23.5).

A network (Sec. 23.6) is a digraph in which each edge (i, j) has a capacity c_ij > 0 [= maximum possible flow along (i, j)] and at one vertex, the source s, a flow is produced that flows along the edges to a vertex t, the sink or target, where the flow disappears. The problem is to maximize the flow, for instance, by applying the Ford–Fulkerson algorithm (Sec. 23.7), which uses flow augmenting paths (Sec. 23.6). Another related concept is that of a cut set, as defined in Sec. 23.6.

A bipartite graph G = (V, E) (Sec. 23.8) is a graph whose vertex set V consists of two parts S and T such that every edge of G has one end in S and the other in T, so that there are no edges connecting vertices in S or vertices in T. A matching in G is a set of edges, no two of which have an endpoint in common. The problem then is to find a maximum cardinality matching in G, that is, a matching M that has a maximum number of edges. For an algorithm, see Sec. 23.8.