===== Chapter 7: Network Flow ===== ==== 7.1 - The Maximum-Flow Problem and the Ford-Fulkerson Algorithm ==== Network models have capacities along edges (how much they can carry), source nodes (sending traffic), and sink nodes (receiving traffic). Given a flow network, find a flow of maximum possible value. We can push forward on edges with leftover capacity, and we can push backwards on edges that are already carrying slow. augment(f, P) Let b=bottleneck(P, f) For each edge (u,v) in P If e=(u,v) is a forwad edge then increase f(e) in G by b Else ((u,v) is a backward edge, and let e=(u,v)) decrease f(e) in G by b Endif Endfor Return(f) The Ford-Fulkerson Algorithm: Max-Flow Initially f(e)=0 for all e in G While there is an s-t path in the residual graph G(f) Let P be a simple s-t path in G(f) f’=augment(f,P) Update f to be f’ Update the residual graph G(f) to be G(f’) Endwhile Return f At every intermediate stage of the F-F Algorithm, the flow values {f(e)} and the residual capacities in G(f) are integers. Then the it terminates in at most C iterations of the While loop. run time: O(mC) time ==== 7.2 - Maximum Flows and Minimum Cuts in a Network ==== Divide the nodes of the graph into two sets: A (s in A) and B (t in B). Let f be any s-t flow, and (A,B) any s-t cut. Then v(f) = f(A out) - f(A in). Also, v(f) = f(B in) - f(B out). By watching the amount of flow f sends across a cut, we can exactly measure the flow value: the total amount that leaves A minus the amount that ‘swirls back’ into A. v(f) <= c(A,B) The value of every flow is upper-bounded by the capacity of every cut. If f is an s-t flow such that there is no s-t path in the residual graph G(f), then there is an s-t cut (A*,B*) in G for which v(f) = c(A*,B*). Consequently, f has the max value of any flow in G, and (A*,B*) has the min capacity of any s-t cut in G. Given a flow f of max value, we can compute an s-t cut of minimum capacity in O(m) time. The max value of an s-t flow is equal to the min capacity of an s-t cut. ==== 7.5 - A First Application: The Bipartite Matching Problem ==== Bipartite graph G = (V,E) is an undirected graph whose node set can be partitioned as V = X U Y, with the property that every edge e in E has one end in X and the other end in Y. The Bipartite Matching Problem finds a matching G of the largest size. First we direct all edges in G from X to Y. Then add node s, and an adge (s,x) from s to each node in X. Add a node t, and an edge (y,t) from each node in Y to t. Each edge has a capacity of 1. The computed max flow in this network is equal to the size of the maximum matching in G’. The size of the max matching in G is equal to the value of the max flow in G’; and the edges are that which carry flow from X to Y in G’. The F-F Algorithm can be used to find an optimal solution in O(mn) time. ==== 7.7 - Extensions to the Maximum-Flow Problem ==== Circulations with Demands: Suppose there can be multiple source and sink nodes. Assuming fixed supply and sink values, we incorporate a demand value with each node, negative if it sends flow and positive if it receives flow. If there is a feasible circulation with demands d(v), then all for all cuts (A,B) SUM(d(v)) <= c(A,B).