運(yùn)籌學(xué)第六章圖與網(wǎng)絡(luò)分析1

第十章圖與網(wǎng)絡(luò)分析§1.圖的基本概念

圖：由點(diǎn)和線構(gòu)成。點(diǎn)代表所研究的對象，線代表對象之間的關(guān)聯(lián)性質(zhì)。邊：兩點(diǎn)之間不帶箭頭的聯(lián)線?；。簝牲c(diǎn)之間帶箭頭的聯(lián)線。無向圖(圖)：由點(diǎn)及邊所構(gòu)成的圖。記為G=(V，E)，V，E分別是G的點(diǎn)集合和邊集合。一條聯(lián)結(jié)點(diǎn)vi，vj的邊記為[vi，vj](或[vj，vi]){vi}E={ei}A={ai}Va=點(diǎn)：邊：?。阂?、圖的定義、分類及述語1有向圖：由點(diǎn)及弧所構(gòu)成的圖，記為D=(V，A)，V，A分別是D的點(diǎn)集合和弧集合。一個方向是從vi指向vj的弧記為(vi，vj)圖G或D中的點(diǎn)數(shù)記為p(G)或p(D)，邊(弧)數(shù)記為q(G)或(q(D))，簡記為p,q。若邊e=[u,v]∈E，則稱u,v為e的端點(diǎn)，稱e是點(diǎn)u(及點(diǎn)v)的關(guān)聯(lián)邊。

相鄰：若vi與vj與是同一條邊的兩個端點(diǎn)，稱點(diǎn)vi與vj相鄰，若ei與ej有公共端點(diǎn)，則邊ei與ej相鄰若在圖G中，某個邊的兩個端點(diǎn)相同，則稱e是環(huán)。2若兩個點(diǎn)之間有多于一條的邊，稱這些邊為多重邊。簡單圖：一個無環(huán)，無多重邊的圖。多重圖：一個無環(huán)、但允許有多重邊的圖。

點(diǎn)v的次：以點(diǎn)v為端點(diǎn)邊的條數(shù)，記為dG(v)或d(v)。奇點(diǎn)：次為奇數(shù)的點(diǎn)偶點(diǎn)：次為偶數(shù)的點(diǎn)孤立點(diǎn)：次為零的點(diǎn)。懸掛點(diǎn)：次為1的點(diǎn)3

定理1：圖G=(V,E)中，所有點(diǎn)的次之和是邊數(shù)的兩倍，即Σd(v)=2qvV定理2：任一圖中，奇點(diǎn)的個數(shù)為偶數(shù)。給定一個圖G=(V,E)，一個點(diǎn)邊的交錯序列(vi1,ei1,vi2,ei2,…,vik-1,eik-1,vik)，如果滿足eit=[vit,vit+1](t=1,2,…,k-1)，則稱為一條聯(lián)結(jié)vi1和vik的鏈，記為(vi1,vi2,…,vik)，稱點(diǎn)vi2,vi3,…,vik-1為鏈的中間點(diǎn)。懸掛邊：懸掛點(diǎn)的關(guān)聯(lián)邊4鏈(vi1,vi2,…,vik)中，若vi1=vik,，則稱之為一個圈，記為(vi1,vi2,…,vik-1,vi1)。若鏈(vi1,vi2,…,vik)中，點(diǎn)vi1,vi2,…,vik都是不同的，則稱之為初等鏈；若圈(vi1,vi2,…,vik-1,vi1)中，點(diǎn)vi1,vi2,…,vik-1都是不同的，則稱之為初等圈。若鏈(圈)中含的邊均不相同，則稱之為簡單鏈（圈）。V1V2V4V5V3V9V8V7V6e1e2e4e3e5e6e7e8e9e10初等鏈

(v1,v2,v3,v6,v7)初等圈

(v1,v2,v3,v4,v1)簡單鏈

(v1,v2,v3,v4,v5,v3,v6,v7)簡單圈

(v4,v1,v2,v3,v5,v7,v6,v3,v4,)5連通圖：圖G中，若任何兩個點(diǎn)之間，至少有一條鏈。連通分圖(分圖)：若G是不連通圖，它的每個連通的部分稱為G的一個連通分圖。基礎(chǔ)圖：給定一個有向圖D=(V,A)，從D中去掉所有弧上的箭頭，所得到的無向圖。記之為G(D)。路（回路）：在有向圖D=(V,A)中，如果其基礎(chǔ)圖G(D)中某條鏈（圈）上的邊方向相同時，稱為路（回路）圖G1=(V1,E1)和圖G2=(V2,E2)，如果V1

