第6章圖與網(wǎng)絡(luò)分析

第6章圖與網(wǎng)絡(luò)分析第一頁(yè)，共96頁(yè)。問(wèn)題1(哥尼斯堡七橋問(wèn)題1736年):

Pregel河橫穿K?nigsberg城，河上建有七座橋，能否設(shè)計(jì)散步路線，走過(guò)所有七座橋，每座橋恰好經(jīng)過(guò)一次而回到同一地點(diǎn)？第二頁(yè)，共96頁(yè)。建立模型七橋問(wèn)題可以轉(zhuǎn)化為以下的問(wèn)題：從圖中某個(gè)點(diǎn)出發(fā)，能否每條邊只經(jīng)過(guò)一次，再回到起點(diǎn)？ABCDABCD第三頁(yè)，共96頁(yè)。十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)城市，能否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過(guò)每個(gè)城市恰好一次最后回到出發(fā)點(diǎn)？問(wèn)題2(哈密頓環(huán)球旅行問(wèn)題1859年):哈密頓圈（環(huán)球旅行游戲）第四頁(yè)，共96頁(yè)。問(wèn)題3(四色猜想):

英國(guó)大學(xué)生Guthrie（1852年）：一張地圖，只需要四種顏色就能保證每?jī)蓚€(gè)相鄰的地區(qū)顏色不同？第五頁(yè)，共96頁(yè)?！?.1圖與子圖無(wú)向圖基本概念有向圖基本概念關(guān)聯(lián)矩陣和鄰接矩陣主要結(jié)論子圖第六頁(yè)，共96頁(yè)。1無(wú)向圖基本概念無(wú)向圖G：一個(gè)有序二元組(N,E),記為G=(N,E)G的點(diǎn)集合：（例如：圖（1）中的

N={n1，n2，n3，n4，n5}是一個(gè)無(wú)向圖的點(diǎn)的集合）G的邊集合：E={eij}且eij={ni,nj}為右圖無(wú)序二元組eij的端點(diǎn)：有eij={ni,nj}，則稱ni和nj為

eij的端點(diǎn)，且稱eij

連接點(diǎn)ni和nj

環(huán)：兩個(gè)端點(diǎn)重合為一點(diǎn)的邊（例如右圖中的e11）重邊：兩個(gè)端點(diǎn)都相同的邊。孤立點(diǎn)：不與任何邊關(guān)聯(lián)的點(diǎn)（例如右圖中的n5）34512第七頁(yè)，共96頁(yè)。關(guān)聯(lián)：一條邊的端點(diǎn)稱為這條邊的關(guān)聯(lián)鄰接：與同一條邊關(guān)聯(lián)的端點(diǎn)稱為是鄰接的，同時(shí)如果兩條邊有一個(gè)公共端點(diǎn)，則稱這兩條邊是鄰接的有限圖：點(diǎn)和邊都是有限集合的圖（否則無(wú)限圖）空?qǐng)D：沒(méi)有任何邊的圖平凡圖：只有一個(gè)點(diǎn)的圖簡(jiǎn)單圖：既沒(méi)有環(huán)也沒(méi)有重邊的圖1無(wú)向圖基本概念一個(gè)圖G=(N,E),一般記|N|=n,|E|=m.第八頁(yè)，共96頁(yè)。完全圖每一對(duì)點(diǎn)之間均有一條邊相連的圖二分圖

G=(N,E)存在N的一個(gè)二分劃(S,T),使得G的每條邊有一個(gè)端點(diǎn)在S中，另一個(gè)端點(diǎn)在T中,記作G=(S,T,E)完全二分圖

G=(S,T,E)S中的每個(gè)點(diǎn)與T中的每個(gè)點(diǎn)都相連的簡(jiǎn)單二分圖簡(jiǎn)單圖G的補(bǔ)圖

與G有相同頂點(diǎn)集合的簡(jiǎn)單圖，且圖中的兩個(gè)點(diǎn)相鄰當(dāng)且僅當(dāng)它們?cè)贕中不相鄰1無(wú)向圖基本概念第九頁(yè)，共96頁(yè)。

