第八章續(xù)最大流問題

第八章續(xù)最大流問題第一頁，共二十一頁，編輯于2023年，星期四定義7.9.1設(shè)G＝〈Ｖ，Ｅ，Ψ〉是弱連通有向圖且C:E→R0(其中R0為非負(fù)實(shí)數(shù)集合。)如果加權(quán)圖〈G，C〉滿足：i)圖中恰有一個(gè)結(jié)點(diǎn)入度為0，稱為源。ii)圖中恰有一個(gè)結(jié)點(diǎn)出度為0，稱為匯。則稱〈G，C〉為網(wǎng)絡(luò)，C為該網(wǎng)絡(luò)的容量函數(shù)。對G的任意邊e,稱C(e)為e的容量?；靖拍?51142352sv2v1v3v4t

第二頁，共二十一頁，編輯于2023年，星期四

所謂網(wǎng)絡(luò)上的流，是指定義在弧集E上的函數(shù)f＝{f(vi,vj)}，并稱f(vi,vj)為弧(vi,vj)上的流量，簡記為fij。3,15,21,01,04,12,23,15,22,1sv2v1v3v4t標(biāo)示方式：每條邊上標(biāo)示兩個(gè)數(shù)字，第一個(gè)是容量，第二是流量第三頁，共二十一頁，編輯于2023年，星期四可行流、可行流的流量、最大流。可行流是指滿足如下條件的流：（1）容量限制條件：對G中每條邊(vi,vj),有（2）平衡條件：對中間點(diǎn)，有：（即中間點(diǎn)vi的物資輸入量等于輸出量）對收點(diǎn)vt與發(fā)點(diǎn)vs，有：（即vs發(fā)出的物資總量等于vt接收的物資總量），W是網(wǎng)絡(luò)的總流量。第四頁，共二十一頁，編輯于2023年，星期四可行流總是存在的，例如f={0}就是一個(gè)流量為0的可行流。所謂最大流問題就是在容量網(wǎng)絡(luò)中尋找流量最大的可行流。一個(gè)流f={fij}，當(dāng)fij=cij，則稱f對邊(vi,vj)是飽和的，否則稱f對邊(vi,vj)不飽和。最大流問題實(shí)際上是一個(gè)線性規(guī)劃問題。但利用它與圖的密切關(guān)系，可以利用圖直觀簡便地求解。第五頁，共二十一頁，編輯于2023年，星期四

給定容量網(wǎng)絡(luò)G＝(V,A,E)，若點(diǎn)集V被剖分為兩個(gè)非空集合V1和V2，使s∈V1，t∈V2，則把弧集(V1,V2)稱為（分離s和t的）割集。

顯然，若把某一割集的弧從網(wǎng)絡(luò)中去掉，則從s到t便不存在路。所以，直觀上說，割集是從s到t的必經(jīng)之路。351142352sv2v1v3v4t注：有向邊也稱為弧。第六頁，共二十一頁，編輯于2023年，星期四割集的例子sv1v4v3tv2邊集（s,v1），（v1,v3），（v2,v3），（v3,t），（v4,t）是G的割集。其頂點(diǎn)分別屬于兩個(gè)互補(bǔ)不相交的點(diǎn)集。去掉這五條邊，則圖不連通，去掉這五條邊中的任意1-4條，圖仍然連通。第七頁，共二十一頁，編輯于2023年，星期四

定義7.9.5割集的容量(簡稱割量)

最小割集割集(V1,V2)中所有起點(diǎn)在V1，終點(diǎn)在V2的邊的容量的和稱為割集容量。例如下圖中所示割集的容量為5351142352sv2v1v3v4t在容量網(wǎng)絡(luò)的所有割集中，割集容量最小的割集稱為最小割集（最小割）。第八頁，共二十一頁，編輯于2023年，星期四

對于可行流f＝{fij}，我們把網(wǎng)絡(luò)中使fij＝cij的弧稱為飽和弧，使fij<cij的弧稱為非飽和?。话咽筬ij＝0的弧稱為零流弧，使fij>0的弧稱為非零流弧。

設(shè)f是一個(gè)可行流，μ是從s到t的一條鏈，若μ滿足前向弧都是非飽和弧,后向弧都是都是非零流弧,則稱μ是（可行流f的）一條增廣鏈。3,15,21,01,04,12,23,15,22,1sv2v1v3v4t

若μ是聯(lián)結(jié)源點(diǎn)s和匯點(diǎn)t的一條鏈，我們規(guī)定鏈的方向是從s到t，則鏈上的弧被分成兩類：前向弧、后向弧。第九頁，共二十一頁，編輯于2023年，星期四

對最大流問題有下列定理：

定理7.9.1容量網(wǎng)絡(luò)中任一可行流的流量不超過其任一割集的容量。

定理7.9.2（最大流-最小割定理）任一容量網(wǎng)絡(luò)中，最大流的流量等于最小割集的割量。

推論1可行流f*＝{fij*}是最大流，當(dāng)且僅當(dāng)G中不存在關(guān)于f*的增廣鏈。

第十頁，共二十一頁，編輯于2023年，星期四求最大流的標(biāo)號法(Ford,Fulkerson)

