運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五圖與網(wǎng)絡(luò)分析

2023/11/121運(yùn)籌學(xué)

OPERATIONSRESEARCH

2023/11/122§1．圖的基本概念與模型§2．樹圖和圖的最小部分樹§3．最短路問題§4．網(wǎng)絡(luò)的最大流§5．最小費(fèi)用流第六章圖與網(wǎng)絡(luò)分析2023/11/123BACD

當(dāng)?shù)氐木用駸嶂杂谶@樣一個(gè)問題：一個(gè)漫步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地。盡管試驗(yàn)者很多，但是都沒有成功。哥尼斯堡的七橋問題2023/11/124

為了尋找答案，1736年歐拉把陸地縮為一點(diǎn)，把橋作為連接點(diǎn)的邊，將這個(gè)問題抽象成圖形的一筆畫問題。即能否從某一點(diǎn)開始不重復(fù)地一筆畫出這個(gè)圖形，最終回到原點(diǎn)。歐拉在他的論文中證明了這是不可能的，因?yàn)檫@個(gè)圖形中每一個(gè)頂點(diǎn)都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就是古典圖論中的第一個(gè)著名問題。BACD2023/11/125

在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點(diǎn)和線來畫出各式各樣的示意圖。例有六支球隊(duì)進(jìn)行足球比賽，我們分別用點(diǎn)v1…v6

表示這六支球隊(duì)，它們之間的比賽情況，也可以用圖反映出來，已知v1

隊(duì)?wèi)?zhàn)勝v2

隊(duì)，v2

隊(duì)?wèi)?zhàn)勝v3隊(duì)，v3

隊(duì)?wèi)?zhàn)勝v5

隊(duì)，如此等等。這個(gè)勝負(fù)情況，可以用下圖所示的有向圖反映出來。v3v1v2v4v6v52023/11/126§6.1．圖的基本概念與模型

圖（graph）是由一些結(jié)點(diǎn)或頂點(diǎn)（nodes

orvertices）以及連接點(diǎn)的邊（edges）構(gòu)成。記做G={V,E}，其中V是頂點(diǎn)的集合，E是邊的集合。

給圖中的點(diǎn)和邊賦以具體的含義和權(quán)值，我們稱這樣的圖為網(wǎng)絡(luò)圖（賦權(quán)圖）一、基本概念2023/11/127

圖中的點(diǎn)用

v

表示，邊用

e表示，對每條邊可用它所聯(lián)結(jié)的點(diǎn)表示，如圖，則有：e1=[v1,v1]，e2=[v1,v2]或e2=[v2,v1]用點(diǎn)和點(diǎn)之間的線所構(gòu)成的圖，反映實(shí)際生產(chǎn)和生活中的某些特定對象之間的特定關(guān)系。通常用點(diǎn)表示研究對象,用點(diǎn)與點(diǎn)之間的線表示研究對象之間的特定關(guān)系。一般情況下，圖中點(diǎn)的相對位置如何，點(diǎn)與點(diǎn)之間線的長短曲直，對于反映研究對象之間的關(guān)系，顯的并不重要，因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。2023/11/128端點(diǎn)，關(guān)聯(lián)邊，相鄰

若邊e可表示為e

=[vi

,vj]，稱vi

和vj是邊

e

的端點(diǎn)，同時(shí)稱邊

e

為點(diǎn)vi

和vj的關(guān)聯(lián)邊，若點(diǎn)vi

,vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi

和vj相鄰；若邊ei與ej有公共端點(diǎn)，稱邊ei

和ej相鄰；

如果邊e

的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)，如果兩個(gè)點(diǎn)之間的邊多于一條，稱為具有多重邊，對無環(huán)、無多重邊的圖稱為簡單圖。環(huán)，多重邊，簡單圖2023/11/129次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)

與某個(gè)點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，稱為該點(diǎn)的次（或度、線度），記作

