運(yùn)籌學(xué)圖論概述

本章重點(diǎn)圖的基本概念常見(jiàn)的四個(gè)問(wèn)題的求解方法圖的含義圖是一種模型如公路、鐵路交通圖，通訊網(wǎng)絡(luò)圖等圖是對(duì)現(xiàn)實(shí)的抽象很多問(wèn)題都可以用頂點(diǎn)和邊來(lái)表示，一般頂點(diǎn)表示實(shí)體，邊(頂點(diǎn)與頂點(diǎn)之間的連線(xiàn))表示實(shí)體之間的關(guān)系，頂點(diǎn)和邊的集合定義為圖圖論的提出(1)用圖來(lái)描述事物及其聯(lián)系，最早是由瑞士數(shù)學(xué)家歐拉(Euler)于1736年解決哥尼斯堡七橋問(wèn)題時(shí)提出的如右圖所示，哥尼斯堡地區(qū)被河流分為了四個(gè)區(qū)域，四個(gè)區(qū)域之間有七座橋相連，問(wèn)是否有一條路線(xiàn)，可以經(jīng)過(guò)所有的橋并且每座橋只經(jīng)過(guò)一次？BACD圖論的提出(2)用圖來(lái)表示這個(gè)問(wèn)題用四個(gè)頂點(diǎn)表示四個(gè)地區(qū)用七條邊表示七座橋要尋找這樣的一條路線(xiàn)：經(jīng)過(guò)所有的邊并且每條邊只經(jīng)過(guò)一次該問(wèn)題已經(jīng)證明無(wú)解圖的基本概念(1)圖：頂點(diǎn)和邊的集合點(diǎn)的集合用V表示，邊的集合用E表示，則圖可以表示為G=(V,E)如下圖G=(V,E)其中，V={A,B,C,D}E={e1,e2,e3,e4,e5,e6,e7}E中，e1=(A,D),e2=(B,D),e3=(C,D)e4=(B,C),e5=(A,C),e6=(A,C),e7=(B,C)e2e1e3e4e5e6e7圖的基本概念(2)邊都沒(méi)有方向的圖稱(chēng)為無(wú)向圖，前面所講的圖就是無(wú)向圖。無(wú)向圖的邊eij=(vi,vj)=(vj,vi)=eji當(dāng)圖中的邊都有方向時(shí)，稱(chēng)為有向圖。為了區(qū)別于無(wú)向圖，有向圖用G(V,A)表示在有向圖中，有向邊又稱(chēng)為弧，用aij=(vi,vj)表示，(vi,vj)≠(vj,vi)，弧的方向用箭頭標(biāo)識(shí)既有邊又有弧的圖稱(chēng)為混合圖下圖中從左向右依次為：無(wú)向圖，有向圖，混合圖圖的基本概念(3)集合V中元素的個(gè)數(shù)稱(chēng)為圖G的頂點(diǎn)數(shù)，記作p(G)。前例中，p(G)=4集合E(或A)中元素的個(gè)數(shù)稱(chēng)為圖G的邊數(shù)，記作q(G)。前例中，q(G)=7若e=(u,v)∈E(或a=(u,v)∈A)，則稱(chēng)u和v為e(或a)的端點(diǎn)，e(或a)稱(chēng)為頂點(diǎn)u和v的關(guān)聯(lián)邊，也稱(chēng)u,v與邊e(或a)相關(guān)聯(lián)。前例中，A,B是邊e1的端點(diǎn)，e1是A,B的關(guān)聯(lián)邊若頂點(diǎn)u和v與同一條邊相關(guān)聯(lián)，則稱(chēng)u和v為相鄰點(diǎn)若兩條邊ei和ej有同一個(gè)端點(diǎn)，則稱(chēng)ei和ej為相鄰邊圖的基本概念(4)若一條邊的兩個(gè)端點(diǎn)是同一個(gè)頂點(diǎn)，則稱(chēng)該邊為環(huán)若兩個(gè)端點(diǎn)之間有多于一條邊，則稱(chēng)為重邊(書(shū)上稱(chēng)為多重邊)，前例中，A,C之間和B,C之間都有兩條邊無(wú)環(huán)也無(wú)重邊的圖稱(chēng)為簡(jiǎn)單圖與頂點(diǎn)v相關(guān)聯(lián)的邊的數(shù)目，稱(chēng)為該頂點(diǎn)的“度”(書(shū)上稱(chēng)為次)，記為d(v)度數(shù)為奇數(shù)的頂點(diǎn)稱(chēng)為奇點(diǎn)，度數(shù)為偶數(shù)的頂點(diǎn)稱(chēng)為偶點(diǎn)在有向圖中，由頂點(diǎn)指向外的弧的數(shù)目稱(chēng)為正度，記為d+，指向該頂點(diǎn)的弧的數(shù)目稱(chēng)為負(fù)度，記為d–度數(shù)為0的點(diǎn)稱(chēng)為孤立點(diǎn)，度數(shù)為1的點(diǎn)稱(chēng)為懸掛點(diǎn)圖的基本概念(5)與懸掛點(diǎn)連接的邊稱(chēng)為懸掛邊若圖中所有的點(diǎn)都是孤立點(diǎn)，則稱(chēng)為空?qǐng)D定理6.1所有頂點(diǎn)的度數(shù)之和，等于所有邊數(shù)的兩倍原因：每條邊關(guān)聯(lián)兩個(gè)頂點(diǎn)，計(jì)算頂點(diǎn)的度數(shù)時(shí)，每條邊計(jì)算了2次定理6.2圖中奇點(diǎn)的個(gè)數(shù)總是偶數(shù)個(gè)原因：所有頂點(diǎn)的度數(shù)之和是偶數(shù)，偶點(diǎn)的度數(shù)之和也是偶數(shù)，因此，奇點(diǎn)的度數(shù)之和必為偶數(shù)，因此，奇點(diǎn)的個(gè)數(shù)必是偶數(shù)個(gè)圖的基本概念(6)點(diǎn)邊交錯(cuò)序列v0,e1,v1,e2,v2,…,vn-1,en,vn稱(chēng)為鏈。其中v0稱(chēng)為路的起點(diǎn)，vn稱(chēng)為路的終點(diǎn)若v0≠vn，稱(chēng)為開(kāi)鏈；反之，稱(chēng)為閉鏈(對(duì)于無(wú)向圖而言，也稱(chēng)為回路)若鏈中所含的邊均不相同，稱(chēng)為簡(jiǎn)單鏈若鏈中所含的頂點(diǎn)均不相同，稱(chēng)為初等鏈(對(duì)于無(wú)向圖而言，也稱(chēng)為通路)除起點(diǎn)和終點(diǎn)外均不相同的閉鏈，稱(chēng)為圈(對(duì)于無(wú)向圖而言，也稱(chēng)為初等回路)以上概念(除特別標(biāo)注的外)對(duì)無(wú)向圖和有向圖均適用圖的基本概念(7)在有向圖中，點(diǎn)邊交錯(cuò)序列v0,e1,v1,e2,v2,…,vn-1,en,vn(其中ek=(vk-1,vk))稱(chēng)為路若v0≠vn，稱(chēng)為開(kāi)路；反之，稱(chēng)為回路(注意和無(wú)向圖的回路區(qū)分開(kāi)來(lái))若路中所含的邊均不相同，稱(chēng)為簡(jiǎn)單路若路中所含的頂點(diǎn)均不相同，稱(chēng)為初等路除起點(diǎn)和終點(diǎn)外均不相同的回路，稱(chēng)為初等回路(注意和無(wú)向圖的初等回路區(qū)分開(kāi)來(lái))本頁(yè)概念都是針對(duì)有向圖圖的基本概念(8)若一個(gè)圖(無(wú)向圖或有向圖)中任意兩點(diǎn)之間至少有一條初等鏈連接，則稱(chēng)該圖為連通圖，否則稱(chēng)為不連通圖在一個(gè)有向圖中，若任意兩點(diǎn)u和v，u到v和v到u之間都至少有一條初等路連接，則稱(chēng)該圖為強(qiáng)連通圖，否則稱(chēng)為非強(qiáng)連通圖圖的基本概念(9)子圖：設(shè)G1=(V1,E1)，G2=(V2,E2)，若V1V2，E1E2，則稱(chēng)G1是G2的子圖注：生成子圖時(shí)，可以只選頂點(diǎn)不選與該頂點(diǎn)相關(guān)聯(lián)的邊，但不能只選邊不選與該邊相關(guān)聯(lián)的頂點(diǎn)如下圖，右圖是左圖的子圖圖的基本概念(10)如下圖，右圖是左圖的真子圖真子圖：若V1V2，E1E2，稱(chēng)G1是G2的真子圖部分圖：若V1=V2，E1E2，稱(chēng)G1是G2的部分圖圖的基本概念(11)導(dǎo)出子圖：若V1V2，E1={(ui,vj)E2|uiV1,vjV1}，稱(chēng)G1是G2中由V1導(dǎo)出的導(dǎo)出子圖，記作G(V1)如下圖，右圖是左圖的導(dǎo)出子圖圖的基本概念(12)一個(gè)沒(méi)有圈的圖稱(chēng)為無(wú)圈圖或稱(chēng)為林一個(gè)連通的無(wú)圈圖稱(chēng)為樹(shù)一個(gè)林的每個(gè)連通子圖都是一個(gè)樹(shù)定理6.3：關(guān)于樹(shù)的以下描述是等價(jià)的無(wú)圈連通圖(定義)無(wú)圈圖G，q(G)=p(G)-1(定義+對(duì)頂點(diǎn)個(gè)數(shù)用歸納法)連通圖G，q(G)=p(G)-1(定義+對(duì)頂點(diǎn)個(gè)數(shù)用歸納法)無(wú)圈，但增加一條邊可以得到唯一的圈(定義+對(duì)頂點(diǎn)個(gè)數(shù)用歸納法)連通，但去掉一條邊就不連通(反證法)每一對(duì)頂點(diǎn)之間有且僅有一條初等鏈(反證法)圖的基本概念(13)若T是圖G的部分圖，且T是樹(shù)，則稱(chēng)T為G的生成樹(shù)(書(shū)上稱(chēng)為部分樹(shù))圖的存儲(chǔ)方式(1)計(jì)算機(jī)中存儲(chǔ)圖一般采用矩陣存儲(chǔ)常用的存儲(chǔ)方法有兩種鄰接矩陣關(guān)聯(lián)矩陣圖的存儲(chǔ)方式(2)對(duì)于無(wú)向圖，鄰接矩陣存儲(chǔ)方式如下若頂點(diǎn)vi和vj之間沒(méi)有邊，則aij=aji=0若頂點(diǎn)vi和vj之間存在n條邊，則aij=aji=n注：一般i≤jv1v2v3v4v5圖的存儲(chǔ)方式(3)v1v2v3v4v5對(duì)于有向圖，鄰接矩陣存儲(chǔ)方式如下若頂點(diǎn)vi和vj之間沒(méi)有弧，則aij=0若頂點(diǎn)vi和vj之間存在n條弧(vi,vj)，則aij=n注：允許i=j圖的存儲(chǔ)方式(4)對(duì)于無(wú)向圖，關(guān)聯(lián)矩陣存儲(chǔ)方式如下若頂點(diǎn)vi不和邊ej相關(guān)聯(lián)，則bij=0若頂點(diǎn)vi和邊ej相關(guān)聯(lián)，則bij=1v1v2v3v4v5e1e2e3e4e5e6e7e8e9e9關(guān)聯(lián)的頂點(diǎn)個(gè)數(shù)為1，是自環(huán)圖的存儲(chǔ)方式(5)對(duì)于有向圖，關(guān)聯(lián)矩陣存儲(chǔ)方式如下若頂點(diǎn)vi不和弧ej相關(guān)聯(lián)，則bij=0若頂點(diǎn)vi是弧ej的起點(diǎn)，則bij=1若頂點(diǎn)vi是弧ej的終點(diǎn)，則bij=-1若頂點(diǎn)vi既是弧ej的起點(diǎn)又是弧ej的終點(diǎn)，則bij=2v1v2v3v4v5e1e2e3e4e5e6e7e8e9簡(jiǎn)單圖的權(quán)值矩陣(1)對(duì)于賦權(quán)簡(jiǎn)單圖，權(quán)值矩陣存儲(chǔ)方式如下若頂點(diǎn)vi和vj之間沒(méi)有邊，則wij=0若頂點(diǎn)vi和vj之間有邊(vi,vj)，則wij=相應(yīng)邊的權(quán)值注：無(wú)向圖和有向圖均適用，有向圖要注意邊的方向簡(jiǎn)單圖的權(quán)值矩陣(2)v1v2v3v4v5376245v1v2v3v4v5376245最短路線(xiàn)問(wèn)題一般針對(duì)賦權(quán)連通圖(有向圖或無(wú)向圖皆可)，求兩點(diǎn)之間所經(jīng)路線(xiàn)權(quán)值之和為最小的路線(xiàn)求解該問(wèn)題可以采用上一章介紹的動(dòng)態(tài)規(guī)劃的方法該方法適用于無(wú)負(fù)初等回路(指所有邊的權(quán)值之和為負(fù)值的初等回路)的賦權(quán)連通圖(有向圖或無(wú)向圖皆可)；若有負(fù)初等回路，則不存在最短路線(xiàn)該方法需要人工劃分階段，適合人工計(jì)算書(shū)上介紹的三種算法，不需要明確的劃分階段，較為適合計(jì)算機(jī)運(yùn)算狄克斯拉(Dijkstra)算法(1)該算法有兩個(gè)依據(jù)從v1到vn的最短路線(xiàn)也是從vn到v1的最短路線(xiàn)對(duì)于無(wú)向圖必定成立對(duì)于有向圖而言，vn到v1的最短路線(xiàn)是指將圖中弧的方向反過(guò)來(lái)，但權(quán)值不變時(shí)的最短路線(xiàn)以vn為起點(diǎn)，v1為終點(diǎn)應(yīng)用動(dòng)態(tài)規(guī)劃的最優(yōu)性原理第一條依據(jù)保證了按這種方法求得的結(jié)果是從v1到vn的最短路線(xiàn)狄克斯拉(Dijkstra)算法(2)算法步驟已知網(wǎng)絡(luò)的距離矩陣L=(lij)，lij表示vi到vj的弧上的距離權(quán)值令i=1，S1={v1}，S2={v2,v3,…,vn}，令P(v1)=0，T(vj)=∞（vj∈S2）令T(vj)=min{T(vj)，P(vi)+lij|vj∈S2}令vk=min{T(vj)|vj∈S2}，P(vk)=T(vk)若vk=vn，則已經(jīng)找到v1到vn的最短距離P(vk)否則，令i=k，從S2中刪去vi，轉(zhuǎn)上一步狄克斯拉(Dijkstra)算法(3)該算法適用于無(wú)負(fù)初等回路的賦權(quán)連通圖(有向圖或無(wú)向圖皆可)，但算法本身不能判定圖中是否存在負(fù)初等回路因此，該算法一般應(yīng)用于無(wú)負(fù)權(quán)值的賦權(quán)連通有向圖或無(wú)向圖示例(6.1-1)sabcdt5839149543路線(xiàn)圖如下所示，箭頭表示通行方向，線(xiàn)上數(shù)字表示道路長(zhǎng)度，試用Dijkstra算法求s到t的最短路線(xiàn)示例(6.1-2)sabcdt初始值T()第1次P()+lijT()第2次P()+lijT()第3次P()+lijT()第4次P()+lijT()第5次P()+lijT()0∞∞∞∞∞0+50+80+∞0+∞0+∞58∞∞∞5+∞5+35+95+∞8814∞8+∞8+48+∞812∞8+38+9111711+51612345示例(6.1-3)sabcdt5839149543海斯算法(1)該算法有兩個(gè)依據(jù)從v1到vn的最短路線(xiàn)也是從vn到v1的最短路線(xiàn)對(duì)于無(wú)向圖必定成立對(duì)于有向圖而言，vn到v1的最短路線(xiàn)是指將圖中弧的方向反過(guò)來(lái)，但權(quán)值不變時(shí)的最短路線(xiàn)若從vi到vj的最短路線(xiàn)經(jīng)過(guò)vk，則vi到vk、vk到vj的都是相應(yīng)的最優(yōu)路線(xiàn)第一條依據(jù)保證了從vi到vj的最短路線(xiàn)也是從vj到vi的最短路線(xiàn)則根據(jù)動(dòng)態(tài)規(guī)劃最優(yōu)性原理，vk到vj和vk到vi都是相應(yīng)的最優(yōu)路線(xiàn)，由此得到上面的結(jié)論海斯算法(2)算法步驟已知網(wǎng)絡(luò)的距離矩陣L=(lij)，lij表示vi到vj的弧上的距離權(quán)值令dij(0)=lij，i=1～n，j=1～ndij(t)表示從vi到vj的2t步距離當(dāng)dij(m-1)已知時(shí)，令

