圖與網(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最小生成樹(shù)（一）基本概念與理論（二）Kruskal算法（加邊法、破圈法）（三）丟邊法（破圈法）主要內(nèi)容：10.4最大流問(wèn)題（一）基本概念（二）雙標(biāo)號(hào)算法10.5最小費(fèi)用最大流（一）基本概念（二）求解算法§10.1基本概念

1圖

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

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

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

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

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

def4：設(shè)有兩個(gè)圖：G1=(V1,E1)，G2=(V2,E2)若有，則稱(chēng)G1為G2的子圖，記作；若有V1=V2而,則稱(chēng)圖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è)個(gè)圖（（或有有向圖圖），，若對(duì)對(duì)G的每一一條邊邊（或或?。〆ij都賦予予一實(shí)實(shí)數(shù)ωij，稱(chēng)其為為該邊邊（弧弧）的的權(quán)，，則G連同其其他弧弧上的的權(quán)集集合稱(chēng)稱(chēng)為一一個(gè)賦賦權(quán)圖圖，記記作G=(V,E,W)或G=(V,A,W)，，此中W={ωij}，ωωij為對(duì)應(yīng)應(yīng)邊（（?。〆ij的權(quán)。。若G=(V,E,W)（（或(V,A,W)））為賦權(quán)權(quán)圖，，且在在G的V中指定定一個(gè)個(gè)發(fā)點(diǎn)點(diǎn)（常常記為為Vs）和一個(gè)個(gè)收點(diǎn)點(diǎn)（記記為Vt），其余點(diǎn)點(diǎn)稱(chēng)為為中間間點(diǎn)，，則稱(chēng)稱(chēng)這樣樣指定定了發(fā)發(fā)點(diǎn)與與收點(diǎn)點(diǎn)的賦賦權(quán)圖圖G為網(wǎng)絡(luò)絡(luò)?！?0.2最最短路路問(wèn)題題def6：設(shè)G=（V,A,W）為一個(gè)個(gè)賦權(quán)權(quán)有向向圖，，Vs為指定定發(fā)點(diǎn)點(diǎn)，Vt為指定定收點(diǎn)點(diǎn)，其其余為為中間間點(diǎn)，，P為G中以Vs到Vt的一條條有向向路，，則稱(chēng)稱(chēng)為路P的長(zhǎng)度度，若若有則稱(chēng)為為G中從Vs到Vt的最短路，，為為該該最短短路的的長(zhǎng)度度（此此中F為G中所有從從Vs到Vt的全體體有向向路的的集合合）。。最短路路問(wèn)題題在企企業(yè)廠廠址上上選擇擇，廠廠址布布局，設(shè)設(shè)備更更新，，網(wǎng)絡(luò)絡(luò)線路路安裝裝等工工程設(shè)設(shè)計(jì)與與企業(yè)管管理中中有重重要應(yīng)應(yīng)用。。（一））Bellman最最優(yōu)化化原理理1命命題1：若若P是網(wǎng)絡(luò)絡(luò)G中從Vs到Vt的一條條最小小路，，Vl是P中除Vs與Vt外的任任何一一個(gè)中中間點(diǎn)點(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)點(diǎn)再逐逐步過(guò)過(guò)渡到到終點(diǎn)點(diǎn)Vt。⑵在計(jì)算算過(guò)程程中，，需要要把V中“經(jīng)經(jīng)判斷斷為最最短路路P途徑之之點(diǎn)i”和“尚尚未判判斷是是否為為最短短路P途徑之點(diǎn)j”區(qū)分開(kāi)開(kāi)來(lái)，，可設(shè)設(shè)置集集合I和J,前者歸歸入I，后者歸歸入J，并令算算法初初始時(shí)時(shí)，I中僅包包含Vs，其他點(diǎn)點(diǎn)全在在J中，然然后隨隨著求求解過(guò)過(guò)程的的進(jìn)行，I中的點(diǎn)點(diǎn)逐漸漸增加加（相相應(yīng)J中的點(diǎn)點(diǎn)逐漸漸減少），，直到到終點(diǎn)點(diǎn)Vt歸入I（相應(yīng)J=φ），，此時(shí)迭代結(jié)結(jié)束。。I稱(chēng)為已已標(biāo)號(hào)號(hào)集合合,J稱(chēng)為未未標(biāo)號(hào)號(hào)集合合。⑶為為區(qū)分分中間間點(diǎn)Vk是否已已歸入入I中以及及逆向向求解解最短短路的的方便便，可可在歸歸入I中的點(diǎn)點(diǎn)Vj上方給給予雙雙標(biāo)號(hào)號(hào)（lj,Vk），此中l(wèi)j表示從從Vs到Vj最短路路的距距離，，而Vk則為從從Vs到Vj最短路路P中Vj的前前一一途途徑徑點(diǎn)點(diǎn)。。⑷為在計(jì)計(jì)算算機(jī)機(jī)上上實(shí)實(shí)現(xiàn)現(xiàn)上上述述求求解解思思想想，，還還需需引引入入G中各各點(diǎn)點(diǎn)間間一一步步可可達(dá)達(dá)距距離離陣陣D=(dij)n××n，此中中|V|=n⑸以下下介介紹紹的的是是適適用用于于弧弧權(quán)權(quán)為為正正值值的的有有向向網(wǎng)網(wǎng)絡(luò)絡(luò)中中求求最最短短有有向向路路的的Dijkstra算法法，，又又稱(chēng)稱(chēng)雙雙括括號(hào)號(hào)法法。。事事實(shí)實(shí)上上該該算算法法亦亦適適用用于于弧弧權(quán)權(quán)為為負(fù)負(fù)值值的的有有向向網(wǎng)網(wǎng)絡(luò)絡(luò)求求最最短短路路問(wèn)問(wèn)題題。。由圖圖G建立立一一步步可可達(dá)達(dá)距距離離陣陣D=(dij)n××n給V1(Vs)括號(hào)號(hào)(l1,Vk)=(0,s)給出出已已標(biāo)標(biāo)號(hào)號(hào)集集合合I和未未標(biāo)標(biāo)號(hào)號(hào)集集合合J的元元素素對(duì)于于給給定定的的I和J，，確定定集集合合A={aij|Vi∈I，，Vj∈J}計(jì)算算距距離離給Vk括號(hào)號(hào)(lk,Vh)lk=lh+WhkI=I+{Vk}J=J––{Vk}A=φφ或J＝＝φφ從Vt逆向向搜搜索索雙雙括括號(hào)號(hào)，，可可得得最最小小路路P途徑徑各各點(diǎn)點(diǎn)及及最最小小路路距距離離ENDNY（二二））Dijkstra算法法（（雙雙括括號(hào)號(hào)法法））圖一一例1（（教教材材208頁(yè)））求求G的最最短短路路，，圖G形如如下下形形。。解：：利利用用上上述述Dijkstra算法法步步驟驟可可得得表表一一所所示示求求解解過(guò)過(guò)程程，，并并有有最最短短路路P：：V6V4V3V1，最短短距距離離|P|=2+1+5=8。。512圖（（一一））表一一（（例例1求求解解過(guò)過(guò)程程）例2求求如如下下G之最最小小路路V1V4V2V6V8V5V7333V36666117圖二二742解表二二表三三（（例例2求求解解過(guò)過(guò)程程））由表表三三知知V1V8最短短路路P1：V8V6V2V1最短短路路P2：V8V6V5V3V2V1最短短路路長(zhǎng)長(zhǎng)|P1|=2+7+4=13|P2|=2+3+3+1+4=1344712332（三三））通通信信線線路路布布設(shè)設(shè)問(wèn)問(wèn)題題（（教教材材P209）例3.甲甲、、乙乙兩兩地地之之間間的的公公路路網(wǎng)網(wǎng)絡(luò)絡(luò)如如圖圖三三，，電電信信公公司司準(zhǔn)準(zhǔn)備備在在甲甲、、乙乙兩兩地地沿沿公公路路沿沿線線架架設(shè)設(shè)一一光光纜纜線線，，問(wèn)問(wèn)應(yīng)應(yīng)如如何何架架設(shè)設(shè)此此線線路路方方案案，，以以使使光光纜纜線線路路架架設(shè)設(shè)總總長(zhǎng)長(zhǎng)度度最最短短？？圖三三解：：本本例例之之一一步步可可達(dá)達(dá)距距離離陣陣如如G={V,E,W},V={V1V2V3V4V5V6V7}，本例G為無(wú)向圖圖，求解解過(guò)程見(jiàn)見(jiàn)表四W=表四（（例3求求解過(guò)程程）①由表四可可得最短路P：V7V6V5V3V1最短距離離|P|=10+4+2+6=22②還可得到到自V1（甲）到任任一中間間點(diǎn)之最最短路，，例如V1V4最短路由由表四可可知為P14V4V5V3V1|P14|=1862410（四）設(shè)備備更新問(wèn)問(wèn)題（教教材P212）例4.某公司設(shè)設(shè)備管理理部門(mén)欲欲制定一一個(gè)五年年期某設(shè)設(shè)備的更更新計(jì)劃劃，要求求給出這這五年中中購(gòu)置該該設(shè)備的的年份及及購(gòu)置新新設(shè)備的的使用年年限。在此五年年中購(gòu)置置該設(shè)備備的年初初價(jià)格見(jiàn)見(jiàn)表五，，設(shè)備使使用不同同年限的的維護(hù)費(fèi)費(fèi)見(jiàn)表六六。年份12345年初價(jià)格1111121213表五（（單位：：萬(wàn)元））使用年數(shù)0～11～22～33～44～5年維護(hù)費(fèi)用5681118表六（（單位位：萬(wàn)元元/年）解：設(shè)Vi—i年初購(gòu)進(jìn)進(jìn)一臺(tái)新新設(shè)備aij—i年初購(gòu)進(jìn)進(jìn)之新設(shè)設(shè)備使用用到第j年初（j-1年末）ωij—i年初購(gòu)進(jìn)進(jìn)之新設(shè)設(shè)備使用用到第j年初（j-1年末）之總費(fèi)用用根據(jù)表五五與表六六之有關(guān)關(guān)數(shù)據(jù)可可計(jì)算ωij詳可參見(jiàn)表七七；由表表七可得得W陣如表八八；由表表八可得得有向圖四四；將表表八可轉(zhuǎn)轉(zhuǎn)換成一一步可達(dá)達(dá)陣如表表九，求解過(guò)程程見(jiàn)表10。表七（（W計(jì)算過(guò)程程）表八費(fèi)費(fèi)用用陣（單單位：萬(wàn)萬(wàn)元）jiωij圖四（（設(shè)備備更新有有向圖））表九九表10設(shè)設(shè)備備更新求求解過(guò)程程min由表10可知最最短費(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è)設(shè)備使用用到第3年初（（第2年年末），，第3年年初再購(gòu)購(gòu)置新設(shè)設(shè)備使用用到第5年末末（第6年初））B方案：第第1年初初購(gòu)置設(shè)設(shè)備使用用到第4年初（（第3年年末），，第4年年初再購(gòu)購(gòu)置新設(shè)設(shè)備使用用到第5年末（（第6年年初）§10.3最最小小生成樹(shù)樹(shù)最小生成成樹(shù)在網(wǎng)網(wǎng)絡(luò)（電電信網(wǎng)、、公路網(wǎng)網(wǎng)等）設(shè)設(shè)計(jì)與企企業(yè)管理理中有重重要應(yīng)用用。（一）基基本概念念與理論論def7：無(wú)圈的連連通圖（（無(wú)向圖圖）稱(chēng)為為樹(shù)，常常記為符號(hào)號(hào)T。如圖五的的（a）為樹(shù)，（（b）有圈，（c）不連通，，故（b）（c）均非樹(shù)。。V2V1V5V4V6V3V2V1V5V4V6V3V2V1V5V4V6V3（a）（b）（c）圖五五def8：若T是圖G的一個(gè)生生成子圖圖而且又又是一棵樹(shù)，則則稱(chēng)樹(shù)T是圖G的一個(gè)生生成樹(shù)（（又稱(chēng)支支撐樹(shù)）；；又若樹(shù)樹(shù)T=(V1,E1)為圖G=(V,E,W)的一個(gè)生成成樹(shù)，令令稱(chēng)稱(chēng)為樹(shù)T的權(quán)（或長(zhǎng)度度），則則G中具最小小權(quán)的生生成樹(shù)稱(chēng)稱(chēng)為G的最小生生成樹(shù)，，亦即若若有則有T*為G的最小生生成樹(shù)，，此中F為G的全體生成樹(shù)樹(shù)的集合合。Th1：：設(shè)T=(V,E)是|V|≥3的一個(gè)個(gè)無(wú)向圖圖，則下下列六個(gè)個(gè)關(guān)于樹(shù)樹(shù)的定義義是等價(jià)價(jià)的：⑴T連通且無(wú)無(wú)圈⑵T的任何兩兩個(gè)頂點(diǎn)點(diǎn)間均必必有一條條且僅有有一條通通路相連⑶T連通且有有n-1條邊，此此中n=|V|⑷T有n-1條邊且無(wú)無(wú)圈，此中n=|V|⑸T無(wú)圈，但但在T中任兩個(gè)個(gè)不相鄰鄰的頂點(diǎn)點(diǎn)間添加加一條邊，，則可構(gòu)構(gòu)成一條條回路⑹T連通，，但去去掉任任一條條邊后后就不不連通通，即即樹(shù)T是連通通且邊邊數(shù)最最小的的圖（二））Kruskal算法（（加邊邊法，，破圈圈法））1.算算法法思想想：①由Th1(4)結(jié)論：：若|V|=n，則樹(shù)T有n-1條邊且且無(wú)圈②由def8，最小生生成樹(shù)樹(shù)T*是具有有最小小權(quán)的的生成成樹(shù)故可E中各邊邊按權(quán)權(quán)大小小排列列設(shè)為為W1≤W2≤…≤Wm，對(duì)應(yīng)？？邊依依次為為a1,a2,…am，然后將將a1,a2,…依次進(jìn)進(jìn)入集集合S，直到獲獲得S的生成成樹(shù)T為止（（樹(shù)的的判斷斷可由由Th1(4)結(jié)論）），則則此樹(shù)樹(shù)T必為最小小生成成樹(shù)。。設(shè)G=(V,A,W)，|V|=n，|A|=mS—待生成成的集集合i——S中進(jìn)入入最小小生成成樹(shù)的的邊序序號(hào)j——逐個(gè)進(jìn)進(jìn)入S的G的邊序序號(hào)ei+1—S中進(jìn)入入最小小生成成樹(shù)的的邊jWjajakl1W1a1a232W2a2a55…………mWmama76表11對(duì)G中各邊邊按權(quán)權(quán)大小小順序序排列列，不不妨設(shè)設(shè)為W1≤W2≤…≤Wm填寫(xiě)Wj對(duì)應(yīng)的的各邊邊aj表11S=φ，i=0，，j=1{aj}∪S構(gòu)成回回路？？|S|=n-1ei+1=ajS={ei+1}∪Si=i+1j=j+1j=j+1T*=S打印T*ENDYYNN圖六六例5（（教材材P218）某大學(xué)準(zhǔn)備備對(duì)其所屬屬的7個(gè)個(gè)學(xué)院辦辦公室計(jì)算算機(jī)聯(lián)網(wǎng)．．這個(gè)網(wǎng)絡(luò)絡(luò)的可能聯(lián)聯(lián)通的途徑徑如圖七所所示，圖中中V1，…，V7表示7個(gè)學(xué)學(xué)院辦公室室，邊eij為可能聯(lián)網(wǎng)網(wǎng)的途徑。。邊上所賦賦的權(quán)數(shù)為為這條路線線的長(zhǎng)度（（單位：百百米）。試試設(shè)計(jì)一局局域網(wǎng)既能能聯(lián)結(jié)七個(gè)個(gè)學(xué)院辦公公室，又能能使網(wǎng)絡(luò)線線路總長(zhǎng)度度為最短。。WjajaklT*W1a1a23*W2a2a35*W3a3a27*W4a4a17*W5a5a67*W6a6a37W7a7a56W8a8a57W9a9a43*W10a10a45W11a11a16G={V,E,W},|V|=7,|E|=11W=(ωij)ωij見(jiàn)圖解：依據(jù)各各邊權(quán)自小小到大排列列建立表12，求解解過(guò)程見(jiàn)表表13，由由表13得得知最小生生成樹(shù)T*={a1,a2,a3,a4,a5,a9}W(T*)=1+2+3+3+7=19圖七表12表13（（例5求求解過(guò)程））例6.利利用加邊邊法求圖八八所示的無(wú)無(wú)向圖G之最小生成成樹(shù)WjajaklT*W1a1a12*W2a2a13*W3a3a45*W4a4a23W5a5a25*W6a6a24W7a7a34W8a8a35解：G={V,E,V}，|V|=5|E|=8表14V1V2V5V3V412234442圖八八表15（（例6求解解過(guò)程）（三）丟邊邊法（破圈圈法）1.算法法原理：丟邊法與加加邊法相反反，加邊法法是以不形形成回路為為準(zhǔn)則將S=φ逐步加邊以以形成樹(shù)，，而由于按按邊權(quán)愈小小愈優(yōu)先加加進(jìn)去，故故為最小生生成樹(shù)，而而丟邊法則則是S=E以不形成回回路為準(zhǔn)則則逐步丟邊邊以形成樹(shù)樹(shù)，由于是是按邊權(quán)愈愈大愈優(yōu)先先丟掉，故故同樣為最最小生成樹(shù)樹(shù)。設(shè)G=(V,E,W)，|V|=n，|E|=m，S—待生成的集集合（逐步步丟邊）i—S中丟掉邊的的序號(hào)j—S中保留邊的的序號(hào)ei+1—S中丟到的邊邊e1—S中丟到的邊邊的全體（（集合）fj+1—S中保留的邊邊D—S中保留邊的的集合由于邊個(gè)數(shù)數(shù)為m，樹(shù)含邊的個(gè)個(gè)數(shù)為n-1，故丟掉（形成回回路）邊的的個(gè)數(shù)為m-(n-1)=m-n+1，以此為程序出出口，標(biāo)志志著最小生生成樹(shù)形成成依次從大到到小按列同同例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+1ei=alS=S-{ei}E1=E1∪{ei}T*=S-E1打印T*的邊序列j=j+1fj=alD=D∪{fi+1}i≥m-n-1ENDNNYY圖九例6.（同同例5）用丟丟邊法求解求解過(guò)程見(jiàn)表表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最最大大流問(wèn)題由前知，一個(gè)個(gè)指定了收點(diǎn)點(diǎn)和發(fā)點(diǎn)的賦賦權(quán)圖G稱(chēng)為網(wǎng)絡(luò)，在在網(wǎng)絡(luò)設(shè)計(jì)中中研究網(wǎng)絡(luò)的的流量具有現(xiàn)現(xiàn)實(shí)意義，如如交通網(wǎng)絡(luò)的的車(chē)流流量，，通信網(wǎng)絡(luò)中中的話(huà)務(wù)流量量，金融網(wǎng)絡(luò)絡(luò)中的現(xiàn)金流流量，控制網(wǎng)網(wǎng)絡(luò)中的信息息流量，供電電網(wǎng)絡(luò)中的電電流流量等。。人們也常常常希望知道在在既定網(wǎng)絡(luò)中中能允許通過(guò)過(guò)的最大流量量，以便對(duì)該該網(wǎng)絡(luò)的利用用程序作出評(píng)評(píng)價(jià)，這就是是所謂的網(wǎng)絡(luò)絡(luò)最大流問(wèn)題題。求解方法法有雙標(biāo)號(hào)法法，對(duì)偶圖法法等。1．網(wǎng)絡(luò)中弧的的容量與流量量def9：對(duì)于一個(gè)指指定收、發(fā)點(diǎn)點(diǎn)的賦權(quán)有向向（無(wú)向）圖圖或網(wǎng)絡(luò)N＝（V，A，C），弧aij∈A的最大允許通通過(guò)能力稱(chēng)為為該弧的容量量，記為cij（cij≥0），全體cij構(gòu)成之集合記記為C；而通過(guò)邊aij的實(shí)際流量成成為流量，記記為fij，故有0≤fij≤cij。顯然若fij≥cij則網(wǎng)絡(luò)N在aij邊將發(fā)生堵塞塞現(xiàn)象，這是是人們希望能能避免的現(xiàn)象象。（一）基本概概念2．可行流與最最大流def10：設(shè)有網(wǎng)絡(luò)N＝（V，A，C），稱(chēng)f={fij∣aij∈A}為網(wǎng)絡(luò)N上的流函數(shù)，，簡(jiǎn)稱(chēng)網(wǎng)絡(luò)流；滿(mǎn)足如如下條件的網(wǎng)網(wǎng)絡(luò)流稱(chēng)為可可行流，其中v（f）為網(wǎng)絡(luò)N可行流的總流流量（凈流入入量）。（1）容量限制條條件：（2）流量守恒條條件：說(shuō)明：進(jìn)入節(jié)節(jié)點(diǎn)vj的流量＝自節(jié)節(jié)點(diǎn)vj流出的流量；；fij≡0之零流亦滿(mǎn)足足上述條件，，故零流以為為可行流。3．順向弧、逆逆向弧與可增增路def11：設(shè)f是網(wǎng)絡(luò)N的一可行流，，P是N中從vs到vt的一條路，對(duì)對(duì)于路P途經(jīng)的各弧，，若弧的方向向與路的方向向相同，則稱(chēng)稱(chēng)該弧為順向向弧，若弧的的方向與路的的方向相反，，則稱(chēng)該弧為為逆向弧。若若在路P的一切順向弧?。╲i，vj）上有fij＜cij，在路P的一切逆向弧?。╲j，vi）上有fji＞0，則稱(chēng)路P是一條關(guān)于f的可增路。說(shuō)明：（1）由def11得知：若在路路P中，存在一條條順向?。╲i，vj）有fij＝cij（此時(shí)稱(chēng)弧為為飽和?。?，，或者在路P中存在一條逆逆向?。╲j，vi）有fji＝0，則稱(chēng)路P為不可增路；；（2）在圖10所示的網(wǎng)絡(luò)N中有一可行流流f={fij∣aij∈A}，用藍(lán)字標(biāo)記記，紅字標(biāo)記記各弧的容量量cij。表17給出了四條從從v1到v7的路是否可增增路的判別理理由。（此f滿(mǎn)足流量守恒恒條件與容量量限制條件，，如圖10表17jv1到v7的路可增路？理由1v1v2v5v7√順向弧有fij＜cij2v1v2v5v3v6v7√順向弧fij＜cij逆向弧有f35＞03v1v4v7×順向弧有f47＝c474v1v2v3v4v7×順向弧有f23＝c23，f47＝c47（3）可增路的內(nèi)內(nèi)涵可通過(guò)下下例得知在圖10之可行流f中，對(duì)于路v1v2v5v3v6v7途經(jīng)的各弧中中，若f12，f23增加一個(gè)單位位流量，f35減少一個(gè)單位位流量，利用用流量守恒條條件，可得一一個(gè)如圖11的新的可行流流，并并有v（）=10＞9=v（f）。圖11由上可知在def11中可增路要求求順向弧fij＜cij之條件，實(shí)際際上說(shuō)明沿該該?。╲i，vj）還可提高流量△△ij＝cij－fij＞0，另一方面，，為提高流量v（f）還要求該路路的逆向弧降降低流量，而而fji＞0正說(shuō)明了該逆逆向弧可降低低fji個(gè)單位。1．算法思想（（見(jiàn)圖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（二）雙標(biāo)號(hà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開(kāi)始反向搜索途經(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)整步驟（（見(jiàn)圖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)的的逆向向弧作作調(diào)整整，其其調(diào)整整量△△ji＝fji－l（v）；3oG中不在在pl路上的的各弧弧不作作調(diào)整整。4．例7（教材材P219）某石油油公司司擁有有一管管道網(wǎng)網(wǎng)絡(luò)，，使用用此管管道網(wǎng)網(wǎng)絡(luò)可可將石石油從從采地地v1運(yùn)往銷(xiāo)銷(xiāo)地v7，由于于各地地的地地質(zhì)條條件等等不同同，因因而其其管道道直徑徑有所所不同同，從從而使使各弧弧的容容量cij（單位位：萬(wàn)萬(wàn)加侖侖/小時(shí)））不同同，對(duì)對(duì)于如如圖14所示的的管道道網(wǎng)絡(luò)絡(luò)N＝（V，A，C），問(wèn)問(wèn)每小小時(shí)從從v1往v7能運(yùn)送送多少少加侖侖石油油？圖14解1：若設(shè)設(shè)弧（（vi，vj）上的的流量量為fij，網(wǎng)絡(luò)絡(luò)N上總流流量為為F，則可可建立立如下下LP：maxF＝f12＋f14f12＝f23＋f25f14＝f43＋f46＋f47f23＋f43＝f35＋f36s．tf25＋f35＝f57f36＋f46＝f67f47＋f57＋f67＝f12＋f14fij≤ciji＝1～6，j＝1～7fij≥0i＝1～6，j＝1～7v1v2v3v4v5v6v7v1v2v3v4v5v6v70606000002030000002200030032000000500000050000000C陣?yán)脝渭兗冃畏煽山獾米钭畲罅鳎海篺*＝{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)號(hào)法求最最大流））求解中尋尋找了五五條可增增路，其其標(biāo)號(hào)過(guò)過(guò)程與增增流過(guò)程程見(jiàn)表18，表18中各可增增路及其其流量調(diào)調(diào)整過(guò)程程見(jiàn)圖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)網(wǎng)絡(luò)（電電信網(wǎng)絡(luò)絡(luò)、運(yùn)輸輸網(wǎng)絡(luò)、、計(jì)算機(jī)機(jī)網(wǎng)絡(luò)））的分析析與設(shè)計(jì)計(jì)問(wèn)題中中，人們們除關(guān)心心網(wǎng)絡(luò)的的系統(tǒng)容容量外還還要考慮慮費(fèi)用問(wèn)問(wèn)題，以以便建立立一個(gè)高高效、低低耗的網(wǎng)網(wǎng)絡(luò)系統(tǒng)統(tǒng)。這就就是最小小費(fèi)用最最大流問(wèn)問(wèn)題的研研究。def12：設(shè)網(wǎng)絡(luò)絡(luò)N＝｛V,A｝，除對(duì)對(duì)每一弧弧a∈A規(guī)定了其其容量c(a)外，還給給定一個(gè)個(gè)數(shù)b(a)≥0稱(chēng)為弧a的單位流流量費(fèi)用用，即有有網(wǎng)絡(luò)N＝｛V,A,c,b｝稱(chēng)其為為帶費(fèi)用用（代價(jià)價(jià)）的網(wǎng)網(wǎng)絡(luò)。設(shè)設(shè)f是N上的一個(gè)個(gè)可行流流（從vs到vt），稱(chēng)為為可行流流f的費(fèi)用。。將N上所有流流量等于于v0的可行流流中費(fèi)用用最小的的可行流流f稱(chēng)為流量量為v0的最小費(fèi)費(fèi)用流，，進(jìn)一步步當(dāng)v0又是N中最大流流的流量量時(shí)，則則稱(chēng)此f為最小費(fèi)費(fèi)用最大大流。（一）基基本概念念例8某石油公公司管道道網(wǎng)，由由于輸油油管道的的長(zhǎng)短不不一，故故對(duì)于不不同的地地段（路路徑）有有不同的的容量限限制cij之外，還還有不同同的單位位流量費(fèi)費(fèi)用bij，該cij的單位為為萬(wàn)加侖侖/小時(shí)，bij的單位為為百元/萬(wàn)加侖，，管道網(wǎng)網(wǎng)絡(luò)如圖圖16所示，圖圖中括號(hào)號(hào)內(nèi)的數(shù)數(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)費(fèi)用流，，p是關(guān)于f的可增路路中費(fèi)用用最小的的可增路路?？稍鲈鋈萘繛闉棣膭t沿p增容δ后所得到到的可行行流即即為為的的最小小費(fèi)用流流。若將N中弧aij的單位費(fèi)費(fèi)用bij作為該弧弧的弧長(zhǎng)長(zhǎng)，則上上述定理理中的““可增路路中費(fèi)用用最小””可理解解為“可可增容的的最短路路”。（（∵此中中最短的的含義即即為路徑徑各弧的的費(fèi)用和和最?。├蒙鲜鍪龆ɡ砜煽傻萌缦孪滤惴ú讲襟E。圖172.算法步驟驟表19l關(guān)于fl－1的可