d(v)。次為奇數(shù)的點(diǎn)稱為奇點(diǎn)，次為偶數(shù)的點(diǎn)稱為偶點(diǎn)，次為零的點(diǎn)稱為孤立點(diǎn)。如圖：奇點(diǎn)為v5，v3偶點(diǎn)為v1,v2,

v4,

v6孤立點(diǎn)為

v62023/11/1210鏈，圈，路，回路，連通圖

圖中有些點(diǎn)和邊的交替序列μ={v0,e1,v1,e2,…,ek

,vk}，若其各邊e1,e2,…,ek

各不相同，且任意vi,t-1,vit(2≤t≤k)都相鄰，稱μ為鏈，如果鏈中所有的頂點(diǎn)v0,v1,…,vk也不相同，這樣的鏈成為路，起點(diǎn)和終點(diǎn)重合的鏈稱為圈，起點(diǎn)和終點(diǎn)重合的路稱為回路，若在一個(gè)圖中，每一對頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱該圖為不連通的。鏈路圈2023/11/1211完全圖，偶圖

一個(gè)簡單圖中若任意兩點(diǎn)之間均有邊相連，稱這樣的圖為完全圖，含有

n

個(gè)頂點(diǎn)的完全圖，其邊數(shù)有條。如果圖的頂點(diǎn)能分成兩個(gè)互不相交的非空集合V1和V2,使在同一集合中任意兩個(gè)頂點(diǎn)均不相鄰，稱這樣的圖為偶圖（也稱二分圖），如果偶圖的頂點(diǎn)集合V1和V2

之間的每一對頂點(diǎn)都有一條邊相連，稱這樣的圖為完全偶圖，完全偶圖中V1含m

個(gè)頂點(diǎn)，V2含有n

個(gè)頂點(diǎn)，則其邊數(shù)共m·n條。2023/11/1212子圖，部分圖

圖G1={V1,E1}和G2={V2,E2}，如果有和，稱G1是G2的一個(gè)子圖；若有，則稱G1是G2的一個(gè)部分圖。注意：部分圖也是子圖，但子圖不一定是部分圖。子圖：部分圖2023/11/1213§2．樹圖和最小部分樹

樹圖（簡稱樹，記作T(V,E)）是無圈的連通圖。（無圈，無多重邊）

一.樹的性質(zhì)性質(zhì)1.任何樹中必存在次為1的點(diǎn)。

次為1的點(diǎn)稱為懸掛點(diǎn)，與之關(guān)聯(lián)的邊稱為懸掛邊。

性質(zhì)2.具有

n

個(gè)頂點(diǎn)的樹恰有（n-1）條邊。

性質(zhì)3.任何具有n個(gè)點(diǎn)、(n-1)條邊連通圖是樹。說明：

1.樹中只要任意再加一條邊，必出現(xiàn)圈。

2.樹中任意兩點(diǎn)之間有且只有一條通路，從樹中任意刪掉一條邊，就不再連通。（樹是最脆弱的連通圖）2023/11/1214二.圖的最小部分樹如果G1是G2的部分圖，又是樹圖，則稱G1是G2

的部分樹（或支撐樹）；樹圖的各條邊稱為樹枝(假定各邊均有權(quán)重)；樹枝總長最小的部分樹，稱為該圖的最小部分樹(也稱最小支撐樹)。定理1.圖中任一個(gè)點(diǎn)i，若j

是與i相鄰點(diǎn)中距離最近的，則邊[i,j]一定包含在該圖的最小部分樹中。推論.把圖的所有點(diǎn)分成V和兩個(gè)集合，則兩集合之間連線的最短邊一定包含在最小部分樹內(nèi)。2023/11/1215三.避圈法和破圈法

尋找最小部分樹的方法主要有避圈法和破圈法兩種。

避圈法步驟：1.從圖中任選一點(diǎn)vi，讓vi

∈V，圖中其余點(diǎn)均包含在中；2.從V

