圖論及算法充：最大流.doc

《圖論及算法充：最大流.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、圖論及算法最大流問(wèn)題1概念1.1運(yùn)輸網(wǎng)絡(luò)一個(gè)賦權(quán)有向圖，若滿足下列條件，稱為運(yùn)輸網(wǎng)絡(luò)。①連通，無(wú)自回路；②恰有一個(gè)結(jié)點(diǎn)入度為0的結(jié)點(diǎn)，稱為源點(diǎn)；③恰有一個(gè)結(jié)點(diǎn)出度為0的結(jié)點(diǎn)，稱為匯點(diǎn)；④每條弧的權(quán)稱為該弧的容量，弧的容量記作。示例：弧的權(quán)：道路的運(yùn)輸容量。1.2流為研究網(wǎng)絡(luò)的運(yùn)輸容量，提出“流”的概念。流：代表一個(gè)合理的運(yùn)輸方案。流中的弧值：代表在該弧上的運(yùn)輸量。運(yùn)輸網(wǎng)絡(luò)中流的定義：對(duì)每條弧給定一個(gè)非負(fù)實(shí)數(shù)，滿足下列條件：①若不存在，②對(duì)每一條弧，有③除源點(diǎn)、匯點(diǎn)外，對(duì)每一個(gè)結(jié)點(diǎn)，有。即對(duì)于結(jié)點(diǎn)j，所有流進(jìn)量等于流出量。示例：流的值：

2、8流的值：14流的值：整個(gè)運(yùn)輸方案的運(yùn)輸量。1.3割設(shè)N=(V,E)是一個(gè)運(yùn)輸網(wǎng)絡(luò)，S是V的子集，且源點(diǎn)∈S，匯點(diǎn)∈V-S?？煞QS為源子集，V-S為目標(biāo)子集。割：弧尾在S、弧頭在V-S的弧集，用(S,V-S)表示。即是源子集和目標(biāo)子集交界處的弧集。割的容量C(S，V-S)：設(shè)：C1=弧尾在S、弧頭在V-S的所有弧的容量和。C2=弧尾在V-S、弧頭在S的所有弧的容量和。則：C(S,V-S)=C1-C2C1=9C2=1C(S,V-S)=8C1=14C2=0C(S,V-S)=14定理：在運(yùn)輸網(wǎng)絡(luò)中，流的值=割的容量。2增載軌算法（Ford，F(xiàn)

3、ulkerson，1956）2.1源點(diǎn)到匯點(diǎn)的道路定義從源到匯的道路。道路記作v0,v1,…,vm-1,vm。性質(zhì)：對(duì)于，或是網(wǎng)絡(luò)的一條弧。前向邊：與道路方向一致的有向邊。后向邊：與道路方向相反的有向邊。2.2標(biāo)記法的標(biāo)記過(guò)程設(shè)為道路的運(yùn)輸容量，為道路上的運(yùn)輸量。標(biāo)記過(guò)程如下：①給源點(diǎn)標(biāo)記(-,∞)，表示從源點(diǎn)流出的流量可以任意。δx=∞②選擇一個(gè)已標(biāo)記結(jié)點(diǎn)x，對(duì)與x鄰接的所有未標(biāo)記結(jié)點(diǎn)y按下列規(guī)則處理：①若，令δy＝min{,δx}，給結(jié)點(diǎn)ｙ以標(biāo)記(+x,δy)（即前向邊未飽和）②若，令δy＝min{,δx}，給結(jié)點(diǎn)ｙ以標(biāo)記(-x,δ

4、y)（即后向邊有回流）③④⑤重復(fù)步驟㈡，直到收點(diǎn)ｚ被標(biāo)記：說(shuō)明存在一條可增廣道路，轉(zhuǎn)向增廣過(guò)程；若ｚ點(diǎn)不能獲得標(biāo)記，且不存在其他可標(biāo)記的結(jié)點(diǎn)：所得的流是最大流。3、標(biāo)記法的增廣過(guò)程㈠令u=z。㈡若u的標(biāo)記為(+v,δu)，則f(v,u)←f(v,u)+δz若u的標(biāo)記為(-v,δu)，則f(u,v)←f(u,v)-δz㈢若v=a，則把全部標(biāo)記去掉轉(zhuǎn)向標(biāo)記過(guò)程；否則，令u=v并回到增廣過(guò)程第㈡步。3示例3.1示例13.2示例2