V2

，E1

E2則稱G1是G2的一個子圖。若V1

＝V2

，E1

E2則稱G1是G2的一個支撐子圖。6二、圖的矩陣表示

1．權(quán)矩陣具有n個頂點(diǎn)的賦權(quán)圖G=（V，E），其邊（vi,vj）有權(quán)Wij，構(gòu)造矩陣A=（aij）n×n，其中，稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。

V1V5V4V3V276498243572．鄰接矩陣對于圖G=（V，E），|V|=n，構(gòu)造一個矩陣A=（wij）n×n，其中：例2對上圖構(gòu)造鄰接矩陣

V1V5V4V3V27649824358§2樹一、樹的概念及性質(zhì)例：已知有五個城市，要在它們之間架設(shè)電話線，要求任何兩個城市都可以互相通話（允許通過其它城市），并且電話線的根數(shù)最少。v1v5v4v2v391.樹的定義：連通且不含圈的無向圖稱為樹。

次為1的點(diǎn)稱為樹葉，次大于1的點(diǎn)稱為分枝點(diǎn)，樹的邊稱為樹枝。v1v2v3v5v4v6v1v2v3v5v4v6連通圖樹2.樹的性質(zhì)

（1）任何樹中必存在樹葉（任何樹中必存在次為1的點(diǎn)）10（2）樹中任意兩頂點(diǎn)間必有且僅有一條鏈

（3）在樹的兩個不相鄰的頂點(diǎn)間添上一條邊，就得唯一一個圈（4）樹中去掉任何一條邊，圖就不連通（5）具有n個頂點(diǎn)的樹的邊數(shù)為n-1（6）具有n個頂點(diǎn)，n-1條邊的連通圖是樹二、圖的支撐樹（生成樹）1．定義：G′=（V，E′）是G=（V，E）的支撐子圖，且G′是樹，則稱G′是圖G的一個支撐樹。

2．尋找支撐樹的方法（1）避圈法在已給出的具有n個頂點(diǎn)的圖G中，每步選出一條邊，使它與已選邊不構(gòu)成圈，直到選夠n-1條邊為止。11v1v2v3v5v4v6v1v2v3v5v4v6樹（2）破圈法在圖G上任取一個圈，從圈上任意去掉一條邊，將這個圈破掉，重復(fù)上述過程。直到圖G中沒有圈為止。

12三、最小支撐樹（生成樹）1．支撐樹的權(quán)賦權(quán)圖：給圖G=（V，E），對G中的每一條邊[vi,vj]賦予一個權(quán)wij，這樣的圖稱為賦權(quán)圖。支撐樹的權(quán)：賦權(quán)無向連通圖G=（V，E）中每條邊上有非負(fù)權(quán)。一棵支撐樹上所有樹枝上權(quán)的總和，稱為這個支撐樹的權(quán)。

2．最小支撐樹（最小樹）具有最小權(quán)的支撐樹稱為最小支撐樹。

133．求最小支撐樹的方法（1）避圈法在圖中選一條權(quán)數(shù)最小的邊，在以后的每步中，總從未被選取的邊中選一條權(quán)數(shù)最小的邊，并使之與已選取的邊不構(gòu)成圈（權(quán)數(shù)相同時，任選一條），直到選夠n-1條邊為止。1222233344512222314（2）破圈法先任取一個圈，從圈中去掉一條權(quán)數(shù)最大的邊（權(quán)數(shù)相同時任選一條），在余下的子圖中，重復(fù)上述步驟，直到無圈為止。

1222233344515§3最短路問題

一、最短路問題的描述賦權(quán)有向圖D=（V，A），弧aij=(vi,vj)，權(quán)wij若圖中任意兩點(diǎn)vs~vt間存在路，那么其中一條權(quán)數(shù)最小者稱為最短路。

