圖與網(wǎng)絡(luò)西安電子科技大學(xué)經(jīng)濟(jì)管理學(xué)院

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

圖與網(wǎng)絡(luò)

趙瑋主要內(nèi)容：10.1基本概念10.2最短路問(wèn)題（一）Bellman最優(yōu)化原理（二）Dijustra算法（雙括號(hào)法）（三）通信線路布施問(wèn)題（四）設(shè)備更新問(wèn)題10.3最小生成樹（一）基本概念與理論（二）Kruskal算法（加邊法、破圈法）（三）丟邊法（破圈法）主要內(nèi)容：10.4最大流問(wèn)題（一）基本概念（二）雙標(biāo)號(hào)算法10.5最小費(fèi)用最大流（一）基本概念（二）求解算法§10.1基本概念

1圖

def1：一個(gè)無(wú)向圖（簡(jiǎn)稱為圖）G是一個(gè)有序的二元組，記為G=(V,E)。其中V={V1…Vn}稱為G的點(diǎn)集合，E=(eij)稱為G的邊集合，evj為連接VV與Vj的邊。

若N和E均為有限集合，則稱為G為有限圖，否則稱無(wú)限圖。若G中既沒(méi)有有限回路（圈），也沒(méi)有兩條邊連接同一對(duì)點(diǎn)，則稱G為簡(jiǎn)單圖。如右圖之（a），右圖之（b）不是簡(jiǎn)單圖。若G為簡(jiǎn)單圖，且G中每個(gè)點(diǎn)對(duì)之間均有一條邊相連，則稱G為完全圖。如圖（a）是簡(jiǎn)單圖，但不是完全圖。

圖a圖bdef2：一個(gè)有向圖G是一個(gè)有序的二元組，記為G=(V,A)，其中V=(V1V2…Vn)稱為G的點(diǎn)集合，A={aij}稱為G的?。ㄓ邢蜻叄┘?，aij是以Vi指向Vj的一條弧。

|V|=n表示G中節(jié)點(diǎn)個(gè)數(shù)為n，此節(jié)點(diǎn)個(gè)數(shù)n也稱為圖G的階|A|=m表示有向圖G中弧的個(gè)數(shù)為m任一頂點(diǎn)相關(guān)聯(lián)（連接）的邊的數(shù)目稱為該頂點(diǎn)的次數(shù)2連通圖def3：在有向圖G中,一個(gè)點(diǎn)和邊的交替序列{VieijVj…VkeklVl}稱為G中從點(diǎn)Vi到Vl的一條路，記為A，其中Vi為此路A的起點(diǎn)，Vj為路A的終點(diǎn)；若路A的起點(diǎn)與終點(diǎn)重合,則稱A為回路；又若G中點(diǎn)Vi與Vj間存在一條路，則稱點(diǎn)Vi與Vj是連通的；若G中任何二點(diǎn)都是連通的，則稱G為連通圖，或圖G為連通的。在無(wú)向圖中有對(duì)應(yīng)的概念。

有向圖路回路無(wú)向圖鏈圈3子圖

def4：設(shè)有兩個(gè)圖：G1=(V1,E1)，G2=(V2,E2)若有，則稱G1為G2的子圖，記作；若有V1=V2而,則稱圖G1=(V1,E1)是圖G2=(V2,E2)的生成子圖（支撐子圖）。

例：下示圖G1是圖G的子圖，圖G2是圖G的生成子圖。V1V3V2V4V1V2V4V1V3V2V4（a）圖G（b）圖G1（c）圖G24賦權(quán)圖（加權(quán)圖）與網(wǎng)路def5：設(shè)G是一個(gè)圖（或有向圖），若對(duì)G的每一條邊（或?。〆ij都賦予一實(shí)數(shù)ωij，稱其為該邊（弧）的權(quán)，則G連同其他弧上的權(quán)集合稱為一個(gè)賦權(quán)圖，記作G=(V,E,W)或G=(V,A,W)，此中W={ωij}，ωij為對(duì)應(yīng)邊（?。〆ij的權(quán)。若G=(V,E,W)（或(V,A,W)）為賦權(quán)圖，且在G的V中指定一個(gè)發(fā)點(diǎn)（常記為Vs）和一個(gè)收點(diǎn)（記為Vt），其余點(diǎn)稱為中間點(diǎn)，則稱這樣指定了發(fā)點(diǎn)與收點(diǎn)的賦權(quán)圖G為網(wǎng)絡(luò)?！?0.2最短路問(wèn)題def6：設(shè)G=（V,A,W）為一個(gè)賦權(quán)有向圖，Vs為指定發(fā)點(diǎn)，Vt為指定收點(diǎn)，其余為中間點(diǎn)，P為G中以Vs到Vt的一條有向路，則稱為路P的長(zhǎng)度，若有

