冬令营专题讲座网络流

1、2022/8/91Flow NetworksA flow network is a digraph G = (V, E) such that each edge has a capacity c(u, v) 0. Those edges not in E have capacity 0. We also have two distinguished vertices: a source s and a sink t. We assume each vertex is on some path from s to t. This implies that the graph is connect

2、ed: |E| |V| - 1.A flow in G is a real-valued function that satisfies the properties: Capacity constraint: Skew symmetry: Flow conservation:f(u, v) - with no restriction on sign - is called the flow from vertex u to vertex v.2022/8/92Flow NetworksThe value of the flow is defined as:Maximum flow probl

3、em: given a flow network G with source s and sink t, find a flow of maximum value.Observations: a) skew symmetry implies that the flow conservation property can be restated asThe total flow into a vertex is 0.b) The total positive flows entering and leaving a vertex are defined as:c) Total net flow:

4、 tot. pos. leaving - tot. pos. entering.2022/8/93Flow NetworksExample:2022/8/94Flow NetworksA maximum flow problem may have several sources and sinks. We can reduce the problem to one with a single source and a single sink by adding a supersource and a supersink, with edges connecting them to the so

5、urces and sinks respectively and with infinite capacity along these edges.The next slide gives an example.2022/8/95Flow Networks2022/8/96Flow NetworksSome notation. We extend the definition of the flow function to sets of vertices:Using this notational convention, the flow conservation constraint ca

6、n be written as:We will also “confuse” single set members and singleton sets, whenever the context allows an unambiguous interpretation: V - s means V - s.2022/8/97Flow NetworksLemma 26.1. Let G = (V, E) be a flow network, let f be a flow in G. Then Proof. Ex. 26.1-4. An easy exercise in manipulatio

7、n.Ex.: 2022/8/98Flow NetworksThe Ford-Fulkerson method. This is a “framework” into which one can implement more than one algorithm. We will see that later - in the meantime we introduce terms: residual networks, augmenting paths, cuts, which will be defined shortly.The idea is to start with a flow f

8、unction f(u, v) = 0 on all pairs of vertices of G. We extend it iteratively by finding, at each iteration, an “augmenting path” (paths from s to t) over which the flow (and thus f) can be increased. When no augmenting paths can be found, we are done. More formally:2022/8/99Flow NetworksResidual Netw

9、orks. Let G = (V, E) be a flow network with source s, sink t and capacity c. Let f be a flow in G; let u and v be vertices in V. The residual capacity of (u, v) is given by cf(u, v) = c(u, v) - f(u, v). It is the amount of additional flow that can be pushed from u to v before exceeding the capacity

10、c(u, v).The residual network of G induced by f is Gf(V, Ef), where Thus each residual edge - edge of the residual network - can admit a positive flow. The edges in Ef are either edges in E or their reversals (next slide).2022/8/910Flow NetworksClaim: an edge (u, v) can appear in a residual network o

11、nly if at least one of (u, v) and (v, u) appears in the original network. In particular, |Ef | 2 |E|.Pf. of claim: if f(u, v) 0, and If f(u, v) 0 for an edge , then f(v, u) 0 If neither (u, v) nor (v, u) appears in the original network, then c(u, v) = c(v, u) = f(u, v) = f(v, u) = 0, and this implie

12、s that cf(u, v) = cf(v, u) = 0.Note: the residual network Gf is itself a flow network with capacity function cf.2022/8/911Flow Networks2022/8/912Flow NetworksLemma 26.2. Let G = (E, V) be a flow network with source s, sink t, capacity c and a flow f. Let Gf be the residual network of G induced by f,

13、 let f be a flow in Gf. Then the flow sum f + f defined by (f + f)(u, v) = f(u, v) + f(u, v),is a flow in G with value |f + f| = |f| + |f|.Proof. To show that f + f is a flow, we must show skew symmetry, capacity constraints and flow conservation.a) Skew symmetry: 2022/8/913Flow Networksb) Capacity

