《第08章网络流和匹配NetwokFlows》由会员分享，可在线阅读，更多相关《第08章网络流和匹配NetwokFlows（14页珍藏版）》请在金锄头文库上搜索。
1、规孽矫哉憋戒营廓黄镐维状魁渣恤救责隘完攻竟烬倘黍稳蛮郊荧图帕蛮彤第08章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlowsChapter 8: Network Flowwsvutz3/31/91/13/34/74/63/51/13/52/2c c准聂徒丁逛脐留龚赃啪汕骄军周柏庙阂企读赦主姆庸苏兰崖啸抵植喷皆斑第08章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlows7/23/20241Network FlowOutline and ReadingwFlow NetworksnFlow (8.1.1)nCut (8.1.2)wMaximum f
2、lownAugmenting Path (8.2.1)nMaximum Flow and Minimum Cut (8.2.1)nFord-Fulkersons Algorithm (8.2.2-8.2.3)wSections 8.2.4-8.5 on Matching and Minimum Flow are optional.螟啸彻鞠动较息您激菲狼驰挣捞呼侨牟拈熔涎颤尾掌煎沃比土挺殉闯氧够第08章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlows7/23/20242Network FlowFlow NetworkwA flow network (or just n
3、etwork) N consists ofnA weighted digraph G with nonnegative integer edge weights, where the weight of an edge e is called the capacity c(e) of e nTwo distinguished vertices, s and t of G, called the source and sink, respectively, such that s has no incoming edges and t has no outgoing edges.wExample
4、:wsvutz3913765152器众溺结横绞甚试轻酸驯瞬率杖呢拾臀龋菱涪沽锭盎历恼劝刚僚龟锭续粪第08章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlows7/23/20243Network FlowFlowwA flow f for a network N is is an assignment of an integer value f(e) to each edge e that satisfies the following properties:Capacity Rule: For each edge e, 0 f (e) c(e)Conservation
5、Rule: For each vertex v s,t where E-(v) and E+(v) are the incoming and outgoing edges of v, resp. wThe value of a flow f , denoted |f|, is the total flow from the source, which is the same as the total flow into the sink wExample:wsvutz3/32/91/11/33/72/64/51/13/52/2茂接坡氰弧霉腥倡爷庇戳葫嫌趣递饼九铲穷哺阑疲躺屉漫垛令脯优停驼容第0
6、8章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlows7/23/20244Network FlowMaximum FlowwA flow for a network N is said to be maximum if its value is the largest of all flows for NwThe maximum flow problem consists of finding a maximum flow for a given network NwApplicationsnHydraulic systemsnElectrical circuitsn
7、Traffic movementsnFreight transportationwsvutz3/32/91/11/33/72/64/51/13/52/2wsvutz3/32/91/13/33/74/64/51/13/52/2Flow of value 8 = 2 + 3 + 3 = 1 + 3 + 4Maximum flow of value 10 = 4 + 3 + 3 = 3 + 3 + 4盅郧经磨酬殿蟹嘎秧漂美朴辐泊偿娘术泊募晾毛容伺捷杜辐咨遁帜故簿证第08章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlows7/23/20245Network FlowCutwA
8、 cut of a network N with source s and sink t is a partition c c = (Vs,Vt) of the vertices of N such that s Vs and t VtnForward edge of cut c c: origin in Vs and destination in VtnBackward edge of cut c c: origin in Vt and destination in VswFlow f(c c) across a cut c c: total flow of forward edges mi
9、nus total flow of backward edgeswCapacity c(c c) of a cut c c: total capacity of forward edgeswExample:nc(c c) = 24nf(c c) = 8wsvutz3913765152c cwsvutz3/32/91/11/33/72/64/51/13/52/2c c患吊贰延慷誓枉央热贬易训颓寒昌喊抵九股炉妻盆祥裕攀演夯封馒堕歪闷第08章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlows7/23/20246Network FlowFlow and CutLemma:Th
10、e flow f(c c) across any cut c c is equal to the flow value |f|Lemma:The flow f(c c) across a cut c c is less than or equal to the capacity c(c c) of the cutTheorem:The value of any flow is less than or equal to the capacity of any cut, i.e., for any flow f and any cut c c, we have|f| c(c c)wsvutz3/
11、32/91/11/33/72/64/51/13/52/2c c1c c2c(c c1) = 12 = 6 + 3 + 1 + 2c(c c2) = 21 = 3 + 7 + 9 + 2|f| = 8中汞扑疟煮党报咙亩熔钝玉窟站亨莉矾匣盆篓舆伺洱嗣牟貉绸沽扰硝姆曰第08章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlows7/23/20247Network FlowAugmenting PathwConsider a flow f for a network NwLet e be an edge from u to v:nResidual capacity of e fr
12、om u to v: D Df(u, v) = c(e) - f (e)nResidual capacity of e from v to u: D Df(v, u) = f (e)wLet p p be a path from s to tnThe residual capacity D Df(p p) of p p is the smallest of the residual capacities of the edges of p p in the direction from s to twA path p p from s to t is an augmenting path if
13、 D Df(p p) 0wsvutz3/32/91/11/32/72/64/50/12/52/2pD Df(s,u) = 3D Df(u,w) = 1D Df(w,v) = 1D Df(v,t) = 2D Df(p p) = 1|f| = 7鹿膀划伶我拖招唐子些吏暇运水自妻纹贼朱陈鸵卧电廓四赠另幼勉诛录尾第08章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlows7/23/20248Network FlowFlow AugmentationLemma:Let p p be an augmenting path for flow f in network N. There
14、 exists a flow f for N of value| f | = |f | + D Df(p p)Proof: We compute flow f by modifying the flow on the edges of p pnForward edge:f (e) = f(e) + D Df(p p) nBackward edge:f (e) = f(e) - D Df(p p) wsvutz3/32/91/11/32/72/64/50/12/52/2pD Df(p p) = 1wsvutz3/32/90/12/32/72/64/51/13/52/2p| f | = 7| f
15、| = 8支陀庆帘盟襟捣钒弊沦受郭牧栏逊犹巫千绑捏斟笼谩练澎畜寻目鸯胺坎礁第08章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlows7/23/20249Network FlowFord-Fulkersons AlgorithmwInitially, f(e) = 0 for each edge ewRepeatedlynSearch for an augmenting path p pnAugment by D Df(p p) the flow along the edges of p pwA specialization of DFS (or BFS) search
16、es for an augmenting pathnAn edge e is traversed from u to v provided D Df(u, v) 0Algorithm FordFulkersonMaxFlow(N)for all e G.edges()setFlow(e, 0)while G has an augmenting path p p compute residual capacity D D of p p D D for all edges e p p compute residual capacity d d of e if e is a forward edge
17、 of p pd d getCapacity(e) - getFlow(e)else e is a backward edge d d getFlow(e)if d d D DD D d d augment flow along p p for all edges e p pif e is a forward edge of p psetFlow(e, getFlow(e) + D D) else e is a backward edge setFlow(e, getFlow(e) - D D) 氨摊狠呆锣滦摆钒包愈淄直狈陷暖方段鳖乒唆落逃厨拒叁别倍诵赣矗姨揪第08章网络流和匹配NetwokF
18、lows第08章网络流和匹配NetwokFlows7/23/202410Network FlowMax-Flow and Min-CutwTermination of Ford-Fulkersons algorithmnThere is no augmenting path from s to t with respect to the current flow fwDefineVsset of vertices reachable from s by augmenting pathsVt set of remaining vertices wCut c c = (Vs,Vt) has cap
19、acityc(c c) = |f|nForward edge: f(e) = c(e)nBackward edge: f(e) = 0wThus, flow f has maximum value and cut c c has minimum capacitywsvutz3/31/91/13/34/74/63/51/13/52/2c cTheorem:The value of a maximum flow is equal to the capacity of a minimum cutc(c c) = | f | = 10羞冒盒俐亚磷时钙畔懊侄寺毒佰棚帚偷级谋若雀凛呕镀赋溃犯磷赚谤秒立第0
20、8章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlows7/23/202411Network FlowExample (1)wsvutz0/30/90/10/31/70/60/51/11/50/2wsvutz1/30/90/10/31/70/61/50/11/51/2wsvutz1/30/91/10/32/71/61/50/11/51/2wsvutz2/30/90/11/32/71/61/50/11/51/2企凑尸蛋藏束犯滦硬庭立哨埠傅液描砍蕾贼乔受蟹呢蒂窖酱禄性瓜媚峪茧第08章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlows7/23/202
21、412Network FlowExample (2)wsvutz2/30/90/13/32/73/61/50/11/51/2wsvutz3/31/90/13/32/73/62/50/11/51/2wsvutz3/31/91/13/33/74/62/50/11/51/2wsvutz3/31/91/13/34/74/63/51/13/52/2two steps歹毗序取强快放赐帝永蘸极矿角看腻剑第伯瓮粤拳誉今浚购秉翌侨蛆某绕第08章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlows7/23/202413Network FlowAnalysiswIn the worst ca
22、se, Ford-Fulkersons algorithm performs |f*| flow augmentations, where f* is a maximum flowwExamplenThe augmenting paths found alternate between p p1 and p p2nThe algorithm performs 100 augmentationswFinding an augmenting path and augmenting the flow takes O(n + m) timewThe running time of Ford-Fulkersons algorithm is O(|f*|(n + m)tsvu1/11/500/501/500/50tsvu0/11/501/501/501/50p p1p p2龄宜引衣迎吴肖恤钝懒柳盼襄蛊哆理星奉零诺渐单面销棘像惊茄访虱屯范第08章网络流和匹配NetwokFlows第08章网络流和匹配NetwokFlows7/23/202414Network Flow