1．Dijkstra算法（wij≥0）（1）基本思想：若{vs,v1,…vi,vk}是從vs到vk的最短路，則{vs,v1,…,vi}是從vs到vi的最短路。從vs出發(fā)，逐步向外探尋最短路。執(zhí)行過程中，與每一個點(diǎn)對應(yīng)，記錄下一個數(shù)（稱為這個點(diǎn)的標(biāo)號），它或者表示從vs到該點(diǎn)的最短路的權(quán)（稱為p標(biāo)號，永久性標(biāo)號），或者是從vs到該點(diǎn)的估計最短路的權(quán)的上界（T標(biāo)號，試探性標(biāo)號）。算法的每一步都把某一點(diǎn)的T標(biāo)號改為p標(biāo)號，當(dāng)終點(diǎn)vt得到p標(biāo)號時，全部計算結(jié)束，對于有n個頂點(diǎn)的圖，最多經(jīng)n-1步就可以得到從始點(diǎn)到各點(diǎn)的最短路。

16

2）步驟：①給vs的p標(biāo)號，p(vs)=0，其余各點(diǎn)均給T標(biāo)號，T（vi）=+∞②若vi為剛得到p標(biāo)號的點(diǎn)，把與vi有弧(邊)直接相連而且有屬于T標(biāo)號的節(jié)點(diǎn)，改為下列T標(biāo)號③比較所有具有T標(biāo)號的點(diǎn)，把最小者改為P標(biāo)號，即當(dāng)存在兩個以上最小者

時，可同時改為P標(biāo)號。

T(臨時)標(biāo)號：從vs到某一節(jié)點(diǎn)最短距離的上界。P(永久)標(biāo)號：從vs到某一節(jié)點(diǎn)的最短距離。17例

求節(jié)點(diǎn)vs到節(jié)點(diǎn)v5的最短距離及其路線vSv1v2v3v4v5122233344

[解]第一步：

P(vs)=0,T(vj)=∞,j=1,…,5，S1={vs}。第二步：T(v1)=min{T(v1),P(vs)+ds1}=min{∞,0+4}=4

(1)與節(jié)點(diǎn)vs直接相連的臨時標(biāo)號的節(jié)點(diǎn)為v1,v2，將這兩個節(jié)點(diǎn)的臨時標(biāo)號改為④若全部點(diǎn)均為P標(biāo)號則停止，否則用代替vi轉(zhuǎn)步驟②18T(v2)=min{T(v2),P(vs)+ds2}=min{∞,0+3}=3

(2)在所有T標(biāo)號中，最小的為T(v2)=3,于是令P(v2)=3，

S2={vs,v2}，

λ(v2)=vs第三步：

(1)與節(jié)點(diǎn)v2直接相連的臨時標(biāo)號的節(jié)點(diǎn)為v1和v4，把這兩個節(jié)點(diǎn)的T標(biāo)號改為T(v1)=min{T(v1),P(v2)+d21}=min{4,3+2}=4T(v4)=min{T(v4),P(v2)+d24}=min{∞,3+2}=5

(2).在所有T標(biāo)號中，T(v1)=4最小，于是令P(v1)=4,S3={vs,v2,v1}，

λ(v1)=vsvSv1v2v3v4v512223334419第四步：

(1).與節(jié)點(diǎn)v1相連的臨時標(biāo)號的節(jié)點(diǎn)為v3,v4，把這兩個節(jié)點(diǎn)的T標(biāo)號改為T(v3)=min{T(v3),P(v1)+d13}=min{∞,4+3}=7T(v4)=min{T(v4),P(v1)+d14}=min{5,4+1}=5

(2).在T標(biāo)號中，T(v4)=5最小，令P(v4)=5S4={vs,v2,v1,

v4}，

λ(v4)=v1或v2

第五步：

(1).與節(jié)點(diǎn)v4相連的T標(biāo)號有v3,v5把這兩個節(jié)點(diǎn)的T標(biāo)號改為vSv1v2v3v4v512223334420T(v3)=min{T(v3),P(v4)+d43}=min{7,5+2}=7T(v5)=min{T(v5),P(v5)+d45}=min{∞,5+4}=9

(2).T(v3)最小,P(v3)=7,

S5={vs,v2,v1,

v4,

v3}，

λ(v3)=v4或v1第六步：

(1).與v3相連的臨時標(biāo)號有v5T(v5)=min{T(v5),P(v3)+d35}=min{9,7+3}=9(2).P(v5)=9,S6={vs,v2,v1,

v4,

v3,

v5

}，