與的連線中找出最小邊，這條邊一定包含在最小部分樹中，不妨設(shè)這條邊為[vi,vj]將其加粗，標(biāo)記為最小部分樹中的邊。3.令V∪vj→V，-vj→；4.重復(fù)2、3兩步，一直到圖中所有點(diǎn)均包含在V中。2023/11/1216

避圈法另一種做法：

1.在所有各邊中找到邊權(quán)最小的一條，將其作為最小部分樹中的第一邊；在剩余的邊中，仍然找到邊權(quán)最小的作為最小部分樹的第二條邊；2.在剩余的邊中，找到邊權(quán)最小的邊，查看其是否與前面的邊形成圈，如果沒有，則在最小部分樹中添加該邊，如果形成了圈，則不再考慮該邊；3.重復(fù)進(jìn)行第二步，直到找到第n-1條邊為止。（因?yàn)橛衝

個(gè)頂點(diǎn)的樹中一定有n-1條邊）2023/11/1217例：分別用兩種避圈法構(gòu)造下圖的最小部分樹。第一種解法：1.在點(diǎn)集中任選一點(diǎn)，不妨取S，令V={S}

2.找到和S

相鄰的邊中，權(quán)值最小的[S,A]。2023/11/12183.V={S,A}4.重復(fù)第2，3步，找到下一個(gè)點(diǎn)。2023/11/1219第二種做法求解過程：2023/11/1220破圈法求解步驟：1.從圖N中任取一回路，去掉這個(gè)回路中邊權(quán)最大的邊，得到原圖的一個(gè)子圖N1。2.從剩余的子圖中任找一回路，同樣去掉回路中邊權(quán)最大的一條邊，得一新的子圖；3.重復(fù)第2步，直到圖中不再含有回路為止。用破圈法求解上例：1.任意找到一回路，不妨取DETD，去掉邊權(quán)最大的邊[T,E];2023/11/12212.從剩余的子圖中任找一回路，同樣去掉回路中邊權(quán)最大的一條邊，得一新的子圖；依次類推。2023/11/1222破圈法的另一種解法：1.從剩余圖中找到邊權(quán)最大的一條邊，如果將其刪除后圖仍然是連通的，則刪除此邊，否則不再考慮此邊；2.重復(fù)上述步驟，直到剩余邊數(shù)為

n-1為止。用此法求解上述問題：2023/11/1223注意：1.一個(gè)圖的最小部分樹不唯一，該題中用幾種解法得到的結(jié)果都是相同的，是特殊情況；2.不同解法得到的最小部分樹所包含的邊雖然可能不相同，但是，每個(gè)最小部分樹中所有邊權(quán)的總和一定都是相同的，即都達(dá)到了最小。2023/11/1224§3．最短路問題最短路問題是指從給定的網(wǎng)絡(luò)圖中找出任意兩點(diǎn)之間距離最短（權(quán)值和最?。┑囊粭l路。某些整數(shù)規(guī)劃和動態(tài)規(guī)劃問題可以歸結(jié)為求最短路的問題。如選址問題、管道鋪設(shè)選線問題、設(shè)備更新、投資等問題。

最短路的求法：1.從某一點(diǎn)至其它各點(diǎn)之間最短距離的狄克斯屈拉(Dijksrta

)算法;2.求網(wǎng)絡(luò)圖中任意兩點(diǎn)之間的最短距離的矩陣算法。2023/11/1225

一.Dijkstra算法1.設(shè)

dij

表示圖中兩相鄰點(diǎn)i

與j

的距離，若i

與j

不相鄰，令dij

=∞，顯然dii=0。

Dijkstra算法假設(shè)：基本思路：如果v1→v2→v3→v4是v1→v4

的最短路徑，則v1→v2→v3

一定是v1→v3

的最短路徑。v2→v3→v4

一定是v2→v4的最短路徑。2.設(shè)Lsi表示從s點(diǎn)到i

點(diǎn)的最短距離。2023/11/1226Dijkstra算法步驟：1.對起始點(diǎn)

s，因Lss=0，將0標(biāo)注在s

旁的小方框內(nèi)，表示s