標(biāo)號法思想是：先找一個(gè)可行流。對于一個(gè)可行流，經(jīng)過標(biāo)號過程得到從源點(diǎn)s到匯點(diǎn)t的增廣鏈；經(jīng)過調(diào)整過程沿增廣鏈增加可行流的流量，得新的可行流。重復(fù)這一過程，直到可行流無增廣鏈，得到最大流。第十一頁，共二十一頁，編輯于2023年，星期四

標(biāo)號過程:(1)給s標(biāo)號(-,+∞)，s成為已標(biāo)號未檢查的點(diǎn)，其余都是未標(biāo)號點(diǎn)。(2)取一個(gè)已標(biāo)號未檢查的點(diǎn)vi，對一切未標(biāo)號點(diǎn)vj：若有非飽和弧(vi,vj)，則vj標(biāo)號(vi,l(vj))，其中l(wèi)(vj)＝min[l(vi),cij–fij]，vj成為已標(biāo)號未檢查的點(diǎn)；若有非零弧(vj,vi)，則vj標(biāo)號(-vi,l(vj))，其中l(wèi)(vj)＝min[l(vi),fji]，vj成為已標(biāo)號未檢查的點(diǎn)。vi成為已標(biāo)號已檢查的點(diǎn)。(3)重復(fù)步驟(2)，直到t成為標(biāo)號點(diǎn)或所有標(biāo)號點(diǎn)都檢查過。若t成為標(biāo)號點(diǎn)，表明得到一條s到t的增廣鏈，轉(zhuǎn)入調(diào)整過程；若所有標(biāo)號點(diǎn)都檢查過，表明這時(shí)的可行流就是最大流，算法結(jié)束。

調(diào)整過程：在增廣鏈上，前向弧流量增加l(vt)，后向弧流量減少l(vt)。第十二頁，共二十一頁，編輯于2023年，星期四下面用實(shí)例說明具體的操作方法：例(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)sv2v1v3v4t(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)sv2v1v3v4t在圖中給出的可行流的基礎(chǔ)上，求s到t的最大流。(-,+∞)(s,4)(-v1,1)(-v2,1)(v2,1)(v3,1)(3,3)(5,2)(1,0)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)sv2v1v3v4t(vs,3)(-,+∞)

得增廣鏈，標(biāo)號結(jié)束，進(jìn)入調(diào)整過程

無增廣鏈，標(biāo)號結(jié)束，得最大流。同時(shí)得最小割。第十三頁，共二十一頁，編輯于2023年，星期四下圖中已經(jīng)標(biāo)示出了一個(gè)可行流，求最大流[-,∞][s,3][s,4][v2,4][-v4,2]sv1v2v3v4v5t(4,0)(5,2)(1,0)(4,0)(1,0)(2,2)(3,2)(4,0)(2,0)(5,2)[v4,3]如圖已經(jīng)得到增廣鏈，然后進(jìn)行調(diào)整。第十四頁，共二十一頁，編輯于2023年，星期四調(diào)整后的可行流如下圖：vsv1v2v3v4v5t(4,3)(5,2)(1,0)(4,3)(1,0)(2,2)(3,2)(4,0)(2,0)(5,5)[-,∞][vs,3][vs,1][v2,1][-v4,1][v3,1][v5,1]如圖已經(jīng)得到增廣鏈，然后進(jìn)行調(diào)整。第十五頁，共二十一頁，編輯于2023年，星期四調(diào)整后的可行流如下圖：vsv1v2v3v4v5t(4,4)(5,2)(1,0)(4,4)(1,0)(2,2)(3,1)(4,1)(2,1)(5,5)[-,∞][vs,3]如圖所示最小割集的容量（即當(dāng)前可行流的流量），就是最大流的流量。注：用該方法可以同時(shí)得到最小割集，即圖中連結(jié)已標(biāo)號的點(diǎn)與未標(biāo)號的點(diǎn)的邊集。第十六頁，共二十一頁，編輯于2023年，星期四具有實(shí)際背景的例子國慶大假期間旅游非?；鸨瑱C(jī)票早已訂購一空。成都一家旅行社由于信譽(yù)好、服務(wù)好，所策劃的國慶首都游的行情看好，要求參加的游客眾多，游客甚至不惜多花機(jī)票錢輾轉(zhuǎn)取道它地也愿參加此游。旅行社只好緊急電傳他在全國各地的辦事處要求協(xié)助解決此問題。很快，各辦事處將其已訂購機(jī)票的情況傳到了總社。根據(jù)此資料，總社要作出計(jì)劃，最多能將多少游客從成都送往北京以及如何取道轉(zhuǎn)機(jī)。下面是各辦事處已訂購機(jī)票的詳細(xì)情況表：第十七頁，共二十一頁，編輯于2023年，星期四成都重慶武漢上海西安鄭州沈陽昆明廣州北京成都105158121030重慶561525武漢10上海158西安86鄭州148沈陽18昆明810廣州82610第十八頁，共二十一頁，編輯于2023年，星期四用圖來描述就是成重武昆上廣西鄭沈京85101581210305615251015886141881082610源點(diǎn)s=成都，匯點(diǎn)t=北京。前面已訂購機(jī)票情況表中的數(shù)字即是各邊上的容量（允許通過的最大旅客量），當(dāng)各邊上的實(shí)際客流量為零時(shí)略去不寫，以零流作為初始可行流。第十九頁，共二十一頁，編輯于