例某地區(qū)有五個(gè)鎮(zhèn)A、B、C、D、E它們之間有公路相通的情況如圖所示。1無(wú)向圖基本概念第十頁(yè)，共96頁(yè)。

在圖論中，我們只關(guān)心兩點(diǎn)間是否有聯(lián)系，至于公路的大小、等級(jí)、狀況均無(wú)關(guān)緊要，亦即不考慮線段（邊）的長(zhǎng)度，點(diǎn)的位置帶有隨意性，它們并不按比例尺畫，如五個(gè)鎮(zhèn)之間的連接圖也可畫成右圖表示。

ABCDE1無(wú)向圖基本概念第十一頁(yè)，共96頁(yè)。圖G=(V,E)的圖解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.

一個(gè)圖會(huì)有許多外形不同的圖解,今后將不計(jì)較這種外形上的差別,而用一個(gè)容易理解的、確定的圖解去表示一個(gè)圖.1無(wú)向圖基本概念第十二頁(yè)，共96頁(yè)。n1n2n3n4n52有向圖基本概念第十三頁(yè)，共96頁(yè)。2有向圖基本概念有向圖G：一個(gè)有序二元組(N,A)，記為G=(N,A)

G的弧集合：A={aij}且aij={ni,nj}為有序二元組，若aij={ni,nj}，則稱aij從ni連向nj，

ni稱為aij的尾，nj為

aij的頭，ni稱為nj的前繼(先輩)，nj稱為

ni的后繼有向圖G的基本圖：對(duì)于G的每條弧用一條邊代替后得到的無(wú)向圖第十四頁(yè)，共96頁(yè)。3關(guān)聯(lián)矩陣13452簡(jiǎn)單圖的關(guān)聯(lián)矩陣：一個(gè)階矩陣:第十五頁(yè)，共96頁(yè)。階矩陣:簡(jiǎn)單有向圖的關(guān)聯(lián)矩陣：一個(gè)3關(guān)聯(lián)矩陣1342第十六頁(yè)，共96頁(yè)。3鄰接矩陣13452簡(jiǎn)單圖G=(N,E)的鄰接矩陣:一個(gè)|N|×|N|階矩陣A=(aij):第十七頁(yè)，共96頁(yè)。3鄰接矩陣1342簡(jiǎn)單有向圖G=(N,A)的鄰接矩陣:一個(gè)|N|×|N|階矩陣A=(aij):第十八頁(yè)，共96頁(yè)。n3n1n2n4n54主要結(jié)論（次的計(jì)算）各頂點(diǎn)次數(shù)為：d(n1)=4d(n2)=2d(n3)=1d(n4)=2d(n5)=？

無(wú)向圖有向圖n1n2n3n4各頂點(diǎn)次數(shù)為：d(n1)=d+(n1)+d-(n1)=3+0=3d(n2)=d+(n2)+d-(n2)=1+1=2第十九頁(yè)，共96頁(yè)。定理6.1.2（握手定理）

圖G=(N,E)(或G=(N,A))為任意圖,|N|=n,，|E|=m(或|A|=m)，則*推論

任何圖(無(wú)向的或者有向的)中，次數(shù)為奇數(shù)的頂點(diǎn)個(gè)數(shù)是偶數(shù)。定理6.1.3

有向圖G=(N,A),|N|=n,，|A|=m，則4主要結(jié)論第二十頁(yè)，共96頁(yè)。5子圖第二十一頁(yè)，共96頁(yè)。5子圖4導(dǎo)出子圖

G[E*]2真子圖G’1母圖Gn4n1n2n3n5n6支撐子圖G’V＝V’5導(dǎo)出子圖G[N*]第二十二頁(yè)，共96頁(yè)。§6.2圖的連通性圖的連通網(wǎng)絡(luò)基本概念第二十三頁(yè)，共96頁(yè)。1圖的連通（無(wú)向圖的路）135426圖G中路：一個(gè)點(diǎn)和邊交替序列

