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
2,2 6 7,2 6 9,6 3,3 2 5,5 d b(a+,2) 0 0 70. 2,0 7,0,0 t 4,0 c(b+,2) t(d+,2) 3, 40 d(e+,2) d(c+,2)
bes+ (4,4) 8,8 7, s(-,+g 9,8 c(s+,1) (3 3,3 (42) C 5,5 (44) d(c+,2) In the path(S, b, c, t)from s to t, edge(c, b)is reverse order
In the path (s,b,c,t) from s to t, edge (c,b) is reverse order
Suppose that vertex b is labeled, If fcb>0 then c is abeled(b,△c), where△c min(Ab, fcb If t is labeled, then an increasing flow is constructed ◆ We change fi to后+ At when(1j)∈E,if Gi,jEEthen we change fi to fi-At b(c-,2) 8,8 7,0 6 s(-,+0 9, c(s+,3) 身t(b+,2) 4,2 5,5 5,5
◆Suppose that vertex b is labeled, If fcb>0， then c is labeled (b- ,Δc), where Δc = min{Δb,fcb} ◆If t is labeled, then an increasing flow is constructed. ◆We change fij to fij +Δt when (i,j)E, if (i,j)E then we change fji to fji -Δt
0)Construct a initial conservation flow in N(,E, C). 1) Label s with(-,+∞) U=Xx is an adjacent vertex of s 2)Suppose that vertex i is labeled, andj is no labeled, where ∈U U=U-{} iIf(iJEE andf<ci, then ij is labeled (it, Aj), where Aj=min(Ai, Cir- fip, UUxx is an adjacent vertex of j. goto 3)) ii)If jEEand fi?0, then i is labeled(i-,Δj), whereΔj mn nAi, fi U=UUxx is an adjacent vertex of j Ifj is not labeled, then goto 4) 3)If t is labeled then f We change fi to fi +At. ifj is labeled with i+. If j is labeled with i-, then fi is changed to fi -At goto 1) else goto 2) 4)If U=#0 then goto 2)m else stop
▪ 0) Construct a initial conservation flow in N(V,E,C). ▪ 1) Label s with (-,+∞). ▪ U={x|x is an adjacent vertex of s} ▪ 2)Suppose that vertex i is labeled, and j is no labeled, where jU. ▪ U=U-{j} ▪ i) If (i,j)E and fij0，then ▪ {j is labeled (i-, Δj), where Δj = min{Δi，fji}. ▪ U=U∪{x|x is an adjacent vertex of j} } ▪ If j is not labeled, then goto 4) ▪ 3)If t is labeled then ▪ { We change fij to fij +Δt . if j is labeled with i+. ▪ If j is labeled with i-, then fji is changed to fji –Δt goto 1) ▪ else goto 2) ▪ 4)If U then goto 2) else stop
Theorem 5.24: The labeling algorithm produces a maximum flow Proof: P=xx is labeled when algorithm end, thus v-P=( xx is not labeled when algorithm end. By the labeling algorithm, sEP and tEV-P. Thus E(P,V-P)is a cut. (1)(i)∈E(PvP)(ie.ie∈P.j∈VP) (2)(,i)∈E(e.i∈P.j∈VP) f:=0. By lemma 5.3, the labeling algorithm produces a maximum flow
▪ Theorem 5.24: The labeling algorithm produces a maximum flow. ▪ Proof: P={x|x is labeled when algorithm end},thus V-P={ x|x is not labeled when algorithm end}. ▪ By the labeling algorithm, sP and tV-P. Thus E(P,V-P)is a cut. ▪ (1) (i,j) E(P,V-P)(i.e. iP. jV-P) ▪ fij=cij， ▪ (2) (j,i) E (i.e. iP. jV-P) ▪ fji=0. ▪ By lemma 5.3, the labeling algorithm produces a maximum flow
b(c-,2) 8,8 2,2 7,2 g(,+x 9,6 c(s+,3) 染t(+,2) 9 c(a+,1) 4,2 5,5 5,5 d d(c+,1)
5.8 Graph Matching Example: set of worker assign to a set of task Four tasks are to be assigned to four tasks workers. workers A Worker I is qualified to do tasks b and o B Worker 2 is qualified to do tasks AC and D Worker 3 is qualified to do tasks B and d 4 Worker 4 is qualified to do task a and c Can all 4 workers be assigned to different tasks for which they are qualified?
5.8 Graph Matching ▪ Example: Set of worker assign to a set of task ▪ Four tasks are to be assigned to four workers. ▪ – Worker 1 is qualified to do tasks B and C ▪ – Worker 2 is qualified to do tasks A,C and D ▪ – Worker 3 is qualified to do tasks B and D ▪ – Worker 4 is qualified to do task A and C. ▪ Can all 4 workers be assigned to different tasks for which they are qualified?