下载此文档

算法课件lecture13章节.ppt

文档分类：IT计算机 | 页数：约25页举报非法文档有奖

1/25

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该文档所得收入归上传者、原创者。
3.下载的文档，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1/25 下载此文档

文档列表 文档介绍

MaximumFlowProblemNotionsanddefinitionsFordandFulkerson’works……worksDefinition:workG=(V,E)isadirectedgraphtogetherwithanonnegativemapC:ER,calledcapacity,andtwodistinguishedverticessandtcalledthesource(withnoin-edges)andthesink(withnoout-edges),-valuedfunctionf:ERthatsatisfiesthefollowingproperties:Capacityconstraint:ForalleE,0f(e)c(e)Flowconservation:ForallvV-{s,t},(v):thesetofedgesenteringvertexv(v):thesetofedgesleavingvertexvValueofaFlowCallFthevalueofaflowf,whereMaximum-flowProblemInput:workGwithsourcesandsinktOutput:aflowofmaximumvalueCutLetSbeasubsetofVsuchthatsSandtSC(SC=V\S),(S,SC)bethesetofedgesof(u,v)EwithuSandvSC,and(SC,S)bethesetofedgesof(u,v)EwithuSCandv(S,SC)(SC,S),thatis,Howtoproveit?ProofForvV-{s,t},SumitforvSC-{t}ConsiderAddtheabovetwoProofThatis:

算法课件lecture13章节来自淘豆网www.taodocs.com转载请标明出处.