點(diǎn)已標(biāo)號；2.從點(diǎn)s

出發(fā)，找出與s相鄰的點(diǎn)中距離最小的一個(gè)，設(shè)為

r，將Lsr=Lss+dsr的值標(biāo)注在r

旁的小方框內(nèi)，表明點(diǎn)r

也已標(biāo)號；3.從已標(biāo)號的點(diǎn)出發(fā)，找出與這些點(diǎn)相鄰的所有未標(biāo)號點(diǎn)p，若有Lsp=min{Lss+dsp,Lsr+drp}，則對p點(diǎn)標(biāo)號，并將Lsp的值標(biāo)注在p點(diǎn)旁的小方框內(nèi)；4.重復(fù)第3步，直到

t

點(diǎn)得到標(biāo)號為止。求從起始點(diǎn)s

到終止點(diǎn)t的最短路徑。2023/11/1227例.求下圖中從v1到v7的最短路。解：(1)

從v1點(diǎn)出發(fā)，對v1點(diǎn)標(biāo)號，將L11=0標(biāo)注在旁的小方框內(nèi)，令v1∈V，其余點(diǎn)屬于；2023/11/1228L1r=min{0+d12

,0+d13

}=min{5,2}=2=L13(2)

同v1相鄰的未標(biāo)號點(diǎn)有v2、v3，2023/11/1229對

v3

標(biāo)號，將L13的值標(biāo)注在v3旁的小方框內(nèi)；將(v1,v3)加粗，并令V∪v3→V，。2023/11/1230L1p=min{L11+d12

,L13+d34,L13+d36

}=min{0+5,2+7,2+4}=5=L12(3)

同v1,v3相鄰的未標(biāo)號點(diǎn)有v2、v4、v6，2023/11/1231對

v2

標(biāo)號，將L12的值標(biāo)注在v2旁的小方框內(nèi)；將(v1,v2)加粗，并令V∪v2→V，2023/11/1232L1p=min{L12+d25

,L12+d24,

L13+d34

,L13+d36

}=min{5+7,5+2,2+7,2+4}=6=L16。(4)

同v1,v2

,v3相鄰的未標(biāo)號點(diǎn)有v4、v5、v6，2023/11/1233對

v6

標(biāo)號，將L16的值標(biāo)注在v6旁的小方框內(nèi)；將(v3,v6)加粗，并令V∪v6→V，2023/11/1234L1p=min{L12+d25

,L12+d24,L13+d34

,L16+d64,L16+d65,L16+d67

}=min{5+7,5+2,2+7,6+2,6+1,6+6}=7=L14=L15(5)

同v1,v2

,v3,

v6相鄰的未標(biāo)號點(diǎn)有v4、v5、v7，2023/11/1235對

v4,v5同時(shí)標(biāo)號，將L14=L15的值標(biāo)注在v4,v5旁的小方框內(nèi)；將(v2,v4),(v6,v5)加粗，并令V∪v4∪v5→V，2023/11/1236L1p=min{L15+d57

,L16+d67

}=min{7+3,6+6}=10=L17(6)

同v1,v2

,v3,v4,v5,

v6相鄰的未標(biāo)號點(diǎn)只有v7，2023/11/1237

對

v7

標(biāo)號，將L17的值標(biāo)注在v7旁的小方框內(nèi)；將(v5,v7)加粗。圖中粗線表明從點(diǎn)v1到網(wǎng)絡(luò)中其它各點(diǎn)的最短路，各點(diǎn)旁的數(shù)字就是點(diǎn)v1到各點(diǎn)的最短距離。2023/11/1238二.求任意兩點(diǎn)間最短距離的矩陣算法用Dijkstra

算法只能計(jì)算從圖中某一點(diǎn)到其他點(diǎn)的最短距離，如果要計(jì)算各點(diǎn)之間的最短距離就需要對每個(gè)點(diǎn)分別計(jì)算，而用矩陣算法則可以同時(shí)求出所有各點(diǎn)間的最短距離。例.利用矩陣算法求上述網(wǎng)絡(luò)圖中各點(diǎn)間的最短距離。解.設(shè)