dij(m)=min{dik(m-1)+dkj(m-1)|k=1～n}當(dāng)對(duì)所有的i,j有dij(m)=dij(m-1)時(shí)，dij(m)是vi到vj的最短距離。否則，若2m-1＜n-1，m=m+1，轉(zhuǎn)上一步；若2m-1≥n-1，說(shuō)明存在負(fù)初等回路，最短路線(xiàn)不存在，算法停止海斯算法(3)該算法可以判斷是否存在負(fù)初等回路，適用于任意權(quán)值的賦權(quán)連通有向圖或無(wú)向圖所得的結(jié)果矩陣中包含了圖中任意兩點(diǎn)之間的最短距離示例(6.2-1)sabcdt5839149543路線(xiàn)圖如下所示，箭頭表示通行方向，線(xiàn)上數(shù)字表示道路長(zhǎng)度，試用海斯算法求s到t的最短路線(xiàn)示例(6.2-2)示例(6.2-3)示例(6.2-4)由于D(3)=D(2)，停止計(jì)算s到t的最短路線(xiàn)長(zhǎng)度為16由D(2)知s到t經(jīng)過(guò)c由D(1)知s到c經(jīng)過(guò)a，c到t經(jīng)過(guò)d則最短路線(xiàn)為sacdtsabcdt5839149543福德(Ford)算法(1)該算法和Dijkstra算法一樣有兩個(gè)依據(jù)從v1到vn的最短路線(xiàn)也是從vn到v1的最短路線(xiàn)對(duì)于無(wú)向圖必定成立對(duì)于有向圖而言，vn到v1的最短路線(xiàn)是指將圖中弧的方向反過(guò)來(lái)，但權(quán)值不變時(shí)的最短路線(xiàn)以vn為起點(diǎn)，v1為終點(diǎn)應(yīng)用動(dòng)態(tài)規(guī)劃的最優(yōu)性原理第一條依據(jù)保證了按這種方法求得的結(jié)果是從v1到vn的最短路線(xiàn)福德(Ford)算法(2)算法步驟已知網(wǎng)絡(luò)的距離矩陣L=(lij)，lij表示vi到vj的弧上的距離權(quán)值令dj(1)=l1j，j=1～ndj(t)表示從v1到vj的步數(shù)不超過(guò)t的最短距離當(dāng)dj(k)已知時(shí)，令dj(k+1)=min{di(k)+lij|i=1～n}當(dāng)對(duì)所有的j有dj(k+1)=dj(k)時(shí)，dj(k)是v1到vj的最短距離。否則，若k＜n-1，k=k+1，轉(zhuǎn)上一步；若k≥n-1，說(shuō)明存在負(fù)初等回路，最短路線(xiàn)不存在，算法停止福德(Ford)算法(3)該算法可以判斷是否存在負(fù)初等回路，適用于任意權(quán)值的賦權(quán)連通有向圖或無(wú)向圖所得的結(jié)果中包含了從v1到其他任意點(diǎn)的最短距離示例(6.3-1)sabcdt5839149543路線(xiàn)圖如下所示，箭頭表示通行方向，線(xiàn)上數(shù)字表示道路長(zhǎng)度，試用Ford算法求s到t的最短路線(xiàn)示例(6.3-2)abcdd示例(6.3-3)由于dj(4)=dj(3)(j=s,a,b,c,d,t)，停止計(jì)算s到t的最短路線(xiàn)長(zhǎng)度為16最短路線(xiàn)為sacdtsabcdt5839149543最小生成樹(shù)問(wèn)題一般針對(duì)賦權(quán)連通圖，求該圖權(quán)值之和為最小的生成樹(shù)求解該問(wèn)題一般有兩種方法破圈法生長(zhǎng)法破圈法求最小生成樹(shù)假設(shè)原圖為賦權(quán)連通圖破圈法依據(jù)樹(shù)的定義給出求最小生成樹(shù)算法破圈法步驟如下在圖中找到一個(gè)圈，進(jìn)入下一步；若無(wú)圈則停止，此時(shí)的圖就是原圖的最小生成樹(shù)查看該圈與其它圈是否有公共邊若沒(méi)有公共邊，在該圈中選權(quán)值最大的邊，去掉該邊；對(duì)新的圖返回上一步若有公共邊，將這些有公共邊的若干個(gè)圈合在一起看作一個(gè)回路，在該回路中選權(quán)值最大的邊，去掉該邊；對(duì)新的圖返回上一步示例(6.4-1)3354726432用破圈法求下圖的最小生成樹(shù)生長(zhǎng)法求最小生成樹(shù)(1)生長(zhǎng)法依據(jù)根據(jù)動(dòng)態(tài)規(guī)劃最優(yōu)性原理，劃分n-1個(gè)階段x1=S1從圖中任選一點(diǎn)vi，令S1={vi}，S2=V-S1，k=1uk為k階段選中的權(quán)值最小的邊(vi,vj)，vi∈S1，vj∈S2xk+1=xk+{uk}+{vj}S1=S1+{(vi,vj)}+{vj}，S2=S2-{vj}xn狀態(tài)結(jié)束此時(shí)，S1就是要求的最小生成樹(shù)的點(diǎn)邊集合，S2是空集生長(zhǎng)法求最小生成樹(shù)(2)假設(shè)原圖為賦權(quán)連通圖生長(zhǎng)法步驟如下從圖中任選一點(diǎn)vi，令S1={vi}，S2=V-S1從S1中的各點(diǎn)到S2中各點(diǎn)的邊中選擇權(quán)值最小的邊(vi,vj)，vi∈S1，vj∈S2令S1=S1+{(vi,vj)}+{vj}，S2=S2-{vj}若S2是空集，則停止，S1就是要求的最小生成樹(shù)的點(diǎn)邊集合；否則轉(zhuǎn)第二步示例(6.5-1)3354726432用生長(zhǎng)法求下圖的最小生成樹(shù)作業(yè)(17)書(shū)上218頁(yè)5-1的(b)補(bǔ)充：3和8之間權(quán)值為13破圈法或生長(zhǎng)法皆可最大流問(wèn)題(1)一般針對(duì)賦權(quán)連通有向圖，每條弧的權(quán)值表示該弧允許流過(guò)的最大流量，每個(gè)頂點(diǎn)的流入量之和等于流出量之和，求圖上兩定點(diǎn)之間允許流過(guò)的最大流量最大流-最小割定理最大流量等于最小割集(容量最小的割集)的容量注：將圖G中頂點(diǎn)集合V分為兩個(gè)集合S1和S2，其中起點(diǎn)vs∈S1、終點(diǎn)vt∈S2，且S1∪S2=V、S1∩S2=，則把集合C={(vi,vj)|vi∈S1,vj∈S2}稱(chēng)為圖G的一個(gè)割集割集中弧的權(quán)值之和稱(chēng)為該割集的容量最大流問(wèn)題(2)利用最大流-最小割定理，福德和富克遜提出了求解最大流問(wèn)題的標(biāo)號(hào)法可行流最大流結(jié)束改變流量是否最大流問(wèn)題(3)標(biāo)號(hào)法相關(guān)概念若弧(vi,vj)上的流量xij=bij，則稱(chēng)該弧為飽和弧，否則稱(chēng)為非飽和弧若弧(vi,vj)上的流量xij=0，則稱(chēng)該弧為零流弧，否則稱(chēng)為非零流弧在一條從vs到vt的點(diǎn)邊交錯(cuò)序列中，與vs到vt方向一致的弧稱(chēng)為正向弧，與vs到vt方向相反的弧稱(chēng)為逆向弧若從vs到vt的某個(gè)點(diǎn)邊交錯(cuò)序列中，正向弧均為非飽和弧，逆向弧均為非零流弧，則稱(chēng)該點(diǎn)邊交錯(cuò)序列為一條流量增廣鏈最大流問(wèn)題(4)流量增廣鏈的作用它是用來(lái)增加正向總流量的使增廣鏈上正向弧的流量增大使增廣鏈上逆向弧的流量減小若找不到，表示不能再增大正向總流量，即當(dāng)前的正向總流量就是最大流量最大流問(wèn)題(5)標(biāo)號(hào)法步驟如下分配vi到vj的初始流xij尋找增廣鏈，若不存在，則已經(jīng)最優(yōu)；否則進(jìn)入下一步調(diào)整。尋找增廣鏈方法如下將vs標(biāo)記上(-,∞)，S1={vs}，S2=V-S1若存在以S1中點(diǎn)為起點(diǎn)、以S2中點(diǎn)為終點(diǎn)的非飽和弧(vi,vj)，則為vj標(biāo)記上(vi+,zj)，zj=min{zi,bij-xij}，S1=S1+{vj}，S2=S2-{vj}若存在以S2中點(diǎn)為起點(diǎn)、以S1中點(diǎn)為終點(diǎn)的非零流弧(vj,vi)，則為vj標(biāo)記上(vi-,zj)，zj=min{zi,xji}，S1=S1+{vj}，S2=S2-{vj}若S1中已包含vt

