图论第四章.ppt

Graph Theory * Maximum Network Flow The value val(f) of a flow f is the net flow f –(t)-f +(t) into the sink. A maximum flow is a feasible flow of maximum value. Graph Theory * Example of Max Flow The zero flow assigns flow 0 to each edge It is feasible. (0)1 (0)1 (0)2 (0)2 (0)2 (0)2 (0)1 s v x y u t f Graph Theory * Example of Max Flow In the network below we illustrate a non-zero feasible flow. Capacities are shown in bold, flow values in parentheses. Our flow f assigns f(sx) = f(vt) = 0, and f(e) = 1 for every other edge e. This is a feasible flow of value 1. (1)1 (1)1 (0)2 (0)2 (1)2 (1)2 (1)1 s v x y u t f Graph Theory * Example of Max Flow A path from the source to the sink with excess capacity would allow us to increase flow. In this example, no path remains with excess capacity, but the flow f’ with f’(vx) = 0 and f’(e) = 1 for e ≠ vx has value 2. (1)1 (1)1 (0)2 (0)2 (1)2 (1)2 (1)1 s v x y u t f (1)1 (0)1 (1)2 (1)2 (1)2 (1)2 (1)1 s v x y u t f Graph Theory * f-Augmenting Path 4.3.4 When f is a feasible flow in a network N, an f-augmenting path is a source-to-sink path P in the underlying graph G such that for each e ∈ E(P), a) if P follows e in the forward direction, then f(e) c(e). b) if P follows e in the backward direction, then f(e)0. Let ε(e)=c(e) - f(e) when e is forward on P, and let ε(e)=f(e) when e is backward on P. The tolerance of P is mine∈E(P)ε(e). Graph Theory * New Flow after Augmenting The edges of P incident to an internal vertex v of P occur in one of the four ways shown below. In each case, the change to the flow out of v is the same as the change to the flow into v, so f ?(v) = f ?(v). + + - + + - - - Graph Theory * Lemma. If P is an f-augmenting path with tolerance z, then changing flow by +z on edges followed forward by P and by –z on edges followed backward by P produces a feasible flow f’ with val(f’) = val(f)+z. Proof: The definition of tolerance ensures that 0 ≤ f’(e) ≤ c(e) for every edge e, so the c