dij

表示圖中兩相鄰點(diǎn)i

與j

的距離，若i

與j

不相鄰，令dij

=∞，顯然dii=0。建立距離矩陣：2023/11/12392023/11/1240從上述距離矩陣可以看出從i點(diǎn)到

j點(diǎn)的直接距離，但從i到j(luò)的最段距離不一定就是從i點(diǎn)直接到

j點(diǎn)。如上述問題中，從v1→v2的最短距離應(yīng)該是min{d11+d12,d12+d22,d13+d32,d14+d42,d15+d52,d16+d62,d17+d72}即min{d1r+dr2}。因此可以構(gòu)造一個(gè)新的矩陣D(1)，令D(1)中每一個(gè)元素為：dij(1)=min{dir+drj}，則矩陣D(1)給出了網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)及經(jīng)由一個(gè)中間點(diǎn)時(shí)的最短距離。2023/11/1241再構(gòu)造矩陣D(2)，

dij(2)=min{dir(1)

+drj(1)}。依次類推構(gòu)造矩陣D(k)，

dij(k)=min{dir(k-1)

+drj(k-1)}

計(jì)算停止的控制：

p是圖中頂點(diǎn)數(shù)。2023/11/1242該例中k=32023/11/1243

上述D(2)

中的元素給出了各點(diǎn)間的最短距離，但是并沒有給出具體是經(jīng)過了哪些中間點(diǎn)才得到的這個(gè)最短距離，如果要知道中間點(diǎn)具體是什么，需要在計(jì)算過程中進(jìn)行記錄。教材160頁例52023/11/1244§4．網(wǎng)絡(luò)的最大流一.網(wǎng)絡(luò)最大流的有關(guān)概念1.有向圖與容量網(wǎng)絡(luò)圖中每條邊有規(guī)定指向的圖稱為有向圖，有向圖的邊稱為弧，記作(vi,vj)，表示方向從點(diǎn)vi指向點(diǎn)vj，有向圖是點(diǎn)與弧的集合，記作D(V,A)?；?vi,vj)的最大通過能力，稱為該弧的容量，記為c(vi,vj)，或簡記為cij。定義了弧容量的網(wǎng)絡(luò)稱為容量網(wǎng)絡(luò)。2023/11/1245容量網(wǎng)絡(luò)通常規(guī)定一個(gè)發(fā)點(diǎn)(源點(diǎn)，記為s)一個(gè)收點(diǎn)(匯點(diǎn)，記為t)，網(wǎng)絡(luò)中其余的點(diǎn)稱為中間點(diǎn)。從發(fā)點(diǎn)到收點(diǎn)之間允許通過的最大流量稱為最大流。多個(gè)收(發(fā))點(diǎn)的網(wǎng)絡(luò)可以轉(zhuǎn)換為只含一個(gè)收(發(fā))點(diǎn)。2.流與可行流流是指加在網(wǎng)絡(luò)各條弧上的一組負(fù)載量，對加在弧(vi,vj)上的負(fù)載量記作f(vi,vj)，或簡記作

fij，若網(wǎng)絡(luò)上所有的fij=0，這個(gè)流稱為零流。2023/11/1246以v(f)表示網(wǎng)絡(luò)中從s→t

的流量，則零流是可行流，求最大流就是求v(f)的最大值。稱網(wǎng)絡(luò)上滿足下述條件(1)、(2)的流為可行流：(1)容量限制條件:對所有弧有0≤f(vi,vj)

≤c(vi,vj)(2)中間點(diǎn)平衡條件：∑f(vi,vj)-∑f(vj,vi)

