5.7 Transport Networks 5.7.1 Transport Networks Transport Networks A conservation flow f value of the conservation flow \ s Maximum flow Cut e(P,v-P Capacity of a cut Minimum cut
5.7 Transport Networks ▪ 5.7.1 Transport Networks ▪ Transport Networks ▪ A conservation flow f ▪ value of the conservation flow vf ▪ Maximum flow ▪ Cut E(P,V-P) ▪ Capacity of a cut ▪ Minimum cut
and any cut E(P, V-P), the result holds:V Theorem 5.23: For every conservation flow ≤C(P,VP) VsC(i,V-p) /<Cmin(P,V-P
▪ Theorem 5.23: For every conservation flow f and any cut E(P,V-P), the result holds: Vf C(P,V-P). ▪ Vf C(P,V-P)， ▪ Vfmax Cmin(P,V-P)
5.7.2A Maximum flow algorithm Lemma 5.3: Let f be a conservation flow, e(,V-P) be a cut. If ViC(,v-P),then Vr, Cmin(P,V-P=C(,V-P) max Proof: By the theorem 5.23 Theorem 5.23: For every conservation flow and any cut E(P,V-P), the result holds: VsC(,V-P)
▪ 5.7.2 A Maximum flow algorithm ▪ Lemma 5.3: Let f be a conservation flow, E(P,V-P) be a cut. If Vf=C(P,V-P)， then Vfmax =Vf ，Cmin(P,V-P)=C(P,V-P). ▪ Proof: By the theorem 5.23, ▪ Theorem 5.23: For every conservation flow f and any cut E(P,V-P), the result holds: Vf C(P,V-P)
Frod. Fulkerson 1956 1 We construct a initial conservation flow in N(,E, C) Generally, we seti°=0 for every edge〔i) ofn. the conservation flow is called zero flow 2) We shall construct an increasing sequence of flows f1,f2s.,f n, that has to terminate in a maximal flow How do we construct the increasing sequence
▪ Frod,Falkerson ▪ 1956 ▪ 1）We construct a initial conservation flow in N(V,E,C) ▪ Generally, we set fij 0=0 for every edge (i,j) of N. The conservation flow is called zero flow. ▪ 2 ） We shall construct an increasing sequence of flows f 1 , f 2 ,…, f n , that has to terminate in a maximal flow. ▪ How do we construct the increasing sequence?
Let u be an undirected pat th from s to t (1When u is a directed path from s to t, iffic for every edge of the path, then we change for every edge of the path, which equals minc lAbel s with(-,AS), where As=too 2)Suppose that vertex i is labeled, Let be an adjacent vertex of i, and no labeled. If fisc thenj is labeled (it, Aj, where Aj= min ai, 3)If t is labeled, then an increasing flow is constructed. We change fi to fi +At for every edge of the path u
▪ Let u be an undirected path from s to t, ▪ (1)When u is a directed path from s to t, if fij<cij for every edge of the path, then we change fij for every edge of the path, which equals min{cij-fij} ▪ 1)Label s with (-,Δs), where Δs=+∞ ▪ 2)Suppose that vertex i is labeled, Let j be an adjacent vertex of i, and no labeled. If fij<cij， then j is labeled (i+ , Δj), where Δj = min{Δi， cij- fij} ▪ 3)If t is labeled, then an increasing flow is constructed. We change fij to fij +Δt for every edge of the path u