416 Applications of Discrete Mathematics

graph shown in Figure 8(a). There (ignoring signs) the first label on t is a, so the augmenting chain vertex sequence ends with a, t. The first label on a is b, so the augmenting chain vertex sequence ends with b, a, t. Finally, the first label on b is s, so the augmenting chain vertex sequence is s, b, a, t.

Figure 8. Showing an augmenting chain being found using labels and being used to increase flow.

When a vertex n is labeled from vertex m, the second label is always the minimum of the second label on m and the amount c(m, n)−f(m, n) or f(n, m) which can be gotten to n from m through the edge. Since the second label on s is ∞, the result is that the second label always gives the largest amount that can get to the vertex labeled. Thus when t is labeled, the second label of t states the increase of flow given by the augmenting chain specified by the labels. For example, in Figure 8(a) the augmenting chain has vertex sequence s, b, a, t, and the amounts of flow that can be forced through the edges of the chain are 4, 3, and 2, successively, with a minimum of 2. Because of the way second labels are chosen, the second label on t is this amount 2.

Example 7 Find an augmenting chain in the graph shown in Figure 8(a), in which there is a preexisting flow of 3 units.

Solution: We label s with (−,∞), and from there we label b with (+s, 4). From b we can label a by canceling flow in (a, b), so a receives the label (−b, 3). From a we can label t with label (+a, 2). These labels are shown in Figure 8(a). Reading first labels backwards, we find the augmenting chain is s, b, a, t as discussed before, and the chain will increase the flow by 2 as the second label on t shows. The resulting flow is shown in Figure 8(b), where 3 units of flow go out of s to a and split there into 2 units that flow directly to t and one that goes to t through b. In addition, 2 units of flow go from s through b to t, making a total of 5 units of flow shown in Figure 8(b).

While we are labeling we can keep track of what is possible, without con- cerning ourselves whether there is actually a chain available from s to t along

Chapter 23 Network Flows 417

which new flow can go. If we can label t, then the flow can be increased; we will show that if we cannot label t, then the flow cannot be increased.

We are also under no obligation to watch for a chain of labels. Since we always label an unlabeled vertex from a labeled vertex, s being always labeled with (−,∞), we automatically form a tree (disregarding the directions of edges). Thus for each labeled vertex x, our labels describe a unique chain from s to x. An example of such a tree is shown by boldface edges in Figure 8(a). As shown in that figure, if we mark on the graph the edges used in labeling vertices, we find the augmenting chain with vertices s, b, a, t shown in bold lines in Figure 8(a).

Example 8 Find a flow in the graph of Figure 1.

Figure 9. (a) Figure 1 converted to a directed capacitated s,t-graph. (b) The first labeling and the associated tree for Example 1.

418 Applications of Discrete Mathematics

Solution: In Figure 9(a), the graph of Figure 1 is reproduced, except that each undirected edge has been replaced by two directed edges, one in each direction, each with the same capacity as the undirected edge. Also, the ca- pacities have been written as the first entries of number pairs, with 0 for flow as the second number.* Starting with the label (−,∞) at s, we label across edges as described above. First a is labeled with (+s, 4), and working from a we label b with (+a, min(4, 3)) = (+a, 3) and d with (+a, min(4, 2)) = (+a, 2), but we do not label s from a because s already has a label. Labeling from b, we do not need to label a, but we label c with (+b, min(3, 2)) = (+b, 2) and g with (+b, min(3, 1)) = (+b, 1). Then we label from c, placing (+c, min(2, 2)) = (+c, 2) on vertex e, but we place no label on d from c, since d already has a label. Next we label from d, placing label (+d, min(2, 1)) = (+d, 1) on ver- tex f . As before, we do not label a from d. Going on to vertex e, we label nothing from there, since all of its neighbors are already labeled. Next we label from f , placing label (+f, min(1, 2)) = (+f, 1) on vertex h. Since all neighbors of g are already labeled, we go on to h, from which we label t with (+h, min(1, 3)) = (+h, 1). Since t is labeled, we are done.

We use the labels to determine the chain from s to t that was found, along which a single unit of flow can flow (because the second label on t is 1). The first label on t is +h, showing that edge (h, t) is the last edge of the chain from s to t. The first label on h is +f , showing the next-to-the-last edge of the chain is (f, h). We continue reading backwards, using the first labels, obtaining the sequence “t, h, f, d, a, s” which reverses to give the chain s, a, d, f, h, t from s to t along which one unit of flow is added. The tree of edges used in our labeling is shown by bold lines in Figure 9(b), and Figure 10(a) shows the network with the flow we found.

To describe a procedure that can be programmed, we need a rule for de- ciding which edge to label across next. Many such rules are possible; the one we have adopted here and used in Example 8 is straightforward: Label from the alphabetically earliest vertex x which has a label and which meets an edge that has not yet been considered from vertex x, and label all possible vertices from x before going on to the next vertex. This rule is called the lexicographic ordering rule.

Once we have increased the flow, the labels we placed on the vertices other than s are wrong for the new combination of graph and flow, so we erase the vertex labels and start again from s. Again we explore the graph, searching for a chain from s to t along which we can increase the flow.

* In Figures 9(b) through 12, to simplify the figures we have shown only the di- rected edges that contain flow when flow is present and the undirected edges when it

is not.

Chapter 23 Network Flows 419

Figure 10. (a) Second labeling, associated tree, and first flow for Example 1. (b) Third labeling, associated tree, and second flow for Example 1.

Example 9 Increase the flow found in Example 8 as much as possible.

Solution: Labeling as before in the graph of Figure 10(a), we obtain the vertex labels shown in that figure. (Again the associated spanning tree is shown with bold lines.) Notice there that vertex f could not be labeled from d because c(d, f) − f(d, f) = 1 − 1 = 0. Hence f was labeled from e.