=0(i≠s,t)2023/11/1247二.割和流量割(集）是指將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，并使s→t

的流中斷的一組弧的集合（截集）弧旁數(shù)字為cij(fij)有不同的割見教材162頁上圖中KK

將網(wǎng)絡(luò)上的點(diǎn)分割成V和兩個(gè)集合，并有s∈V,t∈，稱弧的集合(V,)={(v1,v3),(v2,v4)}是一個(gè)割。注意，這里不包含(v3,v2)。2023/11/1248割的容量是組成它的集合中各弧容量之和，用c(V,)表示，

f(V,)表示通過割(V,)中所有V→方向弧的流量的總和;f(,V)表示通過割中所有→V方向弧的流量的總和，則有：2023/11/1249從s→t

的流量等于通過割的從V→的流量減→V的流量，有：用v*(f)表示網(wǎng)絡(luò)中從s→t

的最大流，則有因此，上例中最大流不會超過14（所有割集中最小者）

。最大流v*(f)應(yīng)最小割的容量(用c*(V,)表示)2023/11/1250三.最大流最小割定理增廣鏈：如果在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在這條鏈上：所有指向?yàn)閟→t的?。ǚQ前向弧，記作μ+），存在f<c(非飽和)；（正向弧不飽和）所有指向?yàn)閠→s的?。ǚQ后向弧，記為μ

-），存在f>0(非零)，（反向弧非零流）這樣的鏈稱增廣鏈。2023/11/1251當(dāng)有增廣鏈存在時(shí)，找出再令顯然，經(jīng)過計(jì)算后

f’

仍然為可行流，但較原來的可行流f

流量增大了θ。因此，只有當(dāng)網(wǎng)絡(luò)圖中找不到增廣鏈時(shí)，s→t流才不可能進(jìn)一步增大。2023/11/1252定理2.在網(wǎng)絡(luò)中s→t

的最大流量等于它的最小割集的容量，即證明：略（教材163頁）三.求網(wǎng)絡(luò)最大流的標(biāo)號算法

Ford-Fulkerson

標(biāo)號算法，其本質(zhì)是判斷是否存在增廣鏈，如果存在，則找出增廣鏈，調(diào)整流量；若不存在，則說明已達(dá)到最大流。2023/11/1253第一步：首先給發(fā)點(diǎn)s標(biāo)號(0,ε(s))。第一個(gè)數(shù)字是使這個(gè)點(diǎn)得到標(biāo)號的前一個(gè)點(diǎn)的代號，因s

是發(fā)點(diǎn)，因此記為0。第二個(gè)數(shù)字ε(s)表示從上一個(gè)標(biāo)號到這個(gè)標(biāo)號點(diǎn)的流量的最大允許調(diào)整值，s為發(fā)點(diǎn)，不限允許調(diào)整容量，故ε(s)=∞。第二步：列出與已標(biāo)號點(diǎn)相鄰的所有未標(biāo)號點(diǎn)：考慮從標(biāo)號點(diǎn)

i

出發(fā)的弧(i,j)（即正向弧)，如果有

fij=cij，不給點(diǎn)

j

標(biāo)號；若fij<cij，則對j標(biāo)號，記為(i,ε(j))，其中

ε(j)=min{ε(i),(cij-fij)}2023/11/1254考慮所有指向標(biāo)號點(diǎn)i的弧(h,i)（即反向弧)

，如果有fhi=0，對h不標(biāo)號，若fhi>0，則對h

點(diǎn)標(biāo)號，記為(i,ε(h))，其中ε(h)=min{ε(i),fhi)}.

如果某未標(biāo)號點(diǎn)k

有兩個(gè)以上相鄰的標(biāo)號點(diǎn)，可按(1),(2)中所述規(guī)則分別計(jì)算出ε(k)的值，并取其中的最大的一個(gè)標(biāo)記。第三步：重復(fù)第二步可能出現(xiàn)如下兩種結(jié)果：

1.標(biāo)號過程中斷，t

得不到標(biāo)號，說明該網(wǎng)絡(luò)中不存在增廣鏈，給定流量即為最大流量。記已標(biāo)號點(diǎn)集為V，未標(biāo)號點(diǎn)集為，(V,)為網(wǎng)絡(luò)的最小割。t得到標(biāo)號，這時(shí)可用反向追蹤法在網(wǎng)絡(luò)中找到一條從s→t