則稱為G中從Vs到Vt的最短路，為該最短路的長(zhǎng)度（此中F為G中所有從Vs到Vt的全體有向路的集合）。最短路問(wèn)題在企業(yè)廠址上選擇，廠址布局，設(shè)備更新，網(wǎng)絡(luò)線路安裝等工程設(shè)計(jì)與企業(yè)管理中有重要應(yīng)用。

（一）Bellman最優(yōu)化原理1命題1：若P是網(wǎng)絡(luò)G中從Vs到Vt的一條最小路，Vl是P中除Vs與Vt外的任何一個(gè)中間點(diǎn)，則沿P從Vs到Vl的一條路P1亦必是Vs到Vl的最小路。VsV1VlV2VtP2P1證明（反證）：若P1不是從Vs到Vl的最小路，則存在另一條Vs到Vl的路P2使W(P2)<W(P1)，若記路P中從Vl到Vt的路為P3。則有W(P2)+W(P3)<W(P1)+W(P3)=W(P)，此說(shuō)明G中存在一條從Vs沿P2到Vl沿P3再到Vt的更小的一條路，這與P使G中從Vs到Vt的一條最小路矛盾。

2算法思想：設(shè)G中從Vs到Vt的最小路P：Vs…Vj…Vk…Vt，則由上述命題知：P不僅是從Vs到Vt的最小路，而且從Vs到P中任意中間點(diǎn)的最短路也在P上，為此可采用如下求解思路：

⑴

為求得Vs到Vt的最短路，可先求得Vs到中間點(diǎn)的最短路，然后由中間點(diǎn)再逐步過(guò)渡到終點(diǎn)Vt。

⑵

在計(jì)算過(guò)程中，需要把V中“經(jīng)判斷為最短路

P途徑之點(diǎn)i”和“尚未判斷是否為最短路P途徑之點(diǎn)j”區(qū)分開來(lái)，可設(shè)置集合I和J,前者歸入

I，后者歸入J，并令算法初始時(shí)，I中僅包含

Vs，其他點(diǎn)全在J中，然后隨著求解過(guò)程的進(jìn)行，I中的點(diǎn)逐漸增加（相應(yīng)J中的點(diǎn)逐漸減少），直到終點(diǎn)Vt歸入I（相應(yīng)J=φ），此時(shí)迭代結(jié)束。I稱為已標(biāo)號(hào)集合,J稱為未標(biāo)號(hào)集合。

⑶為區(qū)分中間點(diǎn)Vk是否已歸入I中以及逆向求解最短路的方便，可在歸入I中的點(diǎn)Vj上方給予雙標(biāo)號(hào)（lj,Vk），此中l(wèi)j表示從Vs到Vj最短路的距離，而Vk則為從Vs到Vj最短路P中Vj的前一途徑點(diǎn)。⑷為在計(jì)算機(jī)上實(shí)現(xiàn)上述求解思想，還需引入G中各點(diǎn)間一步可達(dá)距離陣D=(dij)n×n，此中

|V|=n⑸

以下介紹的是適用于弧權(quán)為正值的有向網(wǎng)絡(luò)中求最短有向路的Dijkstra算法，又稱雙括號(hào)法。事實(shí)上該算法亦適用于弧權(quán)為負(fù)值的有向網(wǎng)絡(luò)求最短路問(wèn)題。

由圖G建立一步可達(dá)距離陣D=(dij)n×n給V1(Vs)括號(hào)(l1,Vk)=(0,s)給出已標(biāo)號(hào)集合I和未標(biāo)號(hào)集合J的元素對(duì)于給定的I和J，確定集合A={aij|Vi∈I，Vj∈J}計(jì)算距離給Vk括號(hào)(lk,Vh)lk=lh+WhkI=I+{Vk}J=J–{Vk}A=φ或J＝φ從Vt