λ(v5)=v4最短路線：vs→v1→v4→v5vs→v2→v4→v5vSv1v2v3v4v512223334421當(dāng)賦權(quán)有向圖中，存在具負(fù)權(quán)的弧時，按Dijkstra算法來求會發(fā)生錯誤。按Dijkstra算法，

P(v3)=5，實(shí)際上P(v3)=32．逐次逼近算法

v158v2v3－5基本思想：如果v1到vj的最短路總是沿著該路從v1先到某一點(diǎn)vi，然后再沿邊（vi,vj）到達(dá)vj，則v1到vj的這條路必然也是v1到vi的最短路，令d1j表示從v1到vj的最短路長，則必有設(shè)任一點(diǎn)vi到任一點(diǎn)vj都有一條弧，如果（vi,vj）不是弧，則添加?。╲i,vj），令wij=+∞22迭代過程：①初始條件：t=1,d1j(1)=w1j(j=1,2,…,n)，如果v1與vj間無邊，其最短路長記為+∞

②t=2,3,…

③當(dāng)進(jìn)行到某一步如k步時，對所有j=1,2,…,n有

則停止，d1j(k)（j=1,2,…,n），即為v1到各點(diǎn)的最短路長

23例：求下圖所示賦權(quán)有向圖中從v1到各點(diǎn)的最短路v1v7v6v5v4v3v2v8-16-1-2382-11-511-37-5-32解：初始條件t=124v1v7v6v5v4v3v2v8-16-1-2382-11-511-37-5-322526尋求最短路徑的方法：反向追蹤法

利用d1j=d1k+wkj關(guān)系反推記錄下vk，再尋求一點(diǎn)vi，使d1k=d1i+wik，記錄下vi，直到v1為止，最短路即為（v1,…,vi,vk,vj）表中空格為+∞27d18=6,因d18=d16+w68，故記下v6d16=-1d16=d13+w36，故記下v3d13=-2d13=d11+w13，故記下v1

所以最短路為v1→v3→v6→v8在含有n個點(diǎn)的圖中，如果不含有總權(quán)小于零的負(fù)回路，求從v1到任一點(diǎn)的最短路權(quán)，用上述方法最多經(jīng)過n-1次迭代必定收斂，顯然如果圖中含有總權(quán)小于零的負(fù)回路，則最短路權(quán)沒有下界。28三、應(yīng)用舉例例：設(shè)備更新問題某企業(yè)使用一臺設(shè)備，在每年年初企業(yè)領(lǐng)導(dǎo)部門就要決定是購置新的，還是繼續(xù)使用舊的，若購置新設(shè)備，就要支付一定的購置費(fèi)用，若繼續(xù)使用舊設(shè)備，則需支付一定的維修費(fèi)用?，F(xiàn)要求制定一個五年的更新計劃，使總的支付費(fèi)用最少。已知設(shè)備在各年的購買費(fèi)，及不同機(jī)器役齡時的維修費(fèi)如下：第1年第2年第3年第4年第5年購買費(fèi)1111121213使用年數(shù)0-11-22-33-44-5維修費(fèi)用5681118[解]：方案很多，如何制定計劃可以使總支付費(fèi)用最少，可以將問題化為最短路問題。29設(shè)以vi(i=1,2,3,4,5)表示“第i年初購進(jìn)一臺新設(shè)備”這種狀態(tài)，以v6表示“第5年末”這種狀態(tài)；以弧(vi,

vj)表示“第i年初購置的一臺設(shè)備一直使用到第j年初”這一方案，以wij表示這一方案所需購置費(fèi)和維護(hù)費(fèi)之和。這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問題就可歸結(jié)為從圖中找出一條從v1到v6的最短路問題。按求解最短路的計算方法求得，v1→v3→v6，v1→v4→v6均為最短路，即有兩個最優(yōu)方案。五年總的支付費(fèi)用均為53。即：方案1：第一年初購置的設(shè)備使用到第三年初予以更新，然后一直使用到第五年末。五年的總費(fèi)用為53。方案2：第一年初購置的設(shè)備使用到第四年初予以更新，然后一直使用到第五年末。五年的總費(fèi)用為53。30v1v2v3v5v6v4163022165941224130173123172318(0)(16)(22)(30)(41)(53)31§4最大流問題如下是一運(yùn)輸網(wǎng)絡(luò)，弧上的數(shù)字表示每條弧上的容量，問：該網(wǎng)絡(luò)的最大流量是多少？vsv2v1v3v4vt432312234vsv2v1v3v4vt41121213232一、基本概念和基本定理