(ni,eij,nj,…,nk,ekl,nl)，簡(jiǎn)單路：邊不重的路初級(jí)路：點(diǎn)不重的路回路：在G中，一條至少包含一個(gè)邊并且起點(diǎn)=終點(diǎn)的路簡(jiǎn)單回路：邊不重的回路初級(jí)回路：點(diǎn)不重的回路第二十四頁(yè)，共96頁(yè)。1圖的連通（無(wú)向圖的連通性）點(diǎn)i和j點(diǎn)是連通的：G中存在一條{i，j}路G是連通的：G中任意兩點(diǎn)都是連通的連通分支：G的極大連通子圖注：G連通當(dāng)且僅當(dāng)G僅有一個(gè)連通分支；第二十五頁(yè)，共96頁(yè)。1圖的連通（無(wú)向圖的連通性）例一擺渡人欲將一只狼,一頭羊,一籃菜從河西渡過(guò)河到河?xùn)|.由于船小,一次只能帶一物過(guò)河，并且狼與羊,羊與菜不能獨(dú)處.給出渡河方法.解：用四維0-1向量表示(人,狼,羊,菜)在河西岸的狀態(tài)(在河西岸則分量取1,否則取0),共有24=16種狀態(tài).在河?xùn)|岸的狀態(tài)類似記作.