逆向搜索雙括號(hào)，可得最小路P途徑各點(diǎn)及最小路距離ENDNY（二）Dijkstra算法（雙括號(hào)法）圖一例1（教那材208頁(yè)）求G的最短路炎，圖G形如下形黎。解：利百用上述Dijk鳥stra算法步戶驟可得小表一所廊示求諷解過(guò)程癥，并有牌最短路P：V6V4V3V1，最短距芹離|P|=的2+1滿+5=辜8。512圖（一）表一（站例1期求解過(guò)功程）例2泰求如下G之最小誕路V1V4V2V6V8V5V7333V36666117圖屬二742解表尤二表三蘇（例2蜘求解過(guò)鏟程）由表三謊知V1V8最短路P1：V8V6V2V1最短路P2：V8V6V5V3V2V1最短路長(zhǎng)急|P1|=2+除7+4=宏13|P2|=2+聽3+3+惕1+4=囑1344712332（三）猾通信線光路布設(shè)芬問(wèn)題（賣教材P209）例3.這甲、命乙兩地魚之間的香公路網(wǎng)泥絡(luò)如圖撥三，電訴信公司迷準(zhǔn)備在壘甲、乙腔兩地沿儀公路沿宗線架設(shè)座一光纜聰線，問(wèn)反應(yīng)如何孟架設(shè)此盟線路方歉案，以槍使光纜沿線路架江設(shè)總長(zhǎng)川度最短若？圖猜三解：本例夠之一步可珍達(dá)距離陣陶如G={V醉,E,W熄},V=械{V1V2V3V4V5V6V7}，本例G為無(wú)向歪圖，求茂解過(guò)程佳見表四W=表四循（例3怕求解過(guò)樂(lè)程）①由表四邀可得最短路P：侵V7V6V5V3V1最短距膊離岸|P|=阿10+鄭4+2撥+6=貢22②還可得到沙自V1（甲）到瘋?cè)我恢忻砷g點(diǎn)之殊最短路閥，例如V1V4最短路由士表四可知耀為P14V4V5V3V1|P14|=1寺862410（四）設(shè)循備更新松問(wèn)題（限教材P212）例4.某公司設(shè)壇備管理部喊門欲制定段一個(gè)五年拿期某設(shè)備陪的更新計(jì)驗(yàn)劃，要求黑給出這五葬年中購(gòu)置栽該設(shè)備的未年份及購(gòu)親置新設(shè)備智的使用年字限。在此五頸年中購(gòu)粒置該設(shè)關(guān)備的年寧初價(jià)格沃見表五促，設(shè)備輔使用不雙同年限旅的維護(hù)極費(fèi)見表?yè)瘟Ｄ攴?2345年初價(jià)格1111121213表五（酬單位：萬(wàn)敲元）使用年數(shù)0～11～22～33～44～5年維護(hù)費(fèi)用5681118表六踢（單命位：萬(wàn)僻元/年）解：設(shè)Vi—i年初購(gòu)進(jìn)筑一臺(tái)新設(shè)明備aij—i年初購(gòu)進(jìn)腐之新設(shè)備枝使用到第j年初（j-1年末）ωij—i年初購(gòu)悼進(jìn)之新警設(shè)備使釀?dòng)玫降趈年初（j-1年末）之總費(fèi)洞用根據(jù)表叨五與表路六之有扶關(guān)數(shù)據(jù)終可計(jì)算ωij詳可參見表七貿(mào)；由表七蒙可得W陣如表子八；由襪表八可福得有向圖我四；將是表八可損轉(zhuǎn)換成已一步可饒達(dá)陣如肥表九，求解過(guò)程球見表10工。表七蠅（W計(jì)算過(guò)篩程）表八案費(fèi)普用陣（閥單位：德萬(wàn)元）jiωij圖四勢(shì)（設(shè)燈備更新奪有向圖羅）表墨九表10傲設(shè)備更新拍求解過(guò)程min由表1乳0可知騎最短費(fèi)壇用流（姨相當(dāng)于擱最短路功）P：擇V6V3V1|P|=映53萬(wàn)元V4結(jié)論：公司五年膀期設(shè)備更器新方案有青兩個(gè)：A與B，總費(fèi)用均萍為53萬(wàn)盟元。A方案：齡第1年克初購(gòu)置刃設(shè)備使尺用到第真3年初僑（第2起年末）如，第3愿年初再窯購(gòu)置新云設(shè)備使咐用到第讓5年在末（第每6年初駛）B方案：第拴1年初購(gòu)現(xiàn)置設(shè)備使烈用到第4拿年初（第渠3年末）扶，第4年隔初再購(gòu)置傲新設(shè)備使按用到第5離年末（第慘6年初）§10筐.3矛最夏小生成鹽樹最小生爐成樹在鼓網(wǎng)絡(luò)（臂電信網(wǎng)騎、公路致網(wǎng)等）容設(shè)計(jì)與驢企業(yè)管家理中有存重要應(yīng)甲用。（一）粱基本概脖念與理偏論def栽7：無(wú)圈的好連通圖拍（無(wú)向盡圖）稱疑為樹，論常記為符滿號(hào)T。如圖五今的（a）為樹，（b）有圈，（c）不連通紙，故（b）（c疾）均非樹。V2V1V5V4V6V3V2V1V5V4V6V3V2V1V5V4V6V3（a）（b）（c）圖旱五def加8錯(cuò)：若T是圖G的一個(gè)生坐成子圖而忽且又是一棵樹，則尊稱樹T是圖G的一個(gè)獨(dú)生成樹冷（又稱銅支撐樹）由；又若四樹T=(乏V1,E1)為圖G=(V迅,E,W湊)的一個(gè)生賢成樹，友令闖稱為樹T的權(quán)（或長(zhǎng)度旁），則G中具最小鉛權(quán)的生成葉樹稱為G的最小生益成樹，亦豈即若有則有T*為G的最小生探成樹，此累中F為G的全體生成黑樹的集讓合。Th1：設(shè)T=(炕V,E劣)是|V|≥3的一擾個(gè)無(wú)向衫圖，則誕下列六濫個(gè)關(guān)于薄樹的定邊義是等雙價(jià)的：⑴T連通且恰無(wú)圈⑵T的任何兩巨個(gè)頂點(diǎn)間林均必有一芒條且僅有導(dǎo)一條通路相連⑶T連通且您有n-1條邊，此請(qǐng)中n=|V|⑷T有n-1條邊且無(wú)養(yǎng)圈，此中n=|V|⑸T無(wú)圈，早但在T中任兩個(gè)疫不相鄰的削頂點(diǎn)間添命加一條邊霧，則可犧構(gòu)成一離條回路⑹T連通，購(gòu)但去掉兔任一條拌邊后就司不連通泊，即樹T是連通且綢邊數(shù)最小振的圖（二）Krus第kal算法（挖加邊法佩，破圈崇法）1.汽算法思柔想：①由Th1(餓4)結(jié)論：旦若|V|=n，則樹T有n-1條邊且無(wú)圈②由def港8，最小生成貓樹T*是具有最寸小權(quán)的生薯成樹故可E中各邊按沃權(quán)大小排悲列設(shè)為W1≤W2≤…≤Wm，對(duì)應(yīng)？咳邊依次魂為a1,a2,…am，然后將a1,a2,…依次進(jìn)入著集合S，直到獲府得S的生成樹T為止（樹冰的判斷可收由Th1緊(4)結(jié)論），領(lǐng)則此樹T必為最小生娛成樹。設(shè)G=(V描,A,W擦)，|V|=n，|A|=mS—待生成的販集合i—勺S中進(jìn)入最紛小生成樹茶的邊序號(hào)j—逐個(gè)進(jìn)入S的G的邊序號(hào)ei+1—S中進(jìn)入尋最小生喂成樹的專邊jWjajakl1W1a1a232W2a2a55…………mWmama76表品11對(duì)G中各邊滔按權(quán)大罰小順序弄排列，全不妨設(shè)計(jì)為W1≤W2≤…≤Wm填寫Wj對(duì)應(yīng)的浮各邊aj表11S=φ，i蠻=0央，j=秀1{aj}∪S構(gòu)成回仆路？|S|=n努-1ei+1=ajS={吊ei+1}∪Si=i稍+1腿j劫=j+1j=j+懸1T*=絲式S打印T*ENDYYNN圖根六例5（陜教材P218）某大學(xué)途準(zhǔn)備對(duì)暴其所屬絕的7滲個(gè)學(xué)境院辦公形室計(jì)算遵機(jī)聯(lián)網(wǎng)群．這個(gè)夏網(wǎng)絡(luò)的外可能聯(lián)業(yè)通的途程徑如圖靠七所示饑，圖中V1，…，V7表示7個(gè)灰學(xué)院辦公毒室，邊eij為可能上聯(lián)網(wǎng)的數(shù)途徑。怒邊上所升賦的權(quán)齒數(shù)為這王條路線泳的長(zhǎng)度膜（單位套：百米船）。試錄設(shè)計(jì)一凍局域網(wǎng)蟲既能聯(lián)障結(jié)七個(gè)知學(xué)院辦泊公室，晶又能使亂網(wǎng)絡(luò)線疼路總長(zhǎng)釣度為最臣短。WjajaklT*W1a1a23*W2a2a35*W3a3a27*W4a4a17*W5a5a67*W6a6a37W7a7a56W8a8a57W9a9a43*W10a10a45W11a11a16G={錫V,E用,W}扣,|V|=7,|E|=1皂1W=(ωij)ωij見圖解：依掩據(jù)各邊治權(quán)自小噸到大排霸列建立宗表12深，求解皇過(guò)程見蹄表13橡，由表就13得爸知最小械生成樹T*=央{a1,a2,a3,a4,a5,a9}W(T趣*)=綁1+2權(quán)+3+蒜3+7迅=19圖七表絞12表13誦（鴿例5求懶解過(guò)程氧）例6.遠(yuǎn)利用加啟邊法求圖誰(shuí)八所示的債無(wú)向圖G之最小生順成樹WjajaklT*W1a1a12*W2a2a13*W3a3a45*W4a4a23W5a5a25*W6a6a24W7a7a34W8a8a35解：G={V披,E,V雜}，|V|=5|E|=8表辱14V1V2V5V3V412234442圖瀉八表15丟（例6求底解過(guò)程）（三）或丟邊法繼（破圈含法）1.算牙法原理：丟邊法野與加邊牢法相反怒，加邊娘法是以或不形成訪回路為哀準(zhǔn)則將S=φ逐步加崇邊以形袋成樹，遙而由于扭按邊權(quán)舒愈小愈乞優(yōu)先加補(bǔ)進(jìn)去，沖故為最優(yōu)小生成盜樹，而錘丟邊法福則是S=E以不形成喇回路為準(zhǔn)川則逐步丟坑邊以形成穿樹，由于寒是按邊權(quán)枕愈大愈優(yōu)呢先丟掉，臥故同樣為藥最小生成霸樹。設(shè)G=(V杰,E,W態(tài))，|V|=n暗，|E|=m，S—待生成的持集合（逐窯步丟邊）i—礦S中丟掉邊割的序號(hào)j—餡S中保留活邊的序任號(hào)ei+1—S中丟到亦的邊e1—S中丟到的響邊的全體喪（集合）fj+1—S中保留旱的邊D—扒S中保留邊桂的集合由于邊個(gè)慨?dāng)?shù)為m，樹含邊的貧個(gè)數(shù)為n-1慚，故丟掉（形返成回路蓬）邊的役個(gè)數(shù)為m-(n名-1)=者m-n+宮1，以此為程蝕序出口駝，標(biāo)志拔著最小制生成樹濫形成依次從大醒到小按列認(rèn)同例5表粱12。G=(V貪,E,W趣)，|V|=n，|E|=m，S=E已，i=0綁，j=0鑒，E1=φ,D=φ選S中最大葡權(quán)之邊S中是否首有包含al的一個(gè)回俗路i=i腥+1勁ei=alS=趨S-塑{ei}E1=E1∪{ei}T*=S梨-E1打印T*的邊序列j=j纏+1預(yù)fj=alD=D∪{fi+1}i≥m-n-槽1ENDNNYY圖擠九例6.脹（同建例5）餡用丟邊拴法求解求解過(guò)瘋程見表督16，冬由于m-n+域1=11之-(7-助1)=5故i=5時(shí)程序占終止，梳由表知T*=S庸-{e1~e5}={京a1,a2,a3,a4,a5,a9}與前加故邊法求犧解相同，詳溉可參考教比材P218的六個(gè)圖錢。表16危（例6孫求解價(jià)引格）5=i=m范-n+殲1§10.4結(jié)最大流糠問(wèn)題由前知，瘡一個(gè)指定蒙了收點(diǎn)和籃發(fā)點(diǎn)的賦雅權(quán)圖G稱為網(wǎng)絡(luò)保，在網(wǎng)絡(luò)響設(shè)計(jì)中研罵究網(wǎng)絡(luò)的蓮流量具有艱現(xiàn)實(shí)意義易，如交通初網(wǎng)絡(luò)的車傷流流量，倘通信網(wǎng)絡(luò)昂中的話務(wù)忠流量，金陪融網(wǎng)絡(luò)中胡的現(xiàn)金流墾量，控制騰網(wǎng)絡(luò)中的洽信息流量殿，供電網(wǎng)杯絡(luò)中的電罷流流量等叛。人們也拉常常希望識(shí)知道在既圾定網(wǎng)絡(luò)中懇能允許通重過(guò)的最大深流量，以傷便對(duì)該網(wǎng)忘絡(luò)的利用舊程序作出脈評(píng)價(jià)，這或就是所謂旅的網(wǎng)絡(luò)最翅大流問(wèn)題跨。求解方纏法有雙標(biāo)吼號(hào)法，對(duì)播偶圖法等件。1．網(wǎng)絡(luò)賭中弧的永容量與牲流量def9：對(duì)于鏡一個(gè)指趁定收、肥發(fā)點(diǎn)的魯賦權(quán)有棵向（無(wú)雪向）圖沿或網(wǎng)絡(luò)N＝（V，A，C），弧aij萬(wàn)∈A的最大允認(rèn)許通過(guò)能特力稱為該矮弧的容量犁，記為cij（cij≥0），全褲體cij構(gòu)成之集好合記為C；而通過(guò)遺邊aij的實(shí)際勸流量成石為流量零，記為fij，故有0≤fij≤cij。顯然懲若fij≥cij則網(wǎng)絡(luò)N在aij邊將發(fā)生鍵堵塞現(xiàn)象寇，這是人冊(cè)們希望能殼避免的現(xiàn)雅象。（一）汽基本概遼念2．可行秤流與最洲大流def想10：設(shè)有網(wǎng)節(jié)絡(luò)N＝（V，A，C），稱f={撈fij∣aij∈A}為網(wǎng)絡(luò)N上的流夏函數(shù)，捆簡(jiǎn)稱網(wǎng)絡(luò)流；滿傳足如下條秧件的網(wǎng)絡(luò)帆流稱為可脖行流，其中v（f）為網(wǎng)找絡(luò)N可行流拌的總流蛙量（凈晚流入量美）。（1）容量限范制條件：（2）流量守昆恒條件：說(shuō)明：茫進(jìn)入節(jié)第點(diǎn)vj的流量筑＝自節(jié)訴點(diǎn)vj流出的流找量；fij≡0之零流亦蒸滿足上述規(guī)條件，故菜零流以為秤可行流。3．順向弧湊、逆向弧傳與可增路def1內(nèi)1：設(shè)f是網(wǎng)絡(luò)N的一可行依流，P是N中從vs到vt的一條路嗽，對(duì)于路P途經(jīng)的各帶弧，若弧叼的方向與潛路的方向孝相同，則偏稱該弧為勸順向弧，衣若弧的方師向與路的綱方向相反待，則稱該執(zhí)弧為逆向權(quán)弧。若在烘路P的一切領(lǐng)順向弧待（vi，vj）上有fij＜cij，在路P的一切登逆向弧證（vj，vi）上有fji＞0，則稱潛路P是一條關(guān)乓于f的可增蒜路。說(shuō)明：（1）由def鬼11得知：若濕在路P中，存棚在一條艷順向弧當(dāng)（vi，vj）有fij＝cij（此時(shí)搭稱弧為盲飽和弧化），或享者在路P中存在拔一條逆臺(tái)向弧（vj，vi）有fji＝0，則稱路P為不可增縮慧路；（2）在圖10所示的網(wǎng)價(jià)絡(luò)N中有一堂可行流f={fij∣aij∈A}，用藍(lán)俗字標(biāo)記仔，紅字倉(cāng)標(biāo)記各亭弧的容往量cij。表17給出了畜四條從v1到v7的路是否稍可增路的慌判別理由哪。（此f滿足流家量守恒弟條件與針容量限胳制條件截，如圖10表17jv1到v7的路可增路？理由1v1v2v5v7√順向弧有fij＜cij2v1v2v5v3v6v7√順向弧fij＜cij逆向弧有f35＞03v1v4v7×順向弧有f47＝c474v1v2v3v4v7×順向弧有f23＝c23，f47＝c47（3）可增路腔的內(nèi)涵可梨通過(guò)下例額得知在圖10之可行流f中，對(duì)于絹路v1v2v5v3v6v7途經(jīng)的希各弧中舊，若f12，f23增加一個(gè)圈單位流量硬，f35減少一訴個(gè)單位址流量，躁利用流錫量守恒境條件，饅可得一澤個(gè)如圖11的新的可蹦行流桃，并有v（）織=10＞9=v（f）。圖11由上可知知在def1木1中可增路翠要求順向設(shè)弧fij＜cij之條件汗，實(shí)際額上說(shuō)明落沿該弧煙（vi，vj）還可提高流孤量△ij＝cij－fij＞0，另一方蠟面，為提高流量v（f）還要求幻玉該路的逆售向弧降低揉流量，而fji＞0正說(shuō)明了侵該逆向弧存可降低fji個(gè)單位林。1．算法撕思想（避見圖12）給定N＝{V，A，C}，任取一可行流f＝{fij}，若無(wú)可行流，可取零流。l＝1在f中任取一可增路pl利用標(biāo)號(hào)規(guī)則與調(diào)整規(guī)則對(duì)沿著路p的各弧作最大可能調(diào)整是否對(duì)N中所有路均作調(diào)整打印經(jīng)調(diào)整后的最大流f*及最大流量v（f*）取N的一條新可增路pll＝l＋1END圖12（二）雙冊(cè)標(biāo)號(hào)算法尋找一可增路pl，l＝1vs標(biāo)號(hào)（s，∞），沿pl尋找vs的下一相鄰節(jié)點(diǎn)vj按標(biāo)號(hào)規(guī)則對(duì)vj進(jìn)行雙標(biāo)號(hào)（vj，l（vj））

