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

運籌學圖與網(wǎng)絡分析第十章

圖與網(wǎng)絡

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

1圖

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

若N和E均為有限集合，則稱為G為有限圖，否則稱無限圖。若G中既沒有有限回路（圈），也沒有兩條邊連接同一對點，則稱G為簡單圖。如右圖之（a），右圖之（b）不是簡單圖。若G為簡單圖，且G中每個點對之間均有一條邊相連，則稱G為完全圖。如圖（a）是簡單圖，但不是完全圖。

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

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

有向圖路回路無向圖鏈圈3子圖

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

vs＝vt沿pl從收點vt開始反向搜索途經(jīng)各弧，按調(diào)整規(guī)則作流量調(diào)整抹去pl上各點之雙標號，從而由原可行流f調(diào)整為新可行流f1，并有v（f）＜v（f1）是否還有新的可增路打印并輸出經(jīng)調(diào)整后的最大流f*＝{fij∣aij∈A}，最大流量v（f*）結束l＝l＋1取N的新的可增路plj＝k，i＝j沿pl尋找vj的相鄰的一點vk圖13NYYN2．調(diào)整步驟（（見圖13）3．標號與調(diào)整整規(guī)則（1）標號規(guī)則：：1o若（vi，vj）為順向弧，，且fij<cij，則給vj標號（vi＋，l（vj）），其中l(wèi)（vj）＝min（l（vi），cij－fij）；2o若（vi，vj）為逆向弧，，且fji>0，則給vj標號（vi－，l（vj）），其中l(wèi)（vj）＝min（l（vi），fji）；3o若（vi，vj）為順向弧但但fij＝cij或（vi，vj）為逆向弧但fji＝0，此時沿該弧弧的路線停止止標號。（2）調(diào)整規(guī)則：：1o若（vi，vj）為順順向弧弧，則則對pl路徑的的順向向弧作作調(diào)整整，其其調(diào)整整量△△ij＝fij＋l（v）；2o若（vi，vj）為逆逆向弧弧，則則對pl途經(jīng)的的逆向向弧作作調(diào)整整，其其調(diào)整整量△△ji＝fji－l（v）；3oG中不在在pl路上的的各弧弧不作作調(diào)整整。4．例7（教材材P219）某石油油公司司擁有有一管管道網(wǎng)網(wǎng)絡，，使用用此管管道網(wǎng)網(wǎng)絡可可將石石油從從采地地v1運往銷銷地v7，由于于各地地的地地質條條件等等不同同，因因而其其管道道直徑徑有所所不同同，從從而使使各弧弧的容容量cij（單位位：萬萬加侖侖/小時））不同同，對對于如如圖14所示的的管道道網(wǎng)絡絡N＝（V，A，C），問問每小小時從從v1往v7能運送送多少少加侖侖石油油？圖14解1：若設設?。ǎ╲i，vj）上的的流量量為fij，網(wǎng)絡絡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陣利用單純純形法可可解得最最大流：：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：（采用用雙標號號法求最最大流））求解中尋尋找了五五條可增增路，其其標號過過程與增增流過程程見表18，表18中各可增增路及其其流量調(diào)調(diào)整過程程見圖15。求解結果果與解1相同。圖15表18（例7求解過程程）l可增路pl第二個標號l（vj）可調(diào)整量l（vt）標號圖調(diào)整圖網(wǎng)絡流量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已無可增增路END§10.5最小費用用最大流流在很多網(wǎng)網(wǎng)絡（電電信網(wǎng)絡絡、運輸輸網(wǎng)絡、、計算機機網(wǎng)絡））的分析析與設計計問題中中，人們們除關心心網(wǎng)絡的的系統(tǒng)容容量外還還要考慮慮費用問問題，以以便建立立一個高高效、低低耗的網(wǎng)網(wǎng)絡系統(tǒng)統(tǒng)。這就就是最小小費用最最大流問問題的研研究。def12：設網(wǎng)絡絡N＝｛V,A｝，除對對每一弧弧a∈A規(guī)定了其其容量c(a)外，還給給定一個個數(shù)b(a)≥0稱為弧a的單位流流量費用用，即有有網(wǎng)絡N＝｛V,A,c,b｝稱其為為帶費用用（代價價）的網(wǎng)網(wǎng)絡。設設f是N上的一個個可行流流（從vs到vt），稱為為可行流流f的費用。。將N上所有流流量等于于v0的可行流流中費用用最小的的可行流流f稱為流量量為v0的最小費費用流，，進一步步當v0又是N中最大流流的流量量時，則則稱此f為最小費費用最大大流。（一）基基本概念念例8某石油公公司管道道網(wǎng)，由由于輸油油管道的的長短不不一，故故對于不不同的地地段（路路徑）有有不同的的容量限限制cij之外，還還有不同同的單位位流量費費用bij，該cij的單位為為萬加侖侖/小時，bij的單位為為百元/萬加侖，，管道網(wǎng)網(wǎng)絡如圖圖16所示，圖圖中括號號內(nèi)的數(shù)數(shù)字表示示（cij，bij）。解1：設fij表示aij上實際流流量，則則由定義義12可建立如如下LPs.tmax總費用b(f)=145此解與例例7的解顯然然不同，，它是在在考慮了了費用目目標后的的結果。。（二）求求解算法法算法原理理：最小小費用最最大流之之算法有有多種，，以下介介紹一種種比較易易理解的的算法。。定理3：設f是流量為為v0的最小費費用流，，p是關于f的可增路路中費用用最小的的可增路路?？稍鲈鋈萘繛闉棣膭t沿p增容δ后所得到到的可行行流即即為為的的最小小費用流流。若將N中弧aij的單位費費用bij作為該弧弧的弧長長，則上上述定理理中的““可增路路中費用用最小””可理解解為“可可增容的的最短路路”。（（∵此中中最短的的含義即即為路徑徑各弧的的費用和和最?。├蒙鲜鍪龆ɡ砜煽傻萌缦孪滤惴ú讲襟E。圖172.算法步驟驟表19l關于fl－1的可