離散數(shù)學(xué)-網(wǎng)絡(luò)模型-(2)市公開課一等獎省賽課獲獎?wù)n件

離散數(shù)學(xué)黃曉宇HuangSir@第1頁本講內(nèi)容網(wǎng)絡(luò)模型基本概念最大流算法最大流最小割匹配第2頁引例bc碼頭a煉油廠zed5324242求出從碼頭到煉油廠最大流量第3頁定義一個傳輸網(wǎng)絡(luò)是一個滿足以下條件簡單加權(quán)有向圖一個源一個匯有向邊(i,j)權(quán)Cij是非負(fù)數(shù)，稱為容量一個網(wǎng)絡(luò)流量是對每邊賦流量值，該值不超出所在邊容量。第4頁定義（二）G是一個傳輸網(wǎng)絡(luò)，Cij是(i,j)容量。G一個流量F賦予(i,j)值Fij，滿足：Fij

≤Cij對非源點和收點i和j，有中間節(jié)點流出流量＝流入流量第5頁定義（三）網(wǎng)絡(luò)流量起點a流出流量＝終點z流入流量，這個流量稱作流量F值網(wǎng)絡(luò)流中關(guān)鍵問題：最大流量碼頭a

bc煉油廠zed5,33,22,24,22,24,32,1第6頁超級源、匯w1bABd364c4323w2w32w1bABd364c4323aw3w2z∞∞∞∞∞第7頁使用網(wǎng)絡(luò)流表示問題P458：例10.1.9P459：習(xí)題1～7第8頁最大流算法傳輸網(wǎng)絡(luò)G一個最大流量是含有最大值流量，最大流可能存在多個；基本思想：從初始流量開始，重復(fù)增加，直至不能再增大。第9頁通路p=(v0,v1,…,vn)，v0=a，vn=z是從a到z一條通路；假如在p中邊e是從vi-1指向vi則稱是定向，不然稱是非定向第10頁通路（a

z）第11頁四種情況3，14，13，25，13，24，03，35，2第12頁定義設(shè)P是網(wǎng)絡(luò)G中從a到z通路，其中容量為C，流量為F,滿足：對P中定向邊(i,j),Fi,j<Ci,j對P中非定向邊(i,j),0<Fi,jCi,j–Fi,j假如(i,j)一致定向邊Xi,j=Fi,j假如(i,j)是非一致定向邊第13頁令?=mini{Xi,j}i,j=1,...,n

定義Fi,j*=Fi,j(i,j)不在P中Fi,j+?(i,j)是P中定向邊Fi,j-?(i,j)是P中非定向邊則F*={Fi,j*}是一個流量比F增值?d流.第14頁算法思想從流量0開始查找滿足定理通路，假如不存在，結(jié)束，流量就是最大通路增加流量?，goto2第15頁輸入：網(wǎng)絡(luò)G，容量C，a,z,n輸出：最大流量FProceduremax_flow(a,z,C,v,n)//v標(biāo)識為(predecessor(v)/前趨結(jié)點，val(v)/結(jié)點v流量增量第16頁第17頁//沒有新通路第18頁//正向邊第19頁//反向邊第20頁第21頁//增量F第22頁abced5,03,02,0b4,02,04,02,0(-,

∞)(a,

3)(b,

2)(a,

5)(c,

2)abced5,03,22,2b4,02,04,22,0(-,

∞)(a,

1)(d,

2)(a,

5)(d,

2)(c,

2)第23頁abced5,23,22,2b4,02,04,42,2(-,

∞)(a,

1)(a,

3)(d,

2)(e,