graphalgorithms(編輯修改稿)
2025-08-11 18:50 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 say, how much es in, also that much es out. – Find a maximum flow from s to t. – Denote the value of f as |f|=?v?Vf(s,v), ., the total flow out of the source s. ? |f|=?u?Vf(u,t), ., the total flow into the sink t. 9 Example of maxflow problem 10 FordFulkerson method ? Contains several algorithms: – Residue works – Augmenting paths 11 Residual Networks ? Given a flow work G=V,E and a flow f, – the residual work of G induced by f is Gf=V,Ef where Ef={(u,v)?V?V: cf(u,v)=c(u,v)f(u,v), and cf(u,v)0} – a work with left capacity 0, also a flow work. 12 Residual work and augmenting path 13 Residual work and flow theorem ? Lemma (page 653): – Let G=V,E be a flow work with source s and sink t, and let f be a flow, – Let Gf be the residual work of G induced by f, and let f39。 be a flow of Gf. – Define the flow sum: f+f39。 as: – (f+f39。)()=f()+f39。(), then – f+f39。 is a flow in G with value |f+f39。|=|f|+|f39。|. ? Proof: – Capacity constraint, skew symmetry, and flow conservation and finally |f+f39。|=|f|+|f39。|. 14 Augmenting paths ? Let G=V,E be a flow work with source s and sink t, and let f be a flow, ? An augmenting path p in G is a simple path from s to t in Gf, the residual work of G induced by f. ? Each edge (u,v) on an augmenting path admits some additional positive flow from u to v without violatin
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1