1．容量網(wǎng)絡(luò)在一個有向圖中，僅有一個入次為0的點(diǎn)vs稱為發(fā)點(diǎn)，一個出次為0的點(diǎn)vt稱為收點(diǎn)，其余點(diǎn)為中間點(diǎn)。這樣的有向圖稱為網(wǎng)絡(luò)。如果讓網(wǎng)絡(luò)的每一條弧都對應(yīng)一個非負(fù)的權(quán)數(shù)（稱為該弧的容量），則稱這樣的網(wǎng)絡(luò)為容量網(wǎng)絡(luò)。

2.網(wǎng)絡(luò)的流：定義在弧集合A上的一個函數(shù)f={f(vi,vj)}，稱f(vi,vj)為弧(vi,vj)上的流量。簡記為fij

上圖中的運(yùn)輸方案就是這個網(wǎng)絡(luò)上的一個流。每個弧上的運(yùn)輸量就是該弧上的流量。

333．可行流滿足以下三個條件的流①非負(fù)及容量限制條件：0≤fij≤cij②中間點(diǎn)（vi）平衡條件：③發(fā)點(diǎn)的純輸出等于收點(diǎn)的純輸入

4．最大流使流量達(dá)到最大的可行流稱為最大流。vsv2v1v3v4vt411212132

可行流總是存在的，零流就是一個可行流345.增廣鏈給定可行流f={fij}，使fij=cij的弧稱為飽和弧，使fij<cij的弧稱為非飽和弧，把fij=0的弧稱為零流弧，fij>0的弧稱為非零流弧。若是網(wǎng)絡(luò)中連接發(fā)點(diǎn)vs和收點(diǎn)vt的一條鏈，定義鏈的方向是vs→vt，則鏈上的弧被分成兩類：

前向?。?

）：與u同向的弧后向?。ā?/p>

）：與u反向的弧f是一個可行流。如果滿足則稱μ為從vs到vt關(guān)于f的一條增廣鏈。

非飽和弧非零流弧35圖中，鏈u=(v1-,v2,v3,v4,v5,v6)是一條增廣鏈。

u+={(v1-,v2),(v2,v3),(v3,v4),(v5,v6)}

u-={(v5,v4)},

u+中每條弧非飽和,

u-中每條弧非零流v1v3v2v4v6(10,5)(8,3)(5,1)(3,3)(3,2)(5,2)(6,3)(11,6)(17,2)(4,1)v5366.截集與截量設(shè)S，TV，ST=，我們把始點(diǎn)在S，終點(diǎn)在T中的所有弧構(gòu)成的集合，記為（S，T）。給定網(wǎng)絡(luò)D=(V,A,C)，若點(diǎn)集V被剖分為兩個非空集合V1和V1，使vs

V1，vt

V1，則把弧集(V1,V1)稱為是（分離vs和vt的）截集。若把一截集的弧從網(wǎng)絡(luò)中去掉，則從vs到vt便不存在路，即截集是vs到vt的必經(jīng)之路，

給定一截集(V1,V1)，把截集(V1,V1)中所有弧的容量之和稱為這個截集的容量(截量),記為v(f)

C(V1,V1)37vsv1v2v3v4vt(4,4)(8,1)(4,2)(2,2)(4,1)(2,1)(1,1)(7,2)(9,3)V1={vs,v2}V1={v1,v3,v4，vt}截集(V1,V1)={(vs,v1),(v2,v3),(v2,v4)}C(V1,V1)=CS1+C23+C24=4+2+2=838若對于一可行流f*，網(wǎng)絡(luò)中有一截集(V1*,V1*)，使得v(f*)=C(V1*,V1*)，則f必是最大流，而(V1*,V1*)，必定是容量最小的截集，即最小截集。

二、定理

1.網(wǎng)絡(luò)中的可行流是最大流的充要條件是網(wǎng)絡(luò)中不存在增廣鏈。

2．最大流量最小截量定理：任一網(wǎng)絡(luò)D中，從vs到vt的最大流的流量等于分離vs，vt的最小截集的容量。

截集有多個，截量最小者稱為最小截集容量（最小截）39三、尋找最大流的標(biāo)號法(Ford，F(xiàn)ulkerson)