由題設(shè),狀態(tài)(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允許的,從而對(duì)應(yīng)狀態(tài)(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允許的.

以可允許的10個(gè)狀態(tài)向量作為頂點(diǎn),將可能互相轉(zhuǎn)移的狀態(tài)用線段連接起來(lái)構(gòu)成一個(gè)圖.

根據(jù)此圖便可找到渡河方法.第二十六頁(yè)，共96頁(yè)。1圖的連通（無(wú)向圖的連通性）(1,1,1,1)

(1,1,1,0)

(1,1,0,1)

(1,0,1,1)

(1,0,1,0)(0,0,0,0)

(0,0,0,1)

(0,0,1,0)

(0,1,0,0)

(0,1,0,1)(0,1,0,1)

(0,1,0,0)

(0,0,1,0)

(0,0,0,1)

(0,0,0,0)(1,0,1,0)

(1,0,1,1)

(1,1,0,1)

(1,1,1,0)

(1,1,1,1)河西=(人,狼,羊,菜)河?xùn)|=(人,狼,羊,菜)將10個(gè)頂點(diǎn)分別記為A1,A2,…,A10,則渡河問(wèn)題化為在該圖中求一條從A1到A10的路.

從圖中易得到兩條路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.第二十七頁(yè)，共96頁(yè)。1圖的連通（有向圖的路）有向圖G中的一條有向路：點(diǎn)和弧的交錯(cuò)序列

(ni,aij,nj,…,nk,akl,nl)，記為(ni,nl)有向路簡(jiǎn)單有向路：弧不重的有向路初級(jí)有向路：點(diǎn)不重的有向路有向回路：至少包含一條弧且ni=nj的(ni,nj)有向路簡(jiǎn)單有向回路：弧不重的有向回路初級(jí)有向回路：點(diǎn)不重的有向回路134256第二十八頁(yè)，共96頁(yè)。G是單側(cè)連通的：G中任意兩點(diǎn)至少存在一個(gè)點(diǎn)到另一個(gè)點(diǎn)的有向路G是強(qiáng)連通的：G中任意兩點(diǎn)都存在雙向的有向路G是弱連通的：如果圖G忽略方向是連通圖1圖的連通（有向圖的連通性）顯然：強(qiáng)連通圖→單側(cè)連通圖→弱連通圖。第二十九頁(yè)，共96頁(yè)。1圖的連通（有向圖的連通性）弱連通單向連通強(qiáng)連通第三十頁(yè)，共96頁(yè)。abfdec2242563452網(wǎng)絡(luò)v6v5v3v1v4v2365112436第三十一頁(yè)，共96頁(yè)。2網(wǎng)絡(luò)

一個(gè)圖連同定義在其邊集上的實(shí)數(shù)一起稱為一個(gè)網(wǎng)絡(luò)．網(wǎng)絡(luò)一般是連通圖．定義在邊集上的實(shí)數(shù)稱為邊的權(quán)數(shù)記為

wij＝w(vi，vj)

它與邊(vi，vj)具有一一對(duì)應(yīng)關(guān)系，可以用以表達(dá)網(wǎng)絡(luò)上的各種有關(guān)性質(zhì)，如路長(zhǎng)、流量、費(fèi)用等等．網(wǎng)絡(luò)的圖解即在每條邊旁標(biāo)上相應(yīng)的權(quán)數(shù)．若一網(wǎng)絡(luò)的每條邊都是無(wú)向邊，則稱為無(wú)向網(wǎng)絡(luò)，記為N＝(G，W)或N＝(V，E,W)

第三十二頁(yè)，共96頁(yè)。

若一網(wǎng)絡(luò)的每條邊都是有向邊，則稱為有向網(wǎng)絡(luò)，記為

N＝(D，W)或N＝(V，A,W)

若一網(wǎng)絡(luò)中既有無(wú)向邊，也有有向邊，則稱為混合網(wǎng)絡(luò)．

所謂網(wǎng)絡(luò)分析，即對(duì)網(wǎng)絡(luò)進(jìn)行定性和定量分析，以便為實(shí)現(xiàn)某種優(yōu)化目標(biāo)而尋求最優(yōu)方案．這方面的典型問(wèn)題有：最小樹問(wèn)題，最短路問(wèn)題，中心問(wèn)題，重心問(wèn)題，最大流問(wèn)題，最小費(fèi)用最大流問(wèn)題，網(wǎng)絡(luò)計(jì)劃問(wèn)題，等等．

3網(wǎng)絡(luò)第三十三頁(yè)，共96頁(yè)?！?.3樹與支撐樹樹樹的基本性質(zhì)支撐樹支撐樹的基本性質(zhì)在各種各樣的圖中，有一類圖是十分簡(jiǎn)單又非常具有應(yīng)用價(jià)值的圖，這就是樹。第三十四頁(yè)，共96頁(yè)。1樹例已知有六個(gè)城市，它們之間要架設(shè)電話線，要求任意兩個(gè)城市均可以互相通話，并且電話線的總長(zhǎng)度最短。v6v3v4v2v5v1第三十五頁(yè)，共96頁(yè)。1樹樹

連通且無(wú)回路的簡(jiǎn)單圖稱為樹，用T表示。T中次為1的點(diǎn)稱為葉子，次數(shù)大于1的點(diǎn)稱為分支點(diǎn)或內(nèi)點(diǎn)。第三十六頁(yè)，共96頁(yè)。1樹森林

非連通且每個(gè)連通分支是樹的圖。平凡圖也是樹稱為平凡樹。第三十七頁(yè)，共96頁(yè)。2樹的基本性質(zhì)1、T是連通且無(wú)回路(即T是樹)。2、T無(wú)回路且m=n-1,其中|V|=n,|E|=m。3、T連通且m=n-1。4、T無(wú)回路,但增加一邊后得到且僅得一個(gè)回路。5、T連通,但刪去任一邊后就不連通。6、每一對(duì)結(jié)點(diǎn)間有且僅有一條通路。v6v3v4v2v5v1給定圖T=<V,E>,以下關(guān)于樹的命題是等價(jià)的。第三十八頁(yè)，共96頁(yè)。定理6.3.2

非平凡樹至少有兩個(gè)次為1的點(diǎn)。如果T恰好有兩個(gè)次為1的點(diǎn)，則其他的點(diǎn)的次必都為2，因此，T是一條路。2樹的基本性質(zhì)第三十九頁(yè)，共96頁(yè)。3支撐樹圖G的一個(gè)支撐子圖T如果是樹，則稱T為G的一個(gè)支撐(生成)樹。設(shè)T=(V,E’)是G=(V,E)的一個(gè)支撐樹，稱T*=G\T為G的反樹。v6v5v2v3v4v1圖G中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為弦。v6v5v2v3v4v1第四十頁(yè)，共96頁(yè)。給定圖G，給出G的一個(gè)支撐樹T？3支撐樹結(jié)論：圖G有支撐樹的充要條件是圖G是連通的。第四十一頁(yè)，共96頁(yè)。4支撐樹的基本性質(zhì)支撐樹存在定理任何連通圖G至少有一棵生成樹。推論：1、設(shè)n階簡(jiǎn)單連通圖G中有m條邊，則m≥n-1。2、設(shè)n階無(wú)向連通圖G中有m條邊，T是G的一棵生成樹，T*是T的反樹，則T*有m-n+1條邊。第四十二頁(yè)，共96頁(yè)。水源某農(nóng)場(chǎng)的水稻田用堤埂分割成很多小塊。為了用水灌溉，需要挖開一些堤埂。問(wèn)最少挖開多少條堤埂，才能使水澆灌到每小塊稻田？4支撐樹的基本性質(zhì)第四十三頁(yè)，共96頁(yè)?！?.4最小樹問(wèn)題最小樹問(wèn)題最小樹問(wèn)題的求解第四十四頁(yè)，共96頁(yè)。1最小樹問(wèn)題設(shè)N=<V,E,W>是一帶權(quán)連通圖,G的支撐樹T的權(quán)w(T)就是T的邊上的權(quán)和.

最小樹在網(wǎng)絡(luò)G的所有生成樹中,權(quán)最小的那棵樹稱為G的最小生成樹。abfdec224256345最小樹第四十五頁(yè)，共96頁(yè)。2最小樹問(wèn)題的求解v3v21v42v53v641v2v3v4v5v6

避圈法（Kruskal算法）：開始選一條權(quán)最小的邊，以后每一步中，總從未被選取的邊中選一條權(quán)盡可能小，且與已選邊不構(gòu)成圈的邊。第四十六頁(yè)，共96頁(yè)。2最小樹問(wèn)題的求解655172344v1v2v3v4v5v6

破圈法：任選一個(gè)圈，從圈中去掉權(quán)最大的一條邊。在余下的圖中重復(fù)這個(gè)步驟，直到得到一不含圈的圖為止。第四十七頁(yè)，共96頁(yè)。2最小樹問(wèn)題的求解反圈法Step1

從圖G中任取一點(diǎn)vi,讓viS,其余各點(diǎn)均包含在S’=V\S中。Step2

從（S,S’)中選一條權(quán)最小的邊e=vivj，加到T中。Step3