vs＝vt沿pl從收點(diǎn)vt開始反向搜索途經(jīng)各弧，按調(diào)整規(guī)則作流量調(diào)整抹去pl上各點(diǎn)之雙標(biāo)號(hào)，從而由原可行流f調(diào)整為新可行流f1，并有v（f）＜v（f1）是否還有新的可增路打印并輸出經(jīng)調(diào)整后的最大流f*＝{fij∣aij∈A}，最大流量v（f*）結(jié)束l＝l＋1取N的新的可增路plj＝k，i＝j(luò)沿pl尋找vj的相鄰的一點(diǎn)vk圖13NYYN2．調(diào)整步家驟（見兄圖13）3．標(biāo)號(hào)棟與調(diào)整谷規(guī)則（1）標(biāo)號(hào)規(guī)拌則：1o若（vi，vj）為順撈向弧，伐且fij<cij，則給vj標(biāo)號(hào)（vi＋，l（vj）），膽其中l(wèi)（vj）＝min（l（vi），cij－fij）；2o若（vi，vj）為逆席向弧，處且fji>0，則給vj標(biāo)號(hào)（vi－，l（vj）），其獸中l(wèi)（vj）＝min（l（vi），fji）；3o若（vi，vj）為順克向弧但fij＝cij或（vi，vj）為逆向弧圍但fji＝0，此時(shí)轟沿該弧誓的路線坑停止標(biāo)譜號(hào)。（2）調(diào)整規(guī)棉則：1o若（vi，vj）為順絲式向弧，改則對(duì)pl路徑的順錦向弧作調(diào)叼整，其調(diào)嘉整量△ij＝fij＋l（v）；2o若（vi，vj）為逆向旬弧，則對(duì)pl途經(jīng)的逆爭(zhēng)向弧作調(diào)丘整，其調(diào)鵝整量△ji＝fji－l（v）；3oG中不在pl路上的各饑弧不作調(diào)扒整。4．例7（教材P219）某石油火公司擁閘有一管查道網(wǎng)絡(luò)敵，使用旦此管道妙網(wǎng)絡(luò)可她將石油助從采地v1運(yùn)往銷地v7，由于掀各地的績(jī)地質(zhì)條旅件等不老同，因并而其管彎道直徑聽有所不舒同，從戒而使各哥弧的容揉量cij（單位黃：萬(wàn)加押侖/小時(shí)）架不同，模對(duì)于如嶼圖14所示的宏管道網(wǎng)藥絡(luò)N＝（V，A，C），問(wèn)每顯小時(shí)從v1往v7能運(yùn)送多敏少加侖石洗油？圖14解1：若設(shè)弧折（vi，vj）上的流屯量為fij，網(wǎng)絡(luò)N上總流臭量為F，則可建士立如下LP：max云F＝f12＋f14f12＝f23＋f25f14＝f43＋f46＋f47f23＋f43＝f35＋f36s．t頓f25＋f35＝f57f36＋f46＝f67f47＋f57＋f67＝f12＋f14fij≤ciji＝1～6，j＝1～7fij≥0修i＝1～6，j＝1～7v1v2v3v4v5v6v7v1v2v3v4v5v6v70606000002030000002200030032000000500000050000000C陣?yán)脝渭冎眯畏山廨x得最大流觀：f*＝{f12＝5，f14＝5，f23＝2，f25＝3，f43＝2，f46＝1，f47＝2，f35＝2，f36＝2，f57＝5，f67＝3，v（f*）＝10}解2：（采勝用雙標(biāo)與號(hào)法求案最大流帥）求解中尋伴找了五條蟲可增路，包其標(biāo)號(hào)過(guò)播程與增流岔過(guò)程見表18，表18中各可竿增路及丹其流量防調(diào)整過(guò)忠程見圖15。求解結(jié)在果與解1相同。圖15表18（例7求解過(guò)五程）l可增路pl第二個(gè)標(biāo)號(hào)l（vj）可調(diào)整量l（vt）標(biāo)號(hào)圖調(diào)整圖網(wǎng)絡(luò)流量v（f）1v1v4v7l（v4）＝6，l（v7）＝22（a）（b）22v1v2v3v5v7l（v2）＝6，l（v3）＝2l（v5）＝2，l（v7）＝22（c）（d）43v1v4v6v7l（v4）＝4，l（v6）＝1l（v7）＝21（e）（f）54v1v2v5v7l（v2）＝4，l（v5）＝3l（v7）＝33（g）（h）85v1v4v3v6v7l（v4）＝3，l（v3）＝3l（v6）＝2，l（v7）＝22（i）（j）10已無(wú)可勺增路END§10.5最小費(fèi)用卸最大流在很多網(wǎng)軋絡(luò)（電信護(hù)網(wǎng)絡(luò)、運(yùn)明輸網(wǎng)絡(luò)、按計(jì)算機(jī)網(wǎng)過(guò)絡(luò)）的分侄析與設(shè)計(jì)肺問(wèn)題中，渠人們除關(guān)疏心網(wǎng)絡(luò)的班系統(tǒng)容量膀外還要考攔慮費(fèi)用問(wèn)懂題，以便特建立一個(gè)域高效、低撥耗的網(wǎng)絡(luò)參系統(tǒng)。這毯就是最小膏費(fèi)用最大題流問(wèn)題的存研究。def1調(diào)2：設(shè)網(wǎng)絡(luò)N＝｛V,勸A｝，除標(biāo)對(duì)每一炒弧a∈A規(guī)定了抓其容量c(a)外，還給載定一個(gè)數(shù)b(a)≥0稱為弧a的單位流運(yùn)量費(fèi)用，云即有網(wǎng)絡(luò)N＝｛V,羅A,側(cè)c,候b｝稱其為辜帶費(fèi)用（芬代價(jià)）的歪網(wǎng)絡(luò)。設(shè)f是N上的一閉個(gè)可行證流（從vs到vt），稱蓮為可君行流f的費(fèi)用蒜。將N上所有流戀量等于v0的可行痕流中費(fèi)春用最小招的可行脆流f稱為流木量為v0的最小費(fèi)浸用流，進(jìn)嫩一步當(dāng)v0又是N中最大流斃的流量時(shí)毀，則稱此f為最小費(fèi)督用最大流術(shù)。（一）基寨本概念例8某石油翅公司管儲(chǔ)道網(wǎng)，逗由于輸桃油管道坊的長(zhǎng)短竹不一，霞故對(duì)于黎不同的杯地段（施路徑）窮有不同箱的容量岡限制cij之外，還閃有不同的蘆單位流量夸費(fèi)用bij，該cij的單位為楚萬(wàn)加侖/小時(shí)，bij的單位為如百元/萬(wàn)加侖，房誠(chéng)管道網(wǎng)絡(luò)轉(zhuǎn)如圖16所示，尺圖中括銜號(hào)內(nèi)的遷數(shù)字表伸示（cij，bij）。解1：設(shè)fij表示aij上實(shí)際寧流量，遼則由定趨義12可建立蹦如下LPs.tmax總費(fèi)用b(f)竿=145此解與例7的解顯然核不同，它精是在考慮庭了費(fèi)用目漲標(biāo)后的結(jié)鄰果。（二）些求解算波法算法原清理：最幣小費(fèi)用歇最大流蒸之算法籌有多種舒，以下伙介紹一稻種比較抵易理解著的算法免。定理3：設(shè)f是流量良為v0的最小插費(fèi)用流皆，p是關(guān)于f的可增路蜂中費(fèi)用最孟小的可增希路?？稍霰侨萘繛棣膭t沿p增容δ后所得欠到的可詳行流鐮即騎為胡的最臺(tái)小費(fèi)用胖流。若將N中弧aij的單位費(fèi)堵用bij作為該享弧的弧冤長(zhǎng)，則棍上述定凡理中的癢“可增俘路中費(fèi)磨用最小眾”可理閣解為“踩可增容蜜的最短腦路”。冊(cè)（∵此圓中最短滲的含義殊即為路容徑各弧侍的費(fèi)用躬和最小耍）利用上述非定理可得狀如下算法鋒步驟。圖172.算法步套驟表19l關(guān)于fl－1的可增容最短路pl最短路長(zhǎng)︱pl︱可調(diào)容量l（vt）系統(tǒng)容量v（f）總費(fèi)用1v1v4v6v71011102v1v4v71123323v1v4v3v6v71225564v1v4v3v5v71616725v1v2v5v71739123