14、constraints: note thatc) Flow conservation:d) Value: 2022/8/914Flow NetworksAugmenting Paths. Let G = (V, E) be a flow network with a flow f. An augmenting path p is a simple path from s to t in the residual network Gf. We define the residual capacity of p: cf(p) = mincf(u, v): (u, v) on p.Lemma 26.

15、3. Let G = (V, E) be a flow network, f a flow in G, p an augmenting path in Gf. DefineThen fp is a flow in Gf, with value |fp| = cf(p) 0.2022/8/915Flow NetworksLemma 26.4. Let G = (V, E) be a flow network, f a flow in G, p an augmenting path in Gf. Let fp be defined as in the previous Lemma. Define

16、by f = f + fp. Then f is a flow in G with value |f| = |f| + |fp| |f|.Proof: immediate form previous results.We now have a way, by the Ford-Fulkerson method, to construct a maximum flow in a flow network: keep augmenting a starter flow until there is no augmenting path left. This will be reasonable (

17、if the scheme actually delivers a maximum flow) if all the capacities are integers; if they are real numbers one may run into problems with the convergence of this scheme2022/8/916Flow NetworksDef.: a cut (S, T) of a flow network G = (V, E) is a partition of V into S and T = V - S s.t.If f is a flow

18、, f(S, T) is the net flow across the cut (S, T). The capacity of the cut is c(S, T).A minimum cut of a network is a cut whose capacity is minimum over all cuts of the network.Flow can be negative, but capacity is always positive.2022/8/917Flow NetworksLemma 26.5. Let f be a flow in a network G = (V,

19、 E), with source s and sink t. Let (S, T) be a cut of G. Then the net flow across (S, T) is f(S, T) = |f |.Proof. Recall: flow conservation implies f (S - s, V) = 0.Corollary 26.6. The value of any flow f in a flow network G is bounded above by the capacity of any cut in G.Proof. Let (S, T) be any c

20、ut of G, f any flow.2022/8/918Flow NetworksA useful immediate observation is that the maximum flow must be bounded by the capacity of a minimum cut. This would lead to the conjecture, possibly backed up by an algorithm and a proof, that the two quantities are the same Theorem 26.7. If f is a flow in

21、 a flow network G = (V, E) with source s and sink t, the following conditions are equivalent: f is a maximum flow in G. The residual network Gf contains no augmenting paths. |f | = c(S, T) for some cut (S, T) of G.2022/8/919Flow NetworksProof. (1) = (2). Assume not. Then there is a max flow f in G,

22、but Gf has an augmenting path p. Then the flow f + fp (defined as in Lemma 26.3) is a flow in G with value strictly greater than |f |, contradicting the maximality assumption.(2) = (3). Suppose Gf has no augmenting path - no path from s to t. Defineand T = V - S. S is a cut. For each pair of vertice

23、s u and v s.t. ,we have f (u, v) = c(u, v) - if not , which would put v in S. Thus |f | = f (S, T) = c(S, T).(3) = (1). Since |f | c(S, T) for all cuts (S, T), f must be a maximum flow.2022/8/920Flow NetworksFord-Fulkerson-Method(G, s, t) initialize flow f to 0 while there exists an augmenting path

24、p do augment flow f along p return fWe will need to show a) that augmentations can be well-defined; b) that the process of successive augmentations will terminate in a finite number of steps; c) that the flow returned is a maximal flow.2022/8/921Flow NetworksWe are now ready to state a more detailed

25、 variant of Ford-Fulkerson.2022/8/922Flow Networks2022/8/923Flow Networks2022/8/924Flow NetworksAnalysis. The first three lines are easy: but things can go bad from here.Start with “no particular strategy” for how we choose the augmenting path, but assume that all capacities have integer values. Let

