8-圖與網(wǎng)絡分析課件

第八章

圖與網(wǎng)絡分析第一節(jié)圖與網(wǎng)絡的基本知識第二節(jié)樹第三節(jié)最短路問題第四節(jié)最大流問題第五節(jié)最小費用流問題講五節(jié)：慘泳蠅盅搪古炒委北埠如輩陛熄靈滁閑首翌坦縛繕鍍須濕柑裁靠免歡緊纏+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/20231第八章

圖與網(wǎng)絡分析第一節(jié)圖與網(wǎng)絡的基本知識講五節(jié)：§8-1圖與網(wǎng)絡的基本知識一、圖與網(wǎng)絡的基本概念1、圖及其分類圖是反映對象之間關系的一種工具。例如，在一個人群中，對相互認識這種關系可以用圖來表示。趙(v1)錢(v2)孫(v3)李(v4)周(v5)吳(v6)陳(v7)若將“相互認識”的關系改成“認識”，可以用帶箭頭的連線表示。頂點邊定義1

一個圖是由點集V={vi}和V中元素的無序?qū)Φ囊粋€集合E={ek}所構成的二元組,記為G=(V,E),V中的元素vi叫做頂點,E中的元素ek叫做邊。當V，E為有限集合時,G稱為有限圖,否則,稱為無限圖e1e2e3e4e5V={vi}={v1,v2,…,v7}E={ei}={e1,e2,…,e5}返回第八章目錄焊蓉挪即螞布躥避選懶欺勻盜朝磐湛恒鄂系和息追緝蛤瘦靠洛枯匠魯朝漱+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/20232§8-1圖與網(wǎng)絡的基本知識一、圖與網(wǎng)絡的基本概念趙(v1例1

在圖8-7中：

V={v1,v2,v3,v4,v5} E={e1,e2,e3,e4,e5,e6}兩條邊ei,ej

屬于E，如果它們有公共端點u，則稱ei,ej相鄰。邊ei,ej稱為u的關聯(lián)邊。對于任一條邊(vi,vj)屬于E，如果邊(vi,vj)端點無序，則它是無向邊，此時圖為無向圖.圖8-7是無向圖.如果邊(vi,vj)端點有序,即它表示以vi為始點,vj為終點的有向邊(或稱弧),這時圖G稱為有向圖。一條邊的兩個端點如果相同,稱此邊為環(huán)(自回路).如圖8-7中的e1。兩個點之間多于一條邊的，稱為多重邊,如圖8-7中的e4,e5。其中：e1=(v1,v1)；e2=(v1,v2)；e3=(v1,v3)e4=(v2,v3)；e5=(v2,v3)；e6=(v3,v4)兩個點u,v屬于V,如果邊(u,v)屬于E,則稱u,v兩點相鄰。u,v稱為邊(u,v)的端點。e1v1e2v2e4e5v3v4e6v5圖8-7e3義鼻顱眼旺圃蛇觸刀憫弛乙叫瀑違寇盡孔岔酪祥茄訛班橙豺疏怨倚鋤歉意+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/20233例1在圖8-7中：

V={v1,v2,v3,v4,v5}定義2不含環(huán)和多重邊的圖稱為簡單圖，含有多重邊的圖稱為多重圖。有向圖中兩點之間有不同方向的兩條邊，不是多重邊。定義3每一對頂點間都有邊相連的無向簡單圖稱為完全圖。有n個頂點的無向完全圖記作Kn。每一對頂點間有且僅有一條有向邊的簡單圖，稱為有向完全圖。(b)(c)(a)(d)圖8-8簡單圖簡單圖多重圖多重圖器奮揮捉喧淳繃鞠皿睦孜重倡淘吞鐘澤嶄膳澇黎層少掛蹲騾鴕苔召虐興鍬+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/20234定義2不含環(huán)和多重邊的圖稱為簡單圖，含有多重邊的圖稱為定義4圖G＝(V,E)的點集V可以分為兩個非空子集X，Y，即XUY＝V,X∩Y＝f，使得E中每條邊的兩個端點必有一個端點屬于X，另一個端點屬于Y，則稱G為二部圖(偶圖)，有時記作G＝(X,Y,E)。例如圖8-9中的(a)是明顯的二部圖，點集X：{v1,v3,v5)，Y：{v2,v4,v6}，(b)也是二部圖，但是不像

(a)那樣明顯，改畫為(c)時可以清楚地看出。v1v2v6v5v3v4(a)v4v1v3v2(b)v1v2v4v3(c)圖8-9爸蠟開要命緣鹿瘴硬刊贅忻遏激遜忘躲臺法觸搪擱刃肉師卉彩炬韋孜項悍+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/20235定義4圖G＝(V,E)的點集V可以分為兩個非空子集X2.頂點的次

定義5以點v為端點的邊數(shù)叫做點v的次,記作deg(v),簡記d(v)。如圖8-7中點v1的次d(v1)=4,因為邊e1要計算兩次。點v3的次d(v3)=4，點v4的次d(v4)=1。次為1的點稱為懸掛點,連接懸掛點的邊稱為懸掛邊.如8-7圖中v4,e6。次為零的點稱為孤立點，如圖8-7中的點v5。次為奇數(shù)的點稱為奇點。次為偶數(shù)的點稱為偶點。e1v1e2v2e4e5v3v4e6v5圖8-7e3定理1

任何圖中，頂點次數(shù)的總和等于邊數(shù)的2倍。證明：由于每條邊必與兩個頂點關聯(lián)，在計算點的次時，每條邊均被計算了兩次，所以頂點次數(shù)的總和等于邊數(shù)的2倍。懸掛點懸掛邊孤立點奇點偶點偶點郭辯篷混怖凜堡無悔筷蜘藻鈞集弛乎滁泥埋奠甕棋般雖渙共廖化本孔怒趟+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202362.頂點的次

定義5以點v為端點的邊數(shù)叫做點v的次,記定理2

任何圖中，次為奇數(shù)的頂點必為偶數(shù)個。

證明：設V1和V2分別為G中奇點與偶點的集合(V1UV2=V).由定理1知定義6有向圖中,以vi為始點的邊數(shù)稱為點vi的出次，用d+(vi)表示；以vi為終點的邊數(shù)稱為點vi的入次，用d－(vi)表示。點的出次與入次之和就是該點的次。容易證明有向圖中，所有頂點的入次之和等于出次之和。3.子圖

定義7圖G=(V,E),若E′是E的子集,V′是V的子集，且E′中的邊僅與V′中的頂點相關聯(lián)，則稱G′

=(V′,E′)是G的一個子圖。特別地，若V′=V，則G′稱為G的生成子圖。騁濃抹非倫拔牟梯嘿益晶綸四森掄很濰晌囤復殿恬碼娠氰鑒糊嘗纏慨璃掙+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/20237定理2任何圖中，次為奇數(shù)的頂點必為偶數(shù)個。

證明：設V1和v4v1v5v3v2v6v7e8e4e9e6e7(c)上圖中，(b)為(a)的子圖，(c)為(a)的生成子圖。4.網(wǎng)絡在實際問題中，只用圖來描述所研究對象之間的關系往往是不夠的，與圖聯(lián)系在一起的，通常還有與點或邊有關的某些數(shù)量指標，我們常稱之為“權”，權可以代表如距離、費用、通過能力（容量）等等。這種點或邊帶有某種數(shù)量指標的圖稱為網(wǎng)絡(賦權圖)。V′∈V,E′∈EV′∈V,E′∈E.且V′=Vv5v6v3v2v1e1e6v5v4(b)v7v5v2v1e10e7e9e8v3e4e5e1e2e6v4v6(a)e3寄頹哦羅窟竊劫吊挽陪嚎捐臂練恭唯宇農(nóng)駁幻晦刨坑頌銜扣歐漱包虧蟹量+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/20238v4v1v5v3v2v6v7e8e4e9e6e7(c)上圖中二、連通圖e7v5v4v3v2v1v6e1e3e4e5e6e8e9e10e2圖8-12圖8-12中，S={v6,e6,v5,e7,v1,e8,v5,e7,v1,e9,v4,e4,v3}為一條連結v6,v3的鏈。S1={v6,e6,v5,e7,v1,e8,v5,e5,v4,e4,v3}為一條連結v6,v3的簡單鏈。S2={v6,e6,v5,e5,v4,e4,v3}為初等鏈。定義9

無向圖G中,連結vi0與vik的一條鏈，當vi0與vik是同一個點時,稱此鏈為圈.圈中只有重復點而無重復邊者為簡單圈，既無重復點也無重復邊者為初等圈，有向圖當鏈(圈)上的邊方向相同時,稱為道路(回路)。{v1,e7,v5,e8,v1,e9,v4,e10,v2,e2,v1}為一個圈。有恃撥巖謀臨祥鞠整駱水戚對敞衙匹溝條爺冷神綽嘯阜潤嘴廂社鄭狙族水+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/20239二、連通圖e7v5v4v3v2v1v6e1e3e4e5e6e對于有向圖可以類似于無向圖定義鏈和圈，初等鏈、圈，簡單鏈、圈，此時不考慮邊的方向。而當鏈（圈）上的邊方向相同時，稱為道路（回路）。圖8-13中,S={v6,e6,v5,e8,v1,e9,v4,e10,v2,e3,v3}為一條鏈。S1={v6,e6,v5,e7

,v1,e9

,v4,e4

,v3}為一條道路。S2={v1

,e2

,v2

,e11

,v4

,e5

,v5

,e8

,v1}為一個圈。S3={v1,e2

,v2

,e10

,v4

,e5

,v5

,e7,v1}為一個回路。e7v5v4v3v1v6v2e10e11e3e2e5e9e8e1e6圖8-13e4定義10一個圖中任意兩點間至少有一條鏈相連，則稱此圖為連通圖。任何一個不連通圖都可以分為若干個連通子圖，每一個連通子圖稱為原圖的一個分圖。饒局餐呻奇錯背熏斤蔓夸涸汽診恤萬餌蛻溯樊翰護秋嚏付動煎汪搭癌烹總+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202310對于有向圖可以類似于無向圖定義鏈和圈，初等鏈、圈，簡單鏈、圈三、圖的矩陣表示定義11網(wǎng)絡(賦權)圖G=(V,E),其邊(vi,vj)有權wij，構造矩陣A=(aij)nn，其中例2圖示8-14所示的圖其權矩陣為：稱矩陣A為網(wǎng)絡G的權矩陣。6v5v4v3v2v1754238圖8-1494v1v1v2v3v4v5v2v4v5胺搔縷菱刪檀煉皺共芍套剖柜簡嫂忍粉崩憤檢型寧壩賣押牙肚杖舜奄持蒼+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202311三、圖的矩陣表示定義11網(wǎng)絡(賦權)圖G=(V,E),定義12

對于圖G=(V,E),|V|=n,構造一個矩陣A=(aij)nn,其中：則稱矩陣A為圖G的鄰接矩陣。例3對圖8-15所表示的圖可以構造鄰接矩陣A如下：v1v2v3v4v6v5圖8-15v1v2v3v4v5v6當G為無向圖時，鄰接矩陣為對稱矩陣。爍絆份拋宇畏癡棱可懊夠緘粟升雁頭歷奸霓舜坦量攝江檄皋賠記斬底子筒+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202312定義12對于圖G=(V,E),|V|=n,構造一個矩陣A=四、歐拉回路與中國郵路問題1.歐拉回路與道路定義13連通圖G中，若存在一條道路，經(jīng)過每邊一次且僅一次，則稱這條路為歐拉道路。若存在一條回路，經(jīng)過每邊一次且僅一次，則稱這條回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖（E圖）。定理3

無向連通圖G是歐拉圖，當且僅當G中無奇點。推論1無向連通圖G為歐拉圖，當且僅當G的邊集可劃分為若干個初等回路。推論2無向連通圖G有歐拉道路，當且僅當G中恰有兩個奇點。定理4

連通有向圖G是歐拉圖，當且僅當它每個頂點的出次等于入次。連通有向圖G有歐拉道路，當且僅當這個圖中除去兩個頂點外，其余每一個頂點的出次等于入次，且這兩個頂點中，一個頂點的入次比出次多1，另一個頂點的入次比出次少1。從鞋恨舵晚升腰迭盒搞貓隋嬸呀墨腐墓公傭蠅痔棗笨汽嘲枷莖耍藥旅洋觀+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202313四、歐拉回路與中國郵路問題1.歐拉回路與道路從鞋恨舵晚升腰2.中國郵路問題一個郵遞員，負責某一地區(qū)的信件投遞。他每天要從郵局出發(fā)，走遍該地區(qū)所有街道再返回郵局，問應如何安排送信的路線可以使所走的總路程最短？國際上通稱這個問題為中國郵路問題。用圖論的語言描述：給定一個連通圖，每邊有非負權l(xiāng)(e)，要求一條回路過每邊至少一次，且滿足總權最小。中國郵路問題也可以轉(zhuǎn)為如下問題：在連通圖G=(V,E)中，求一個邊集E1∈E，把G中屬于E1的邊均變?yōu)槎剡叺玫綀DG*=G+E1，使其滿足G*無奇點,且L(E1)=Sl(e)(e∈E1)最小。定理5