1．判斷可行流f是否為最大流的方法①能否找出vs到vt的增廣鏈，若能，則說明f不是最大流，否則f就是最大流。②v(f)是否等于最小截量，若等，f就是最大流，否則就不是。2．標(biāo)號法的基本思想從一個可行流f出發(fā)，由發(fā)點(diǎn)vs開始，用對網(wǎng)絡(luò)D中的每個點(diǎn)進(jìn)行標(biāo)號的辦法尋找f的增廣鏈，若無，則f為所求的最大流，若有則在增廣鏈上進(jìn)行調(diào)整。使此鏈變?yōu)榉窃鰪V鏈；這時再檢查是否還有增廣鏈，若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。403．標(biāo)號算法的步驟從一個可行流出發(fā)經(jīng)過標(biāo)號過程與調(diào)整過程

1）標(biāo)號過程：兩種點(diǎn)：已標(biāo)號點(diǎn)（已檢查和未檢查兩種）、未標(biāo)號點(diǎn)標(biāo)號點(diǎn)的標(biāo)號包含兩部分第一個標(biāo)號表明它的標(biāo)號是從哪一點(diǎn)得到的，以便找增廣鏈，第二個標(biāo)號是為確定增廣鏈的調(diào)整量θ用的。

①給發(fā)點(diǎn)以標(biāo)號（0，+∞）②選擇一個已標(biāo)號的頂點(diǎn)vi，對于vi所有未給標(biāo)號的全部鄰接點(diǎn)vj按下列規(guī)則處理。

41

(1)若在弧(vi,vj)上，fij<cij，則給vj標(biāo)號(vi,l(vj))，這里l(vj)=min[l(vi)，

cij–fij]。這時點(diǎn)vj成為標(biāo)號而未檢查的點(diǎn)。

(2)若在弧(vj,vi)上，fji>0，則給vj標(biāo)號(–

vi,l(vj))，這里l(vj)=min[l(vi)，fji]。這時點(diǎn)vj成為標(biāo)號而未檢查的點(diǎn)。于是vi成為標(biāo)號而已檢查過的點(diǎn)。重復(fù)上述步驟，一旦vt被標(biāo)上號，表明得到一條從vs到vt的增廣鏈，轉(zhuǎn)入調(diào)整階段。

若所有標(biāo)號都已檢查過，而標(biāo)號過程進(jìn)行不下去，則算法結(jié)束，這時的可行流就是最大流。42

2)調(diào)整過程首先按標(biāo)號點(diǎn)的第一個標(biāo)號，利用“反向追蹤”的方法，找出增廣鏈。令調(diào)整量為

=l(vt)令fij+

(vi,vj)

+

fij′=fij–

(vi,vj)

—

fij(vi,vj)

去掉所有的標(biāo)號，對新的可行流f′={fij′}，重新進(jìn)入標(biāo)號過程。v(f′)=v(f)+

43vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例求下列網(wǎng)絡(luò)的最大流與最小截集。[解]一、標(biāo)號過程（1）先給vs標(biāo)上(0,+)。（2）檢查vs未標(biāo)號的鄰接點(diǎn)v1,v2在弧(vs,v1)上，fs1=7,cs1=9,fs1<cs1,

l(v1)=min{l(vs)，cs1–fs1}=min{+

，9–7}=2

則v1的標(biāo)號為(vs

，2)44在弧(vs,v2)上，fs2=3,cs2=5,fs2<cs2,

l(v2)=min{l(vs)，cs2–fs2}=min{+

，5–3}=2

則v2的標(biāo)號為(vs，2)vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)（3）檢查v1,在弧(v1,v3)上,f13=4,c14=4,不滿足標(biāo)號條件。在弧(v1,v4)上,f14=1,c14=3,f14<c14,l(v4)=min{l(v1)，c14–f14}=min{2，3-1}=2。則v4的標(biāo)號為(v1，2)45（4）檢查v4,在弧(v4,vt)上,f4t=7,c4t=7,不滿足標(biāo)號條件。在弧(v3,v4)上,f34=1>0，l(v3)=min{l(v4)，f34}=min{2，1}=1，則v3的標(biāo)號為(-v4，1)vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)46l(vt)=min{l(v3)，c3t–f3t}=min{1，6-3}=1，則vt的標(biāo)號為(v3,1)這樣，我們得到了一增廣鏈

,如圖所示。vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)