7.1 The maximum-flow problem and the Ford-Fulkerson algorithm
We can use graphs to represent transportation networks, which have edges that carry traffic and nodes that act as “switches” passing the traffic. All the edges have capacities for how much traffic they can carry, source nodes that generate the traffic and sing nodes that absorb traffic when it arrives. The traffic is called flow in these graphs that starts from the source nodes, travels across the edges to be absorbed by the sink nodes. We can think of it as a directed graph with three features: 1.) Associated with each edge e is a capacity, which is a nonnegative number that we denote ce 2.) There is a single source node s ∈ V 3.) There is a single sink node t ∈ V. All the nodes between s and t are internal nodes. For our purposes, there are three assumptions regarding flow networks: 1.) No edge enters source s and no edge leaves sink t, 2.) there is at least one edge incident to each node, 3.) all capacities are integers. Regarding the way the network carries traffic, we say that an s-t flow is a function f that maps each edge e to a nonnegative real number. A flow f has two properties: 1.) (Capacity conditions) For each e in E, we have 0 ⇐ f(e) ⇐ ce, 2.) (Conservation conditions) For each node v other than s and t we have the same flow value flowing into node v and leaving node v. The flow on an edge cannot exceed the capacity of an edge. The source has no entering edges, but can have flow going out or generate flow. The sink has flow coming in to it but no edges leaving it. The value of a flow is defined by the amount of flow generated at the source.
In the Maximum-Flow problem, our goal is, given a flow network, to fin a flow of maximum possible value. The maximum flow value equals the minimum capacity of any such division or the minimum cut (see p. 340-1 for algorithm and figure 7.3). The algorithm used involves a forward-backward operation in which we push forward on the edges with leftover capacity and push backward on edges that are already carrying flow to divert it in another direction and use this to find the residual graph. The residual graph Gf of G has three properties: 1.) The node set of Gf is the same as that of G, 2.) For each edge e = (u, v) of G on which f(e) < ce there are ce – f(e) “leftover” units of capacity on which we could try pushing flow forward. So we include the edge e = (u, v) in Gf with a capacity of ce – f(e). We will call edges included this way forward edges, 3.) For each edge e = (u,v) of G on which f(e) > 0, there are f(e) units of flow that we can “undo” if we want to, by pushing flow backward. So we include the edge e’ = (v, u) in Gf, with a capacity of f(e). e’ is just the reverse of e, and all edges included this way are backward edges.
Algorithm on p. 342-3 shows how to augment paths of a graph to return a new flow f’ in G, obtained by increasing and decreasing flow values on edges of P. Together with the ma-flow algorithm on p. 344 we have the Fod-Fulkerson algorithm, which runs in O(mC) time if all capacities are integers.
7.2 Maximum flows and minimum cuts in a network
We want to be able to show that the flow returned by Ford-Fulkerson has the maximum possible value of any flow in G. We can divide the nodes in to set A and set B, which s includes A and t includes B. This division places an upper bound on the maximum possible flow value, since all the flow must cross from A to B somewhere. We can use cuts as upper bounds on the values of flows and say that f is any s-t flow and (A, B) is any s-t cut, so that v(f) = fout(A) – fin(A). This means that by watching any flow across a cur we can measure the flow value, which is equal to the total amount that leaves A, minus the amount that swirls back into A (proof p. 347).
The Ford-Fulkerson algorithm terminates when the flow f has no s-t path in the residual graph Gf, which proves its maximality. If f is an s-t flow such that there is no s-t path in the residual graph Gf, then there is an s-t cut (A*, B*) in G for which v(f) – c(A*, B*). Consequently, f has the maximum value of any flow in G, and (A*, B*) has the minimum capacity of any s-t cut in G. (Proofs pages 348-350).
7.5 A First Application: The bipartite matching problem
A bipartite graph G = (V, E) is an undirected graph whose nodes can be partitioned into X and Y so every edge has one end in X and the other in Y. We find the maximum flow on a bipartite graph by first starting with graph G and constructing a flow network G’ (see Figure 7.9 on p. 368). We direct all edges in G from X to Y, then add a node s and edge (s,x) to each node in x. We then add a node t and an edge (y, t) from each node in Y to t and give each edge in G’ a capacity of 1. We can then compute a maximum s-t flow in G’.
We can check for perfect matchings in bipartite graphs by checking to see if the maximum for in G’ has value at least n. There will be an s-t cut of capacity less than n if the maximum flow value in G’ has value less than n. If a bipartite graphs has a perfect matching, then each node A has to be matched to a different node in Γ(A), so Γ(A) has to be at least as large as A.
7.7 Extensions to the maximum-flow problem
This section looks at a maximum-flow problem involved a set of S sources generating flow and a set T of sinks absorbing flow. All the edges have capacities and each node has a demand. If the demand of a node is greater than 0, that is the demand for that flow from that node. If the demand is less than 0, that node has a negative supply and wants to send out more flow than it receives. We want to figure out if there exists a circulation that meets both the capacity and demand conditions (p.380). A feasible circulation exists if the total supply equals the total demand.
I give this chapter an 8 in terms of readability. This reading took me a long time just because I had to really think about some of the expressions and explanations, so conceptually this chapter was kind of tough for me but the visuals kind of helped as well as the slides from class.