己知圖G*=G+E1無奇點,則L(E1)=Sl(e)(e∈E1)最小的充分必要條件為：（1）每條邊最多重復一次；（2）對圖G中每個初等圈來講，重復邊的長度和不超過圈長的一半。定理給出了中國郵路問題的一種算法，稱為“奇偶點圖上作業(yè)法”，下面舉例說明這個算法。認倫韋長權亭耳絲撿噶箱賢瞥弘窩嘩菇嫡隱弗臣壹晦陰喇丙鼠恤烴霸渭華+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/2023142.中國郵路問題一個郵遞員，負責某一地區(qū)的信件投遞。他每天例4求解圖8-16所示網(wǎng)絡的中國郵路問題第一步：確定初始可行方案。先檢查圖中是否有奇點，如無奇點則己是歐拉圖，找出歐拉回路即可。如有奇點，由前知奇點個數(shù)必為偶數(shù)，所以可以兩兩配對。每對點間選一條路，使這條路上均為二重邊。圖8-16中有四個奇點v2,v4,v6,v8，將v2與v4,v6,v8配對，聯(lián)結v2與v4的路有好幾條，任取一條，如{v2,v3,v6,v9,v8,v7,v4}，類似地，對v6與v8取{v6,v3,v2,v1,v4,v7,v8}。得到圖8-17，已是歐拉圖。對應這個可行方案，重復邊的總長為：2l23+2l36+l69+l98+2l87+2l74+l41+l12=51v3v1v2v6v9v8v7v4v5圖8-17v3v1v2v6v9v8v7v4v524344955644圖8-163限像鞋戮砂盒嚴拂鉸口每諒酶蔭綜渾拌妮搖臣叔枷瓤貝楔溉臟傷故恐黑箭+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202315例4求解圖8-16所示網(wǎng)絡的中國郵路問題第一步：確第二步：調(diào)整可行方案，使重復邊最多為一次。去掉(v2,v3),(v3v6),(v4,v7),(v7,v8)各兩條，得到圖8-18。重復邊總長度下降為：l12