This time the augmenting chain is s, a, b, c, e, f, h, t, with one more unit of flow available. The resulting flow is shown in Figure 10(b). Again the labels are erased and new ones found. This time, since both c(d, f)− f(d, f) = 0 and c(e, f)− f(e, f) = 1− 1 = 0, f has no label when labeling from e is completed. Hence we do not try then to label from f , but rather label from g. Later f

420 Applications of Discrete Mathematics

does receive a label; indeed, its label shows that flow should be canceled to reach f . In a more complex graph, it would then be reasonable to label from f . In this graph, however, we reach t without using f again. The tree of edges used is shown in Figure 10(b) with bold edges, and the augmenting chain is s, a, b, g, h, t.

The resulting flow is shown in Figure 11. We label again, as shown in Figure 11, and we obtain the tree of edges used, again shown there. However, the tree does not contain t, so we have not found an augmenting chain. Does this mean there is no augmenting chain?

Figure 11. Fourth labeling, associated tree, and a minimum cut.

For the answer to that question, we must bring up machinery appropriate to Example 2.

Definition 3 Given a directed graph G with capacities on the edges, and given a nonempty subset A of its vertices such that V (G)−A is also nonempty, the set of all edges of G directed from vertices in A toward vertices in V (G)−A is called the cut (A, V (G)−A). The capacity c(A, V (G)−A) of this cut is the sum of the capacities of the edges in it. If s ∈ A and t ∈ V (G) − A, then we call the cut an s, t-cut.

Our objective in Example 2 is to find a cut (A, V (G) − A) such that c(A, V (G) − A) is minimum. In Theorem 3, we begin to tie the maximum flow and the minimum cut together, and in Theorem 4 we will complete the connection.

Chapter 23 Network Flows 421

Example 10 Discuss the cuts in the graph of Figure 11.

Solution: In Figure 11, the set of vertices in the tree is A = {s, a, b, c, d, e, g}. The set of edges directed from A to V (G)−A = {f, h, t} is the cut {(d, f), (e, f), (g, h)}. Notice that on each of these edges the flow equals the capacity and that on the return edges (f, d), (f, e), (h, g) in (V (G) − A, A) the flow is zero. The capacity of the cut is c(d, f)+ c(e, f)+ c(g, h) = 1 + 1 + 1 = 3. Notice also that this cut is an s, t-cut, and that the capacity of the cut is exactly the same as the total flow F (A) = F ({s}) = 3.

Theorem 3 The maximum flow from vertex s to vertex t �= s in a directed graph G with capacities on its edges is less than or equal to the capacity of any cut (A, V (G) − A) having s ∈ A and t �∈ A. Proof: Consider any s, t-cut (A, V (G)−A) of graph G. Since any units of flow from s to t must pass through an edge of this cut, it follows immediately that F ({s}) ≤ c(A, V (G) − A).

In Example 10, several facts are evident. First, since s has a label and t does not, any flow from s to t must pass through one or another of the three edges in the cut (A, V (G)−A). Second, since the return edges in (V (G)−A, A) are empty, any flow passing through the three edges directed away from A must continue on toward t. Third, with the edges directed away from A full and the edge directed toward A empty, there is no conceivable way that the flow we have found could be increased. In other words, we have found a maximum flow in this graph from s to t, and its amount is equal to the sum of the capacities of the edges in this cut separating s from t.

Returning to the graph shown in Figure 6(c), we see another example of this situation. Vertex s is labeled (−,∞) as usual. Since f(s, a) = c(s, a) and f(s, b) = c(s, b), the tree of labeled vertices includes only vertex s, so F ({s}) = c({s}, {a, b, t}) = 5.

Notice that there are no edges directed toward {s}, and both of the edges directed out of {s} in Figure 6(c) are full. Thus, it is clear that the flow to vertex t cannot be increased from its value of 5 units shown in Figure 6(c), and the maximum flow is equal to the sum of the capacities of the edges in the set {(s, a), (s, b)}. (We will generalize these observations in Theorem 4, following Algorithm 1.)

The observations made in considering Examples 9 and 10 motivate Algo- rithm 1.

422 Applications of Discrete Mathematics

ALGORITHM 1 Max-flow min-cut algorithm.

procedure Max-flow min-cut(G := directed graph with source s, sink t, and capacities on all edges)

label s with (−,∞) stop := 0 while stop = 0 begin

while t has no label begin

m := labeled vertex not previously examined, chosen by using an ordering rule

x := the second label on m e := edge incident with m and not previously examined

while at m if e = (m, n) and if n is not labeled and if c(e)−f(e) > 0

then label n with (+m, y) where y = min(c(e)−f(e), x) if e = (n, m) and if n is not labeled and if f(e) > 0 then

label n with (−m, y′) where y′ = min(f(e), x) if no such vertex m and edge e exist then stop := 1

end {vertex t has been labeled} if stop = 0 then p := x0, x1, . . . , xn, an augmenting chain

with s = x0 and xn = t {p is found using the labels as described in the text} if stop = 0 then v := the value of the second label on t i := 0 while i < n and stop = 0 begin

if the first label on xi+1 is +xi then replace the second label r on edge (xi, xi+1) with r + v

if the first label on xi+1 is −xi then replace the second label r′ on edge (xi+1, xi) with r′ − v

{r′ ≥ v by the use of minimum as we progress toward t} i := i + 1

end erase all vertex labels except the one on s

end {No more labeling is possible. By Theorem 4, the cut from the set of labeled vertices to the set of unlabeled vertices is a minimum cut and the flow F ({s}) is a maximum flow.}

Chapter 23 Network Flows 423

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