令SvjS,S’\vjS’，(將所選邊的另一個(gè)頂點(diǎn)添加到S中）。Step4

重復(fù)2、3兩步，直到圖中所有點(diǎn)均包含在S中為止。第四十八頁(yè)，共96頁(yè)。v1v5v4v3v212243244v1v5v4v3v2122432442最小樹問(wèn)題的求解第四十九頁(yè)，共96頁(yè)。2最小樹問(wèn)題的求解v1v5v4v3v212243244v1v5v4v3v212243244第五十頁(yè)，共96頁(yè)。v1v2v3v4v5142313522最小樹問(wèn)題的求解第五十一頁(yè)，共96頁(yè)。練習(xí)：分別用三種方法求圖的最小支撐樹2543174341572最小樹問(wèn)題的求解第五十二頁(yè)，共96頁(yè)。最短有向路問(wèn)題最短有向路問(wèn)題的求解§6.5最短有向路問(wèn)題第五十三頁(yè)，共96頁(yè)。什么是最短有向路？v6v5v3v1v4v2365112436給定有向網(wǎng)絡(luò)N=(V,A,W)，設(shè)P為G的一條有向路，令在有向路P中的弧的權(quán)重的和則稱W(P)為P的權(quán)(或長(zhǎng))。G中從點(diǎn)i到點(diǎn)j的權(quán)最小的有向路稱為最短有向路。1最短有向路問(wèn)題第五十四頁(yè)，共96頁(yè)。2最短有向路問(wèn)題的求解

下面僅介紹在一個(gè)賦權(quán)有向圖中尋求最短路的方法——Dijkstra算法，它是在1959年提出來(lái)的。目前公認(rèn)，在所有的權(quán)wij

≥0時(shí)，這個(gè)算法是尋求最短路問(wèn)題最好的算法。并且，這個(gè)算法實(shí)際上也給出了尋求從一個(gè)始定點(diǎn)vs到任意一個(gè)點(diǎn)vj的最短路。第五十五頁(yè)，共96頁(yè)。算法步驟第五十六頁(yè)，共96頁(yè)。例求v1到v6的最短路。v6v5v3v1v4v236511243603549∞∞∞5811710v1到v6的最短路：v1—v2—v3—v5—v4—v6，距離為10。2最短有向路問(wèn)題的求解第五十七頁(yè)，共96頁(yè)。0v6v5v3v1v4v2365112436v1v2v3v4v5v635∞∞∞349∞∞485∞571171010v1到v6的最短路：v1—v2—v3—v5—v4—v6，距離為10。v1到v2的最短路：v1—v2，距離為3。v1到v3的最短路：v1—v2—v3，距離為4。v1到v4的最短路：v1—v2—v3—v5—v4，距離為7。v1到v5的最短路：v1—v2—v3—v5，距離為5。第五十八頁(yè)，共96頁(yè)。求從V1到其它所有點(diǎn)的最短路線及距離。2最短有向路問(wèn)題的求解第五十九頁(yè)，共96頁(yè)。v1v2v3v4v5v6v7v8

03∞7∞∞∞∞3675∞∞∞6658∞∞668∞12681012891091010第六十頁(yè)，共96頁(yè)?！?.6最大流問(wèn)題最大流問(wèn)題基本概念基本定理Ford-Fulkerson算法第六十一頁(yè)，共96頁(yè)。1最大流問(wèn)題最大流問(wèn)題：給定有向網(wǎng)絡(luò)，如果弧權(quán)表示兩點(diǎn)之間的流量限制，即弧的容量，則指定兩點(diǎn)之間的流量一定有一個(gè)上限，這個(gè)上限就是最大流。142312137100從點(diǎn)1到點(diǎn)4的最大流量為？第六十二頁(yè)，共96頁(yè)。2基本概念142312,1013,87,313,138,77,2容量流量守恒方程可行流增廣路(s,t)-割第六十三頁(yè)，共96頁(yè)。2基本概念容量：每個(gè)弧上的最大通過(guò)能力。用cij表示，即弧上的第一個(gè)數(shù)字；流量：弧上實(shí)際通過(guò)的流量，用fij表示，弧上的第二個(gè)數(shù)字；顯然0<=fij<=cij，如果fij=cij則稱為飽和弧；守恒方程：一般假定，除了出發(fā)點(diǎn)s和終點(diǎn)t，表示其他各點(diǎn)的流出和流入量相等的方程?？尚辛鳎簼M足

和守恒方程的流稱為可行流。最大流問(wèn)題，就是求一個(gè)可行流，使得流出出發(fā)點(diǎn)s或者流入終點(diǎn)t的總流量最大；142312,1013,87,313,138,77,2第六十四頁(yè)，共96頁(yè)。2基本概念142312,1013,87,313,138,77,2P為從s到t的一個(gè)無(wú)向路，P的一個(gè)弧(i,j)如果是從s到t，稱為前向弧，否則稱為背(后)向??；如果在一個(gè)路中每一個(gè)前向弧的流量都小于容量，每一個(gè)背向弧的流量都大于零，稱為一個(gè)增廣路；在增廣路的前向弧上增加一個(gè)單位流，同時(shí)在背向弧上減少一個(gè)單位流，則得到增大的可行流。第六十五頁(yè)，共96頁(yè)。2基本概念(s,t)-割：即割(S,T)，s和t分別在S和T中；(s,t)-割的容量：由S到T的全部的弧的容量之和；通過(guò)割的純流：S到T的流減去T到S流；142312,1213,97,113,138,87,0割(S,T):把始點(diǎn)在S中，終點(diǎn)在T中的所有弧構(gòu)成的集合稱為是割集；第六十六頁(yè)，共96頁(yè)。增廣路定理：可行流是最大流當(dāng)且僅當(dāng)不存在從s到t的增廣路；整流定理：如果網(wǎng)絡(luò)中所有弧的容量是整數(shù)，則存在整數(shù)最大流；最大流最小割定理：一個(gè)可行流的最大值等于所有(s,t)-割的最小容量(即分離s,t的最小割集的容量)；3基本理論142312,1213,97,113,138,87,0142312,1013,87,313,138,77,2出弧非飽和、入弧非零、標(biāo)號(hào)如何找增廣路？第六十七頁(yè)，共96頁(yè)。4Ford-Fulkerson算法基本原理：從一個(gè)可行流出發(fā)，尋找增廣路，增加流值，得到新的可行流，再尋找新的增廣路，一直到不存在增廣路為止，根據(jù)增廣路定理，便得到了最大流.v1v2v3v4s2,05,310,66,64,32,12,17,15,55,1t第六十八頁(yè)，共96頁(yè)。算法步驟第六十九頁(yè)，共96頁(yè)。[-,]4Ford-Fulkerson算法[+s,2][+v1,2]v1v2v3v4s2,05,310,66,64,32,12,17,15,55,1t[+v3,2]v1v2v3v4s2,25,510,66,64,32,12,17,15,55,3t出弧非飽和、入弧非零、標(biāo)號(hào)第七十頁(yè)，共96頁(yè)。v1v2v3v4s2,25,510,66,64,32,12,17,15,55,3t4Ford-Fulkerson算法[-,][+s,4][+v2,1][-v4,1][+v3,1]v1v2v3v4s2,25,510,76,64,32,12,27,05,55,4t第七十一頁(yè)，共96頁(yè)。v1v2v3v4s2,25,510,76,64,32,12,27,05,55,4t4Ford-Fulkerson算法[-,][+s,3][-v2,1][+v3,1]v1v2v3v4s2,25,510,86,64,32,02,27,05,55,5t第七十二頁(yè)，共96頁(yè)。v1v2v3v4s2,25,510,86,64,32,02,27,05,55,5t4Ford-Fulkerson算法[-,][+s,2]標(biāo)號(hào)范圍無(wú)法擴(kuò)大，得到最大流，最小割。最大流流量為10。第七十三頁(yè)，共96頁(yè)。4Ford-Fulkerson算法1436582658593672第七十四頁(yè)，共96頁(yè)。4Ford-Fulkerson算法143658,02,06,05,08,05,09,03,06,07,02第七十五頁(yè)，共96頁(yè)。143658,02,06,05,08,05,09,03,06,07,02[-,][+1,8][+2,5][+4,5]143658,52,06,05,58,05,09,53,06,07,02第七十六頁(yè)，共96頁(yè)。143658,52,06,05,58,05,09,53,06,07,02[-,][+1,2][+3,2][+5,2]143658,52,26,05,58,25,09,53,06,07,22第七十七頁(yè)，共96頁(yè)。143658,52,26,05,58,25,09,53,06,07,22[+1,3][+2,3][-,][+3,3][+5,3]143658,82,26,35,58,55,09,53,06,07,52第七十八頁(yè)，共96頁(yè)。143658,82,26,35,58,55,09,53,06,07,52[-,]標(biāo)號(hào)范圍無(wú)法擴(kuò)大，得到最大流，最小割。最大流流量為10。第七十九頁(yè)，共96頁(yè)?！?.7最小費(fèi)用流問(wèn)題最小費(fèi)用流問(wèn)題第八十頁(yè)，共96頁(yè)。1最小費(fèi)用流問(wèn)題stab1,23,11,23,41,2最小費(fèi)用流問(wèn)題：給定有向網(wǎng)絡(luò)，每條弧都有兩個(gè)數(shù)與之相聯(lián)系，一個(gè)是弧的容量cij，一個(gè)是單位流通過(guò)它的費(fèi)用wij。如果x=(xij)是一個(gè)從起點(diǎn)s到終點(diǎn)t的流，則必有一個(gè)費(fèi)用存在：如何確定每條弧上的流值xij

，使得總的費(fèi)用最小的問(wèn)題，就是最小費(fèi)用問(wèn)題。第八十一頁(yè)，共96頁(yè)。運(yùn)輸問(wèn)題第八十二頁(yè)，共96頁(yè)。對(duì)偶規(guī)劃第八十三頁(yè)，共96頁(yè)。算法步驟第八十四頁(yè)，共96頁(yè)。算例求如圖所示運(yùn)輸問(wèn)題的最優(yōu)解1231234-45-20-30-30355040

8

699912137149165第八十五頁(yè)，共96頁(yè)。迭代過(guò)程213123415

2030