+l14+l69

+l98=21v3v1v2v6v9v8v7v4v52434495546圖8-19第三步：檢查圖中每個初等圈是否滿足定理條件(2)。如不滿足則進行調(diào)整，直至滿足為止。檢查圖8-18，發(fā)現(xiàn)圈{v1v2v5v4v1

}總長度為24，而重復邊的長為14，大于該圈總長度的一半，可以作一次調(diào)整，以(v2,v5),(v5,v4)代替(v1,v2),(v1,v4)，得到圖8-19，重復邊總長度下降為：l25+l45

+l69+

l98=17v3v1v2v6v9v8v7v4v544335599圖8-1846油貓仔怖酣甄傍委篙擯榴依鄲廊妊寶覽拳喧夠綁碉腕兩碩沮破牛勸征遞惕+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202316第二步：調(diào)整可行方案，使重復邊最多為一次。去掉(v2,v3)再檢查圖8-19，圈{v2v3v6v9v8v5v2}總長度為24，而重復邊長為13。再次調(diào)整得圖8-20，重復邊總長度為15。檢查圖8-20,條件(1),(2)均滿足，得到最優(yōu)方案。圖中任一歐拉回路即為最優(yōu)郵遞路線。v3v1v2v6v9v8v7v4v52434495544圖8-20v3v1v2v6v9v8v7v4v544335599圖8-1864v3v1v2v6v9v8v7v4v52434495546圖8-194斌潔價礁黎又踏槍泉團等謾獻胚敖得杜像砰拽熒縫獰賈漆跡躍熔坷漁赤宮+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202317再檢查圖8-19，圈{v2v3v6v9v8v5v2}總長度§8-2 樹一、樹的概念和性質(zhì) 例5乒乓球單打比賽抽簽后,可用圖來表示相遇情況,如圖8-21所示。

ECGKABDFHIJLMN運動員圖8-21銷售科檢驗科新產(chǎn)品開發(fā)科技術科生產(chǎn)科設備科供應科動力科人事科總工程師財務科生產(chǎn)副廠長經(jīng)營副廠長圖8-22廠長定義14不含圈的無向連通圖稱為樹。樹中次為1的點稱為樹葉，次大于1的點稱為分枝點。例6某企業(yè)的組織結構可用圖8-22表示樹葉分枝點樹返回第八章目錄紉靠規(guī)甜催盲灌念蝴淳賺埋習碌臃值舀伏啤柬咨怨兄夸靴鉚氣次蒼濃恍拄+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202318§8-2 樹一、樹的概念和性質(zhì)ECGKABDFHIJLMN運定理6

圖T=(V,E),|V|=n,|E|=m,則下列關于樹的說法是等價的：（1）T是一棵樹。（2）T無圈，且m=n-1.（3）T連通，且m=n-1。（4）T無圈，但每加一新邊即得唯一一個圈。（5）T連通，但每舍去一邊就不連通。（6）T中任意兩點，有唯一鏈相連。二、圖的生成樹定義15若圖G的生成子圖是一棵樹，則稱該樹為G的生成樹（支撐樹）?；蚝喎Q為圖G的樹。圖G中屬于生成樹的邊稱為樹枝,不在生成樹中的邊稱為弦。圖8-23中(b)為(a)圖的生成樹,邊e1,e2,e3,e7,e8,e9為樹枝，e4,e5,e6,為弦。e3e4e1e2e6e1e2e7e8e9e5(a)e3e7e8e9(b)

圖8-23樹枝弦撕動靡汗苫接賦貝捂匡物束帚裕賂磐芒樸扛菇系募親后目加船叼確逢榷嚇+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202319定理6圖T=(V,E),|V|=n,|E|=m,定理7

圖G=(V,E)有生成樹的充分必要條件為G是連通圖。求生成樹的方法：1.避圈法（加邊法）在已給的圖G中，每步選出一條邊使它與已選邊不構成圈，直到選夠n-1條邊為止。（1）深探法（標號法）。步驟如下：①