26、 f* denote the maximum flow found by the algorithm, with |f*| denoting its (integer) value. It is conceivable that each pass of the while loop (lines 4-8) will increase the value of the flow by a single unit - but not less. Since finding an augmenting path (or finding that one does not exists) might

27、 require examining all the edges of Gf, the total cost of the loop is O(|E|f*|) - recall that the number of edges in Gf is never more than double that of G.2022/8/925Flow NetworksProblem 1: the bound is tight. The geometry would indicate that arbitrary strategies for finding the augmenting path shou

28、ld be avoided2022/8/926Flow NetworksProblem 2: convergence can be problematic. In case the capacities are irrational, the process may not even produce a max flow after a finite time. Computers cannot explicitly represent irrational numbers - floating point numbers ARE rationals - but other factors (

29、floating point error and drift) may be just as bad The example is taken from D. C. Kozen, The Design and Analysis of Algorithms, Springer-Verlag, 1992.Let r be the positive root of the quadratic x2 + x - 1:2022/8/927Flow NetworksThen r2 = 1 - r, and, more generally rn+2 = rn - rn-1 for any n 0. Sinc

30、e 0 r r r2 r3 0.Also:Consider the flow network:The long horizontal edges will be called flumes.2022/8/928Flow NetworksThe flumes have the capacity shown, all other edges have capacity r + 2. The max flow value is 1 + r + r2 = 2, by inspection (or the max-flow/min-cut theorem: cut the flumes for 2 -

31、all other cuts give a value r + 2 2).Start with the identically 0 flow. Assume that the first augmenting step leads us to push one unit of flow directly from s to t along the top flume. The flumes now have residual capacity of 0, r and r2 respectively - from top to bottom. We now proceed so that aft

32、er n iterations of the process the flumes will have residual capacities of 0, rn+1 and rn+2 in some order: choose the flume with minimum nonzero capacity, say d.2022/8/929Flow NetworksPush d units of flow forward (left-to-right) through this flume, back through the saturated flume (residual 0) and f

33、orward again though the remaining flume (which has enough residual capacity). Suppose we start with residual capacities of 0, rn and rn+1 on the flumes. At the end of the augmentation, the same three flumes have capacities of rn+1, rn - rn+1= rn+2 and 0, respectively.Repeat the process: it can be re

34、peated indefinitely, leaving ever higher powers of r on the flumes. The residual capacities tend to 0, so the flow value tends to the maximum flow value 2.If we add an edge of capacity 1 from s to t, this process will converge to a flow of value 2, while the maximum flow has value 3: convergence is

35、really compromised2022/8/930Flow NetworksEdmonds-Karp.Lemma 26.8. If the second E-K heuristic is run on a flow network G = (V, E) with source s and sink t, then for all vertices , the shortest path distance in the residual network Gf increases monotonically with each flow augmentation. Proof. Suppos

36、e for which a flow augmentation cause the shortest path distance from s to v to decrease. Let f be the flow just before the first augmentation that decreases some shortest path distance, f the flow just after. Let v be the vertex with the minimum whose distance was decreased by the augmentation: 202

37、2/8/931Flow NetworksLet be a shortest path from s to v in Gf, so thatBecause of the way in which v was chosen, the distance label of u did not decrease:Claim: Pf. Assume otherwise. Then which contradicts the assumption thatTo have and the augmentation must have increased the flow from v to u. Since

38、the augmentation changed the flow along a shortest path, the shortest path from s to u in Gf has (v, u) as its last edge. In conclusion:2022/8/932Flow NetworksWhich contradicts our assumption thatTheorem 26.9. If the second E-K heuristic is run on a flow network G = (V, E) with source s and sink t,

39、then the total number of flow augmentations performed by the algorithm is O(|V|E|).Note: using Dijkstras algorithm we obtain a time complexity of which should be compared to that of the first heuristic:2022/8/933Flow NetworksProof.Def. An edge (u, v) in a residual network Gf is critical on an augmen