，則已找到一條增廣鏈，否則轉(zhuǎn)向第二步最大流問(wèn)題(6)調(diào)整流量，方法如下設(shè)vt

上的標(biāo)記為(vk+,zt)，則整個(gè)增廣鏈上最大的調(diào)整量為z=zt由vt

上的標(biāo)記可以得到增廣鏈上的前一個(gè)頂點(diǎn)vk

，依次向前可以找到整個(gè)增廣鏈在增廣鏈上，正向弧流量增加z，逆向弧流量減少z返回第二步繼續(xù)尋找下一個(gè)增廣鏈?zhǔn)纠?6.6-1)(9)(8)(3)(7)(4)(4)(2)(6)(11)711106915543vsvtv2v3v4v5(-,∞)(vs+,7)(v2-,3)(v3+,1)(v3+,3)(v5+,3)用標(biāo)號(hào)法求出從vs到vt的最大流示例(6.6-2)調(diào)整流量，得711106915543vsvtv2v3v4v5(11)(0)(9)(7)(4)(4)(5)(9)(11)(-,∞)(vs+,4)找不到增廣鏈，則當(dāng)前流量20為最優(yōu)最小費(fèi)用-最大流問(wèn)題(1)一般情況下，最大流量是唯一的，而相應(yīng)的每條弧上的流量分布卻是不唯一的如果已知流過(guò)弧(vi,vj)的單位流量要發(fā)生cij的費(fèi)用，要求使得總費(fèi)用為最小的最大流流量分配方案，這種問(wèn)題稱(chēng)為最小費(fèi)用-最大流問(wèn)題可以使用對(duì)偶法解決這個(gè)問(wèn)題最小費(fèi)用-最大流問(wèn)題(2)對(duì)偶法原理對(duì)原圖求出從vs到vt的所有初等路將這些初等路按照單位流量費(fèi)用之和從小到大排序，編號(hào)1,2,3,…,m使第1號(hào)初等路上的流量為最大在余下的允許流量中，使第2號(hào)初等路上的流量為最大在余下的允許流量中，使第3號(hào)初等路上的流量為最大…在余下的允許流量中，使第m號(hào)初等路上的流量為最大此時(shí)，圖中的流量分布即為最小費(fèi)用-最大流在實(shí)際使用時(shí)，要對(duì)原圖求出從vs到vt的所有初等路有一定的難度，容易遺漏最小費(fèi)用-最大流問(wèn)題(3)因此，對(duì)偶法在實(shí)際操作時(shí)求出最大流量，以0流為初始可行流對(duì)原圖求出從vs到vt的單位流量費(fèi)用之和為最小的初等路調(diào)整使得該初等路上的流量為最大，若當(dāng)前可行流的流量等于最大流量，則當(dāng)前可行流就是最小費(fèi)用-最大流，否則進(jìn)入下一步對(duì)當(dāng)前可行流生成擴(kuò)展費(fèi)用圖。在擴(kuò)展費(fèi)用圖中，從原圖的允許流量中去掉當(dāng)前可行流的流量，將圖中某些弧的單位流量費(fèi)用調(diào)整為∞(這些弧的允許流量已經(jīng)減小為0，使得此弧不通)在該擴(kuò)展費(fèi)用圖中，求出新的從vs到vt的單位流量費(fèi)用之和為最小的初等路，轉(zhuǎn)向第三步最小費(fèi)用-最大流問(wèn)題(4)對(duì)偶法步驟用標(biāo)號(hào)法求出最大流量將原圖作為初始擴(kuò)展費(fèi)用圖，以0流作為初始可行流在擴(kuò)展費(fèi)用圖上，用Ford算法求出從vs到vt的單位流量費(fèi)用之和為最小的初等路作為增廣鏈按前面標(biāo)號(hào)法中調(diào)整流量的方法調(diào)整流量，得到一個(gè)新的可行流若當(dāng)前可行流的流量等于最大流量，則當(dāng)前可行流就是最小費(fèi)用-最大流，否則進(jìn)入下一步對(duì)當(dāng)前可行流生成新的擴(kuò)展費(fèi)用圖，轉(zhuǎn)向第三步最小費(fèi)用-最大流問(wèn)題(5)擴(kuò)展費(fèi)用圖的生成在弧(vi,vj)上若xij=0，則原弧不變?nèi)?＜xij＜bij

，則把弧(vi,vj)改造成如下的兩條弧若xij=bij

，則把弧(vi,vj)改造成方向相反的另一條弧vivj(bij-xij,cij)(xij,-cij)vivj(bij,cij)在生成增廣鏈時(shí)用不到反向弧(vj,vi)

，這樣就去掉了當(dāng)前可行流的流量同理，使得弧(vi,vj)不通，將其單位流量費(fèi)用調(diào)整為∞示例(6.7-1)求出從vs到vt的最小費(fèi)用-最大流，圖中弧上數(shù)字含義為(bij,cij)vsvtv2v4v3v5(15,2)(9,6)(3,3)(5,5)(4,9)(7,8)(6,3)(10,1)(11,3)示例(6.7-2)由示例(6.6)，如下圖，已知從vs到vt的最大流量為20vsvtv2v4v3v5(15,2)(9,6)(3,3)(5,5)(4,9)(7,8)(6,3)(10,1)