的有標(biāo)號點(diǎn)以及相應(yīng)的弧連接而成的增廣鏈。2023/11/1255第四步：修改流量。設(shè)原圖中可行流為f，令這樣得到網(wǎng)絡(luò)上的一個(gè)新的可行流

f’

。第五步：抹掉圖上所有標(biāo)號，重復(fù)第一到第四步。注意：在求解步驟中，第三步起到控制運(yùn)算停止的作用，而不是第五步。2023/11/1256例：用標(biāo)號法求下述網(wǎng)絡(luò)圖

s→t的最大流量，并找出該網(wǎng)絡(luò)圖的最小割。2023/11/1257解：(1)先給s

點(diǎn)標(biāo)號(0,∞)；2023/11/1258(2)從s點(diǎn)出發(fā)的弧(s,v2)，因有fs2<cs2，且ε(v2)=min{ε(s),(cs2-fs2)}=2故對v2

點(diǎn)標(biāo)號(s,2)。

(s,v1)飽和，不標(biāo)號。2023/11/1259(3)弧(v1,v2)，因有f12>0

，且ε(v1)=min{ε(v2),f12)}=2故對v1

點(diǎn)標(biāo)號(v2

,2)。

(v2,v4)飽和，不標(biāo)號。2023/11/1260(4)弧(v1,v3)，因有f13<c13，且ε(v3)=min{ε(v1),(c13-f13)}=2故對v3

點(diǎn)標(biāo)號(v1

,2)。2023/11/1261(5)弧(v4,v3)，因有f43>0

，且ε(v4)=min{ε(v3),f43)}=1故對v4

點(diǎn)標(biāo)號(v3

,1)。

(v3,t)飽和，不標(biāo)號,v2已標(biāo)號。2023/11/1262(6)弧(v4,t)，因有f4t<c4t

，且ε(t)=min{ε(v4),(c4t-f4t)}=1故對t

點(diǎn)標(biāo)號(v4

,1)。2023/11/1263(7)由于收點(diǎn)t

得到標(biāo)號，用反追蹤法找出網(wǎng)絡(luò)圖上的一條增廣鏈。2023/11/1264(8)修改增廣鏈上各弧的流量：非增廣鏈上的所有弧流量不變，這樣得到網(wǎng)絡(luò)圖上的一個(gè)新的可行流。2023/11/1265重復(fù)上述標(biāo)號過程，由于對點(diǎn)

s、v1、v2、v3標(biāo)號后，標(biāo)號中斷，故圖中的可行流即為最大流，v*(f)=14已標(biāo)號點(diǎn)集為V={s,v1,v2,v3}，未標(biāo)號點(diǎn)集，(V,)={(3,t),(2,4)}為網(wǎng)絡(luò)的最小割。2023/11/1266三.應(yīng)用舉例例1：P166，例7ADECBF2321211111、方向含義2、E、D之間3、數(shù)字含義切斷A、F之間的通路，相當(dāng)于求最小割集。2023/11/1267例2：P167，例81、匹配關(guān)系1234562、匹配限制145f=1f14

f152023/11/1268134f=1f34

f14

3、等價(jià)網(wǎng)絡(luò)圖123456st1111111111112023/11/1269§5．最小費(fèi)用流

在產(chǎn)銷平衡問題中，研究的是使費(fèi)用最小的物資調(diào)運(yùn)方案；最大流問題中考慮了聯(lián)結(jié)兩個(gè)點(diǎn)之間的弧的容量限制，但是沒考慮流量通過各條弧時(shí)發(fā)生的費(fèi)用。

實(shí)際物資調(diào)運(yùn)中，既要考慮弧的容量又要考慮調(diào)運(yùn)費(fèi)用的節(jié)省，這就是最小費(fèi)用流要研究的問題。即要尋求一個(gè)最大流f，使