40、ting path p if the residual capacity of p is the residual capacity of (u, v): cf(p) = cf(u, v).After augmentation of the flow along an augmenting path, any critical edge on the path disappears from the residual network. Also, at least one edge on each augmenting path must be critical. The proof will

41、 consist in showing that each of the |E| edges of G can e critical at most |V|/2 - 1 times.Let . Since augmenting paths are shortest paths by construction, when (u, v) is critical for the first time, we have: 2022/8/934Flow NetworksOnce the flow is augmented, (u, v) disappears from the residual netw

42、ork. It cannot reappear on an augmenting path until after the flow from u to v is decreased, which happens only if (v, u) is on an augmenting path. Let f be the flow in G when this event occurs. ThenBetween two successive times of criticality, the distance from u to the source has increased by at le

43、ast 2, being initially at least 0. The intermediate vertices on a shortest path from s to u cannot contain s, u or t : (u, v) on the critical path implies u t. Thus, until u es unreachable from s, its distance from s is, at most |V| - 2. Hence (u, v) can e critical at most (|V| - 2)/2 = |V|/2 - 1 ti

44、mes. Since O(|E|) pairs of vertices can have an edge between them in a residual graph, 2022/8/935Flow Networksthe total number of critical edges during the entire execution of the algorithm is O(|V|E|). Each augmentation has, by definition, at least one critical edge. The bound on the number of augm

45、entations follows. Each augmentation can be computed via Dijkstras algorithm.2022/8/936Flow NetworksMaximum Bipartite Matching. The next problem is usually stated as a pure combinatorial problem. Def. Let G = (V, E) be a graph. We say G is bipartite if V can be partitioned into two disjoint sets L a

46、nd R such thatA matching is a subset such that for all at most on edge of M is incident on v. is matched by matching M if some edge in M is incident on v, otherwise v is unmatched. A maximum matching is a matching of maximum cardinality: a matching M such that for any other matching M, |M| |M|.2022/

47、8/937Flow NetworksMatching example. The left matching is not maximal; the right one is.2022/8/938Flow NetworksWe first transform a “maximal” combinatorial problem into a maximal flow problem. Then we will apply the Ford-Fulkerson method to produce a maximum matching in an undirected bipartite graph

48、G.Given G = (V, E), we construct a flow network G = (V, E). Add new vertices s and t,Each edge is assigned unit capacity. Observe also: 2022/8/939Flow NetworksFlow Network Corresponding to a bipartite graph.2022/8/940Flow NetworksDef. A flow f on a flow network G = (V, E) is integer-valued if f(u, v

49、) is an integer for allLemma 26.10. Let G = (V, E) be a bipartite graph with partition and let G = (V, E) be its corresponding flow network. If M is a matching in G, then there is an integer-valued flow f in G with value |f | = |M|. Conversely, if f is an integer-values flow in G, then there is a ma

50、tching M in G with cardinality |M| = |f |.Proof. 1) Let M be a matching in G. Construct f. To define f : if , define f(s, u) = f(u, v) = f(v, t) = 1 and f(u, s) = f(v, u) = f(t, v) = -1. For all other edges in E, f(u, v) = 0. We need to verify (easy) that f satisfies skew symmetry, capacity and cons

51、ervation.2022/8/941Flow NetworksAll the paths are of the form s - u - v - t, carrying one unit of flow. All the paths have only vertices s and t in common. The net flow across the cut is equal to |M|. Thus |f | = |M|. 2) Given f, produce M. LetEach vertex has only one edge entering it, (s, u), with

52、capacity 1. By conservation of flow, u has at most one unit of positive flow leaving it. Since f is integer valued, the one unit of flow must leave on at most one edge. Thus one unit enters iff there is one vertex such that f(u, v) = 1, and at most one edge leaving u can carry a positive flow. 2022/8/942Flow Networks.A symmetric argument can be made for each .By these arguments (and definition o