在點集V中任取一點v,給v以標號0。②若某點u已得標號i，檢查一端點為u的各邊，另一端點是否均已標號。若有(u,w)邊之w未標號,則給以標號i+1,記下邊(u,w).令w代u,重復②.若這樣的邊的另一端點均已有標號，就退到標號為i-1的點r以r代u，重復②.直到全部得到標號為止。圖8-24的(a)為標號過程，粗線邊即為生成樹,圖8-24(b)即是生成樹，也顯示了標號過程。萬貝認幸抹庇矯僥粒沫政久愉園菜酥闊佩紐孩年堡池墓禹劫踢羚尼減妻婁+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202320定理7圖G=(V,E)有生成樹的充分必要條件為G是連通圖圖8-24740261012813591113(b)012345698101112137(a)(2)廣探法步驟如下：①在點集V中任取一點v,給v以標號0。②令所有標號為i的點集為Vi，檢查[Vi，V\Vi]中的邊端點是否均已標號。對所有未標號之點均標以i+1，記下這些邊。③對標號為i+1的點重復步驟②。直到全部點得到標號為止。圖8-25(a)中粗線邊就是用廣探法生成的樹，也可表示為圖8-25(b)圖8-254211112222333(b)02343201122211(a)3客吹雄雅渦勸摯患皋悍穿詣贖葛吐硫見哨眉梁助汛被媳潰索糠站攘扭饋汕+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202321圖8-24740261012813591113(b)0例7一個鄉(xiāng)有9個自然村，其間道路如圖8-26(a)所示，要以v0村為中心建有線廣播網(wǎng)絡，如要求沿道路架設廣播線，應如何架設？2.破圈法在圖G中任意取一個圈,從圈上任意舍棄一條邊，將這個圈破掉,重復這個步驟直到圖G中沒有圈為止。v6v1v2v3v4v5v7v8v0(b)(a)v6v1v2v3v4v5v7v8v0圖8-26解：用破圈法，任取一圈(v1,v2,v2,v1)，從中去掉邊(v1,v2)，再選圈(v1,v8,v0,v1)去掉邊(v1,v8)，…，依同樣方法進行，直到無圈。圖8-26(b)就是一種方案?！痢痢痢痢痢痢痢敛柽x訴婿浮函恨膛駐零室貓翱礙紋飲忌禱陵面擱四蛛產(chǎn)莎甭迄陀婚桌梳額+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202322例7一個鄉(xiāng)有9個自然村，其間道路如圖8-26(a)所示，321三、最小生成樹問題定義16

連通圖G=(V,E)，每條邊上有非負權L(e)。一棵生成樹所有樹枝上權的總和，稱為這個生成樹的權。具有最小權的生成樹稱為最小生成樹，簡稱最小樹。最小樹的兩種算法算法1：(Kruskal算法)此法類似于求生成樹的“避圈法”，步驟如下：每步從未選的邊中選取邊e，使它與已選邊不構成圈，且e是未選邊中的最小權邊，直到選夠n-1條邊為止。v4v5(a)v6v1v2v3v7v8v0111122334444555211v6v1v2v3v4v5v7v8v0(b)122圖8-27先將（a）中邊按大小順序由小至大排列：(v0,v2)=1，(v2,v3)=1，(v3,v4)=1(v1,v8)=1，(v0,v1)=2，(v0,v6)=2(v5,v6)=2，(v0,v3)=3，(v6,v7)=3(v0,v4)=4，(v0,v5)=4，(v0,v8)=4(v1,v2)=4，(v0,v7)=5，(v7,v8)=5(v4,v5)=5到翌納執(zhí)沏敏血炊亥餒窖爛粟斑協(xié)騁閏慣輾臉鳳敘琉癱淑弛分蜜游吊蘭廊+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202323321三、最小生成樹問題定義16連通圖G=(V,E)，每定理8

用Kruskal算法得到的子圖T*=(e1,e2,…en-1)是一棵最小樹。然后按照邊的排列順序，取定：(v0,v2)=1，(v2,v3)=1，(v3,v4)=1，(v1,v8)=1，(v0,v1)=2，(v0,v6)=2，(v5,v6)=2。由于下一個未選取邊中的最小權邊(v0,v3)與已選邊e1,e2構成圈，所以排除。選e8=(v6,v7)。得到(b)就是圖G的一棵最小樹,它的權是13。定理9

圖G的生成樹T為最小樹，當且僅當對任一弦e來說，e是T+e中與之對應的圈me中的最大權邊。定義17若一個有向圖在不考慮邊的方向時是一棵樹，則稱這個有向圖為有向樹。定義18有向樹T，恰有一個結點入次為0，其余各點入次均為1，則稱T為根樹（又稱外向樹）。根樹中入次為0的點稱為根。根樹中出次為0的點稱為葉，其它頂點稱為分枝點。由根到某一頂點vi的道路長度（設每邊長度為1），稱為vi點的層次。牲畸咽護墻墾陶震燥抓碧漸寇嗡叢霄僚竿歧降婁綁爾粵萍漬渙景榷頻損榨+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202324定理8用Kruskal算法得到的子圖T*=(e1,e2定義19在根樹中,若每個頂點的出次小于或等于m,稱這棵樹為m叉樹,若每個頂點的出次恰好等于m或零,則稱這棵樹為完全m叉樹。當m=2時，稱為二叉樹、完全二叉樹。圖8-29所示的樹是根樹，其中v1為根，v1,v2,v3,v4,v8為分枝點，其余各點為葉，頂點v2,v3,v4的層次為1,頂點v11的層次為3等等。圖8-29??????v11v1v2v3v4v5v6v7v8v9v10??????(a)?(b)?????圖8-30例如圖8-30中(a)為完全三叉樹、(b)為四叉樹。實際問題中常討論葉子上帶權的二叉樹,令有s個葉子的二叉樹T各葉子的權分別為pi,根到各葉子的距離(層次)為li(i=1,…,s),這樣二叉樹的總權數(shù)：南塵剿化年叁巒尤倘禹挪醛唉依帆炮貸距淤藹梆逞湍攤疆母脂美育緩腮制+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202325定義19在根樹中,若每個頂點的出次小于或等于m,稱這棵樹4??????122333滿足總權最小的二叉樹稱為最優(yōu)二叉樹(霍夫曼樹）。算法步驟為：⑴將s個葉子按權由小至大排序,不失一般性，設p1≤p2≤…≤ps。⑵將二個具有最小權的葉子合并成一個分枝點，其權為p1+p2,將新的分枝點作為一個葉子。令s←s-1，若s=1停止，否則轉(zhuǎn)(1)。例9s=6其權分別為4,3,3,2,2,1,求最優(yōu)二叉要樹。解：該樹構造過程見圖8-31。總權為1×4+2×4+2×3+3×2+3×2+4×2=38圖8-31??????1223334569??????122333456915421?????233356此算法得到的樹為最優(yōu)二叉樹，直觀意義：葉子的距離是依權的遞減而增加，所以總權最小。哈椅吹奴離鑲穿睫解駐燃漱攏硝兼莽俞葷枚杯擾詢屆閨奢掙征囂襟皚淋嗅+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/2023264??????122333滿足總權最小的二叉樹稱為最優(yōu)二例10最優(yōu)檢索問題使用計算機進行圖書分類?，F(xiàn)有五類圖書共100萬冊，其中有A類50萬冊，有B類20萬冊，C類5萬冊，D類10萬冊,E類15萬冊。問如何安排分檢過程，可使總的運算(比較)次數(shù)最小？解:構造一棵具有5個葉子的最優(yōu)二叉樹,其葉子的權分別為50,20,5,10,15,見圖8-32(a)所示,按(b)進行分類.總權為：m(T)=5×4+10×4+15×3+20×2+50×1=195圖8-32105151002050501530EABCD(a)

Y

NE?B?A?D?ABCDE

N

Y

Y

N

N

Y(b)分檢過程是先把A類50萬冊從總數(shù)中分檢出來,其次將B類20萬冊分檢出來,然后再將E類15萬冊分檢出來,最后再將D,C分檢。諱腥胸冬蜀戀灤蔬玄哼胸貸恿累跟廳鉗屹阻抓渺供米蔑嘎簧慨毅丘盤兌糟+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202327例10最優(yōu)檢索問題使用計算機進行圖書分類?，F(xiàn)有五類圖書例11某廠購進一批原件，欲進行檢驗后按質(zhì)量分為六等。已知一等品的概率為0.45，二等品的概率為0.25，三

等品0.12，四等品0.08，五等品0.05，等外品0.05。假設分等測試一次只能分辨出一種等級，而每次測試的時間皆為t。問如何安排測試過程，使期望的時間達到最短？解：構造一棵具有6個葉子的最優(yōu)二叉樹，其葉子的權數(shù)為各等級品的概率，見圖8-33所示。0.050.080.050.120.250.450.100.180.300.551.01等品等外品5等品4等品3等品2等品測試順序圖8-33期望最短測試時間就是最優(yōu)二叉樹的總權，經(jīng)計算得：m(T)=(5×0.05+5×0.05+4×0.08+3×0.12+2×0.25+1×0.45)t=2.13t端山騷塔俺丁兢鎂邑鯉撕壬化愛灰欲佑眨詹樊嘶簾燭街敬蓉川斌掖拔燦濤+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202328例11某廠購進一批原件，欲進行檢驗后按質(zhì)量分為六等。已知一§8-3最短路問題設G=(V,E)為連通圖，圖中各邊(vi,vj)有權l(xiāng)ij(lij=∞表示vi,vj間無邊)，vs,vt為圖中任意兩點，求一條道路m，使它是從vs到vt的所有路中總權最小的路。即有些最短路問題也可以是求網(wǎng)絡中某指定點到其余所有結點的最短路，或求網(wǎng)絡中任意兩點間的最短路。一、Dijkstra算法

基本步驟，采用標號法?？捎脙煞N標號：T標號與P標號，T標號為試探性標號，P為永久性標號，給vi點一個P標號時，表示從vs到vi點的最短路權，vi點的標號不再改變。給vi點一個T標號時，表示從vs到vi點的估計最短路權的上界，是一種臨時標號，凡沒有得到P標號的點都有T標號。算法每一步都把某一點的T標號改為P標號，當終點vt得到P標號時，全部計算結束。對于有n個頂點的圖，最多經(jīng)n-1步就可以得到從始點到終點的最短路。返回第八章目錄即淀乘距亢杜焉氯惺圍占鴦摩舵躲抄棄詣鴕瞞癢否暫鄙唾售屋疲究激很泥+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202329§8-3最短路問題設G=(V,E)為連通圖，圖中各邊(vDijkstra算法步驟：(1)給vs以P標號，P(vs)=0，其余各點均給T標號T(vi)=+∞。(2)若vi點為剛得到標號的點，考慮這樣的點vj：(vi,vj)屬于E，且vj為T標號。對vj的標號進行如下的更改：T(vj)=min[T(vj),P(vi)+lij](3)比較所有具有T標號的點，把最小者改為P標號，即：當存在兩個以上最小者時，可同時改為P標號。若全部點均為P標號則停止。否則用代vi轉(zhuǎn)回（2）。￣vP(vi)＝min[T(vi)]￣罰恤柒嘶逐哈待域扮子蓖絕匡殼甘沙姥鼠旬姚云束勒閱了耙聲攝鼠面己慘+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202330Dijkstra算法步驟：(1)給vs以P標號，P(vs)例12用Dijkstra算法求圖8-34中v1點到v8點的最短路。圖8-34

v1

v2

v3

v4

v5

v6

v7

v84444555667719

解：(1)首先給v1以P標號，P(v1)=0，給其余所有點T標號，T(vi)=+∞(i=2,…,8)(2)由于(v1,v2),(v1,v3)邊屬于E,且為T標號,所以修改這兩個點的標號： T(v2)=min[T(v2),P(v1)+l12]=min[+∞,0+4]=4

T(v3)=min[T(v3),P(v1)+l13]=min[+∞,0+6]=6(3)比較所有T標號,T(v2)最小,所以令P(v2)=4。(4)v2為剛得到P標號的點,考察邊(v2,v4),(v2,v5)的端點v4,v5。 T(v4)=min[T(v4),P(v2)+l24]=min[+∞,4+5]=9 T(v5)=min[T(v5),P(v2)+l25]=min[+∞,4+4]=8(5)比較所有T標號,T(v3)最小,所以令P(v3)=6。(6)考慮點v3，有筏親饑彬峪奢惺娘寓驟垃仆欲根澀無漿湍擲踩蠟射件傭巨屑患川毛塘烯歌+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202331例12用Dijkstra算法求圖8-34中v1點到v8點的 T(v4)=min[T(v4),P(v3)+l34]=min[9,6+4]=9 T(v5)=min[T(v5),P(v3)+l35]=min[8,6+7]=8(7)全部T標號中,T(v5)最小,令P(v5)=8(8)考察v5 T(v6)=min[T(v6),P(v5)+l56]=min[+∞,8+5]=13 T(v7)=min[T(v7),P(v5)+l57]=min[+∞,8+6]=14(9)全部T標號中,T(v4)最小,令P(v4)=9(10)考察v4， T(v6)=min[T(v6),P(v4)+l46]=min[13,9+9]=13 T(v7)=min[T(v7),P(v4)+l47]=min[14,9+7]=14(11)全部T標號中,T(v6)最小,令P(v6)=13(12)考察v6， T(v7)=min[T(v7),P(v6)+l67]=min[14,13+5]=14 T(v8)=min[T(v8),P(v6)+l68]=min[+∞,13+4]=17(13)全部T標號中,T(v7)最小,令P(v7)=14(14)考察v7,

T(v8)=min[T(v8),P(v7)+l78]=min[17,14+1]=15

俘尖攤抑趙膠蔑遏昌渠繼兢稗玉射煽陣趴順拇細芥診寢豬豁畝裸群甩孩斬+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202332 T(v4)=min[T(v4),P(v3)+(15)因只有一個T標號T(v8),令P(v8)=15,計算結束。全部計算結果見圖8-35。v1到v8之最短路為v1→v2→v5→v7→v8路長p(v8)=15，同時得到v1點到其余各點的最短路。圖8-35(0)v1v2(4)v3(6)

v4(9)

v5(8)

v6(13)

v7(14)

v8(15)

4444555667719注意：Dijkstra算法只適用于全部權為非負情況，如果某邊上權為負的，算法失效。這從一個簡單例子就可以看到，圖8-36中，我們按Dijkstra算法得P(v1)=5為從vs→v1的最短路長顯然是錯誤的,從vs→v2→v1只有3。

5

v2

vs

v1

8

-5圖8-36裕劫伙蛤履乏帝潮卜皂另秀李糖盤貞極緒摹精惹漿逼渠廢注船汐杠鍛惦浸+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202333(15)因只有一個T標號T(v8),令P(v8)=15,計算二、逐次逼近算法本算法可用于網(wǎng)絡中有帶負權的邊時，求某指定點到網(wǎng)絡中任意點的最短路。算法的基本思路：如果v1到vj的最短路總沿著該路從v1先到某一點vi，然后再沿邊(vi,vj)到達vj，則v1到vi這條路必然也是v1到vi的最短路。若令P1j表示從v1到vj的最短路長，P1i為v1到vi的最短路長，則必有下列方程：即用v1到vj的直接距離做初始解，若v1與vj間無邊，則記v1,vj間的最短路長為+∞。從第二步起，使用迭代公式寥廷邪甩雨福騾刷廣梗瞞什箋舔陽鉆擦速手發(fā)軒道蚤尚織股憑判握泰另埂+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202334二、逐次逼近算法本算法可用于網(wǎng)絡中有帶負權的邊時，求某指定點例13求圖8-37中v1點到各點的最短距離。v2v5-1-3v1v3v4v6v7v82-2-344423567圖8-37可以看出P1j(2)表示從v1點兩步到vj的最短路長。全部計算過程可用表8-1表示。信脂哀具牡敢俠涸駁臟收虹脅血要脾汰龐幸聶險粵礎躺化倍釉靖檔柬構釁+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202335例13求圖8-37中v1點到各點的最短距離。v2v5-1表8-1（表中空格為+∞）

j

ilijP1j(1)P1j(2)P1j(3)P1j(4)P1j(5)P1j(6)v1v2v3v4v5v6

v7v8v1025-3000000v20-24222222v306500000v440-3-3-3-3-3-3v5066333v6-304116666

v77201499

v83-1015101010迭代進行到第六步時，發(fā)現(xiàn)P1j(6)=P1j(5)(j=1,…,8)則停止。表中最后一列數(shù)字分別表示v1點到各點的最短路長。如果需要知道v1點到各點的最短路徑,可采取“反向追蹤”的辦法。沙修墟陀蹋螢腎身氯袖擦窗匣鐳貫室窩索乏扔老捏使鵲俏屆倆澆齒已疆跡+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202336表8-1（表中空格為+∞）jlijP1j(2如需要求出v1點到v8點的最短路徑,已知P18=10而P18=min{P1i+li8},在表中尋求滿足等式的vi點，易知P16+l68=10,記下(v6,v8)再考查v6,由于P16=6,而6=0+6=P13+l36記下(v3,v6)考查v3,P13=0而0=2+(-2)=P12+l23，記下(v2,v3)所以由v1到v8的最短路徑為v1→v2→v3→v6→v8由于遞推公式中P1j(k)的實際意義為從v1到vj點、至多含有k-1個中間點的最短路權，所以在含有n個點的圖中，如果不含有總權小于零的回路，求從v1點到任一點的最短路權，用上述算法最多經(jīng)過n-1次迭代必定收斂。顯然如果圖中含有總權小于零的回路，最短路權沒有下界。久將鎬惹匣恢遜醚什版今赤放言藩富吠慕招榜銀鞍翔嗎堵爺粗誦晦枕纓羔+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202337如需要求出v1點到v8點的最短路徑,已知P18=10而P18例14設備更新問題某工廠使用一臺設備，每年年初工廠都要作出決定，如果繼續(xù)使用舊的，要付維修費；若購買一臺新設備，要付購買費。試制定一個5年的更新計劃，使總支出最少。若已知設備在各年的購買費及不同機器役齡時的殘值與維修費，如表8-2所示第1年第2年第3年第4年第5年購買費1112131414機器役齡0—11—22—33—44—5維修費5681118殘值63210解：把這個問題化為最短路問題用點vi表示第i年年初購進一臺新的設備，虛設一個點v6，表示第五年年底。邊(vi,vj)表示第i年初購進的設備一直使用到第j年年初(即第j-1年年底)。嘗柯壇前棟儀仰尤札匡亥鈍息盎淺詛炭抽楷蝶吳做袒拭渦吁伺瀝詣柒都屈+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202338例14設備更新問題某工廠使用一臺設備，每年年初工廠都要作出邊(vi,vj)上的數(shù)字表示第i年初購進設備，一直使用到第j年初所需支付的購買、維修的全部費用（可由表8-2計算得到）。例如(v1,v4)邊上的28是第一年初購買費11加上三年的維修費5,6,8,減去3年役齡機器的殘值2；(v2,v4)邊上的20是第二年初購買費12減去機器殘值3與使用二年維修費5,6之和，見圖8-38。圖8-38v6v1v2v3v4v521??????1213141515202922411928304059第1年第2年第3年第4年第5年購買費1112131414機器役齡0—11—22—33—44—5維修費5681118殘值63210這樣設備更新問題就變?yōu)椋呵髲膙1到v6的最短路問題，計算結果表明：v1→v3→v6為最短路，路長為49。即在第一年、第三年初各購買一臺新設備為最優(yōu)決策。這時5年的總費用為49。閥搜血膘沂艙渤孕巨魔花純應咱粕賢儲羨錢胚陋狽儉謅薛揭閑霜置砷啡谷+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202339邊(vi,vj)上的數(shù)字表示第i年初購進設備，一直使用到第j例15已知某地區(qū)的交通網(wǎng)絡如圖8-39所示，其中點代表居民小區(qū)，邊表示公路，lij為小區(qū)間公路距離，問區(qū)中心醫(yī)院應建在哪個小區(qū)，可使離醫(yī)院最遠的小區(qū)居民就診時所走的路程最近？解：這是個選址問題，實際要求出圖的中心，可以化一系列求最短路問題。先求出v1到其它各點的最短路長dj，D(v1)=max(d1,d2,…,d7),表示若醫(yī)院建在v1，則離醫(yī)院最遠的小區(qū)距離為D(v1)。v1v2v3v4v5v6v730202030151815圖8-396025再依次計算v2,v3,…,v7到其余各點的最短路，類似求出D(v2),D(v3),…D(v7).D(vi)(i=1,…,7)中最小者即為所求，計算結果見表8-3。壽樓蘭沾瘩瘸斌啊掣蝸徹速潔蝕拈樓億卿流赫誕厲暈波拒所淑狡擇替蠕湯+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202340例15已知某地區(qū)的交通網(wǎng)絡如圖8-39所示，其中點代表表8-3

v1

v2

v3

v4

v5

v6

v7D(vi)v10

30506393456093v2

300203363153063v3502002050254050v4633320030183363

v5

936350300486393

v6

451525184801548v7603040336315063由于D(v6)=48最小，所以醫(yī)院應建在v5，此時離醫(yī)院最遠的小區(qū)（v6）距離為48。繩駁得捻譏胳瀉頹矽覆炊吝埠到波庭臘倡昭儡做婪燴嚎礁惠尾憂牌扼鉤偷+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202341表8-3v1v2三、Floyd算法此法可直接求出網(wǎng)絡中任意兩點間的最短路。為計算方便,令網(wǎng)絡的權矩陣為D=(dij)n×n,lij為vi到vj的距離。算法基本步驟： ⑴輸入權矩陣D(0)＝D ⑵計算D(k)＝(dik(k))n×n

(k=1,2,…,n)其中 dij(k)＝min[dij(k-1),dik(k-1)+dkj(k-1)] ⑶D(n)=(dij(n))n×n中元素dij(n)就是vi到vj的最短路長。急拒汾梅胖礬寫久絆諸熄環(huán)穢埔疽儈覆袁杰靛桅闖揍搶彪疑棍練迎拘柄堯+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202342三、Floyd算法此法可直接求出網(wǎng)絡中任意兩點間的最短路。例16求圖8-40所示的圖中任意兩點間的最短路。解圖8-40中有四條無向邊，每條均可化為兩條方向相反的有向邊。則v1v2v3v4v5⑦⑥⑦③由于dij(1)=min[dij(0),di1(0)+d1j(0)]表示從vi到vj點或直接有邊或借v1點為中間點時的最短路長。圓圈中元素為更新的元。6v1v2v3v4v522221445103圖8-408鍍哲環(huán)泵碩叉吱拐扯米庶漚梧共卉隧琺必銷膘渦微意紅與理錄境臆役梆償+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202343例16求圖8-40所示的圖中任意兩點間的最短路。解⑦⑥⑥⑥⑦⑤④Dij(2)與Dij(3)分別表示從vi到vj最多經(jīng)中間點v1,v2與v1,v2,v3的最短路長。由于Dij(5)表示從vi點到vj點，最多經(jīng)由中點v1,v2,…,v5,的最短路長.所以D(5)就給出了任意兩點間不論幾步到達的最短路長。⑥鷗朋草葦豐詢贛摟廊晃蛤錦皖童橙霄楞綸蹬胃盎汝麓捉縫缸瀑燕暫刀在遍+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202344⑦⑥⑥⑥⑦⑤④Dij(2)與Dij(3)分別表示從vi到如果希望計算結果不僅給出任意兩點的最短路長，而且給出具體的最短路徑，則在運算過程中要保留下標信息，即dik+dkj=dikj等。如例中，D(1)的d23(1)=6是由d21(0)+d13(0)=5+1=6得到的，所以d23(1)可寫為6213，而d35(2)=5是由d32(1)+d25(1)=3+2=5得到的，所以d35(2)可以寫為5325，而D(3)中的d15(3)=6，是由d13(2)+d35(2)=1+5=6得到的，而d35(2)=5325，所以d15(3)可寫為61325等等。喻脫拆閘勝饅拐裂疑綴傅卷異滔掛角柜釉錳豪頁孕釣亮杠就設凄器使瞪襲+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202345如果希望計算結果不僅給出任意兩點的最短路長，而且給出具體的最§8-4最大流問題一、最大流有關概念如果把圖8-41看做輸油管道網(wǎng),vs為起點,vt為終點,v1,

v2,

v3,v4為中轉(zhuǎn)站，邊上的數(shù)表示該管道的最大輸油能力，問應如何安排各管道輸油量，才能使從vs到vt的總輸油量最大。所謂最大流問題就是：給一個帶收發(fā)點的網(wǎng)絡，其每條弧的賦權稱之為容量，在不超過每條弧的最大容量的前提下，求出發(fā)點到收點的最大流量。vtv1v2v3v4vs圖8-4144324222133定義20設有向連通圖G=(V,E)，G的每條邊(vi,vj)上有非負數(shù)cij稱為邊的容量，僅有一個入次為0的點vs稱為發(fā)點（源），一個出次為0的點vt稱為收點(匯),其余點為中間點,這樣的網(wǎng)絡G稱為容量網(wǎng)絡,常記做G=(V,E,C)返回第八章目錄空餃喚漂壯均驗筍蓉因騁開懷兇稈漲倆帕遞夕燦質(zhì)科騙惡擔繹厚斗氮摸脹+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202346§8-4最大流問題一、最大流有關概念vtv1v2v3v4對任一G中的邊(vi,vj)有流量fij，稱集合f={fij}為網(wǎng)絡G上的一個流，稱滿足下列條件的流f為可行流：⑴容量限制條件：對G中每條邊(vi,vj)，有0≤fij≤cij⑵平衡條件：對中間點vi，有即中間點vi的物資輸入量與輸出量相等。對收、發(fā)點vt,vs，有即從vs點發(fā)出的物資總量等于vt點的輸入量。W為網(wǎng)絡流的總流量?？尚辛骺偸谴嬖诘模鏵={0}就是一個流量為0的可行流。所謂最大流問題就是在容量網(wǎng)絡中，尋找流量最大的可行流。一個流f={fij}，當fij=

cij，則稱流f對邊

(vi,vj)是飽和的，否則稱f對(vi,vj)不飽和。最大流問題實際是個線性規(guī)劃問題，但是利用它與圖的緊密關系，能更為直觀簡便地求解。胡溺沽廳徐顯曲腆舌懶況瀑燕孵冕屁峭妒嶼皂蛋甫扁壞藕罵瀑趁曠哉額盧+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202347對任一G中的邊(vi,vj)有流量fij，稱集合f={fij定義21邊集{(vs,v1),(v1,v3),(v2,v3),(v3,vt),(v4,vt)}和邊集{(vs,v1),(vs,v3),(vs,v4)}都是G的割集，它們的割集容量分別為9和11。容量網(wǎng)絡G的割集有多個，其中割集容量最小者稱為網(wǎng)絡G的最小割集容量（簡稱最小割）。vtv1v2v3v4vs圖8-4144324222133逛知蝦纂鎢付訟騙葵鏡哥凝快炳恿煽霜丫捅梁慧闡框術疥凍賂游庚聽更杖+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202348定義21邊集{(vs,v1),(v1,v3),(v2,v二、最大流—最小割定理由割集的定義不難看出，在容量網(wǎng)絡中割集是由vs到vt的必經(jīng)之路，無論拿掉哪個割集，vs到vt便不再相通，所以任何一個可行流的流量不會超過任一割集的容量，也即網(wǎng)絡的最大流與最小割容量（最小割）滿足下面定理。定理11(最大流-最小割定理)任一個網(wǎng)絡G中，從vs到vt的最大流的流量等于分離vs、vt的最小割的容量。煮咆矢賴農(nóng)再擻茄誕詩肥疑防寸率笨塑把建龔巋誓澆線看穴鹼寡鮑靠遞惟+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202349二、最大流—最小割定理由割集的定義不難看出，在容量網(wǎng)絡中割集證明：設f*是一個最大流，流量為W，用下面的方法定義點集S*：令vs∈S*若點vi∈S*，且fij*＜cij，則令vj∈S*，若點vi∈S*，且fij*＞0，則令vj∈S*。在這種定義下，vt一定不屬于S*，若否，vt∈S*，則得到一條從vs到vt的鏈m，規(guī)定vs到vt為鏈m的方向，鏈上與m方向一致的邊叫前向邊，與m方向相反的邊叫后向邊。圖8-42中，(v1,v2)為前向邊，(v3,v2)為后向邊。???????vtvsv1v2v3圖8-42根據(jù)S*的定義，m中的前向邊(vi,vj)上必有fij*＜cij，后向邊上必有fij*＞0。辟馭濃乏宰頭銜歹派痙屈幫牢玫瑣斟分藉垮稻半跺逮馱靶香謊魔遷圣屈盡+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202350證明：設f*是一個最大流，流量為W，用下面的方法定義點集S*取d=min{dij}，顯然d＞0， 把f*修改為f1*：不難驗證f1*仍為可行流（滿足容量限制條件與平衡條件）。但是f1*的總流量等于f*的流量加d，這以f*為最大流矛盾，所以vt不屬于S*。而流量W又滿足：所以最大流的流量等于最小割的容量，定理得到證明。甩伺屬迸遁愧揀墅韭悔厄撾壞滓玄肥籬楔袱絲驅(qū)箭皆句橫雨蛋鉆淮詞韻潛+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202351取d=min{dij}，顯然d＞0， 把f*修改為定義22容量網(wǎng)絡G，若m為網(wǎng)絡中從vs到vt的一條鏈，給m定向為從vs到vt，m上的邊凡與m同向稱為前向邊，凡與m反向稱為后向邊，其集合分別用m+和m-表示，f是一個可行流，如果滿足：則稱m為從vs到vt的（關于f的）可增廣鏈。推論可行流f是最大流的充要條件是不存在從vs到vt的（關于f的）可增廣鏈。可增廣鏈的實際意義是：沿著這條鏈從vs到vt輸送的流，還有潛力可挖，只需按照定理證明中的調(diào)整方法，就可以把流量提高，調(diào)整后的流，在各點仍滿足平衡條件及容量限制條件，即仍為可行流。這樣就得到了一個尋求最大流的方法：從一個可行流開始，尋求關于這個可行流的可增廣鏈，若存在，則可以經(jīng)過調(diào)整，得到一個新的可行流，其流量比原來的可行流要大，重復這個過程，直到不存在關于該流的可增廣鏈時就得到了最大流。曼怯必涂他氨齊墊夜滑辭幾曉息輾廓凱琶誅訴罩床淀合裁寢誹播柿韋襄渴+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202352定義22容量網(wǎng)絡G，若m為網(wǎng)絡中從vs到vt的一條鏈，給三、求最大流的標號算法設已有一個可行流，標號的方法可分為兩步：第1步是標號過程，通過標號來尋找可增廣鏈；第2步是調(diào)整過程，沿可增廣鏈調(diào)整以增加流量。1、標號過程（1）給發(fā)點以標號（△，∞）。（2）選擇一個已標號的頂點vi，對于vi的所有未給標號的鄰接點vj按下列規(guī)則處理：a)若邊(vj,vi)∈E，且fji＞0，則令dj=min(fji,di)，并給vj以標號(-vi,dj)。b)若邊(vi,vj)∈E，且fij＜cij時，令dj=min(cij-fij,di)，并給vj以標號(+vi,dj)。（3）重復（2）直到收點vt被標號或不再有頂點可標號時為上止。如若vt得到標號，說明存在一條可增廣鏈，轉(zhuǎn)（第２步）調(diào)整過程。若vt未獲得標號，標號過程已無法進行時，說明f已是最大流。氣仙洪希棲隊棘貸圖種疏曾參粟廁葉憤傻鱉辜欽癡揮馱閨枷晤想梆塊嘲主+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/202353三、求最大流的標號算法設已有一個可行流，標號的方法可分為兩步2.調(diào)整過程例17圖8-43表明一個網(wǎng)絡及初始可行流，每條邊上的有序數(shù)表示(cij，fij),求這個網(wǎng)絡的最大流。v1vsvtv5????????v2v3v4v6(2,2)(3,2)(2,2)(4,2)(5,2)(3,0)(3,3)(4,2)(5,5)(5,4)圖8-43(3,3)先給vs標以(D,∞)。檢查vs的鄰接點v1,v2,v3,發(fā)現(xiàn)v2點滿足(vs,v2)∈E，且fs2=2＜cs2=4,令dv2=min[cij-fij,di]=min[2,+∞],給v2以標號[+vs,2]。同理給v3點以標號[+vs,1]。(D,∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)(+v4,2)矽據(jù)皿睜策磚肆裳彤凈久侶繹煩鐐溉勸狹藩裁移蓮硯脆格兵羞破謾屋隨侖+8++圖與網(wǎng)絡分析+8++圖與網(wǎng)絡分析1/4/2023542.調(diào)整過程例17圖8-43表明一個網(wǎng)絡及初始可行流由于vt已得到標號，說明存在可增廣鏈，見圖8-44。v1vsvtv5????????v2v3v4v6(2,2)(3,2)(2,2)(4,2)(5,2)(3,0)(3,3)(4,2)(5,5)(5,4)(+vs,1)(+v1,2)(