第八章

圖與網(wǎng)絡(luò)分析第一節(jié)圖與網(wǎng)絡(luò)的基本知識(shí)第二節(jié)樹第三節(jié)最短路問題第四節(jié)最大流問題第五節(jié)最小費(fèi)用流問題講五節(jié)：3/14/20231§8-1圖與網(wǎng)絡(luò)的基本知識(shí)一、圖與網(wǎng)絡(luò)的基本概念1、圖及其分類圖是反映對(duì)象之間關(guān)系的一種工具。例如，在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這種關(guān)系可以用圖來(lái)表示。趙(v1)錢(v2)孫(v3)李(v4)周(v5)吳(v6)陳(v7)若將“相互認(rèn)識(shí)”的關(guān)系改成“認(rèn)識(shí)”，可以用帶箭頭的連線表示。頂點(diǎn)邊定義1

一個(gè)圖是由點(diǎn)集V={vi}和V中元素的無(wú)序?qū)Φ囊粋€(gè)集合E={ek}所構(gòu)成的二元組,記為G=(V,E),V中的元素vi叫做頂點(diǎn),E中的元素ek叫做邊。當(dāng)V，E為有限集合時(shí),G稱為有限圖,否則,稱為無(wú)限圖e1e2e3e4e5V={vi}={v1,v2,…,v7}E={ei}={e1,e2,…,e5}返回第八章目錄3/14/20232例1

在圖8-7中：

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

屬于E，如果它們有公共端點(diǎn)u，則稱ei,ej相鄰。邊ei,ej稱為u的關(guān)聯(lián)邊。對(duì)于任一條邊(vi,vj)屬于E，如果邊(vi,vj)端點(diǎn)無(wú)序，則它是無(wú)向邊，此時(shí)圖為無(wú)向圖.圖8-7是無(wú)向圖.如果邊(vi,vj)端點(diǎn)有序,即它表示以vi為始點(diǎn),vj為終點(diǎn)的有向邊(或稱弧),這時(shí)圖G稱為有向圖。一條邊的兩個(gè)端點(diǎn)如果相同,稱此邊為環(huán)(自回路).如圖8-7中的e1。兩個(gè)點(diǎn)之間多于一條邊的，稱為多重邊,如圖8-7中的e4,e5。其中：e1=(v1,v1)；e2=(v1,v2)；e3=(v1,v3)e4=(v2,v3)；e5=(v2,v3)；e6=(v3,v4)兩個(gè)點(diǎn)u,v屬于V,如果邊(u,v)屬于E,則稱u,v兩點(diǎn)相鄰。u,v稱為邊(u,v)的端點(diǎn)。e1v1e2v2e4e5v3v4e6v5圖8-7e33/14/20233定義4圖G＝(V,E)的點(diǎn)集V可以分為兩個(gè)非空子集X，Y，即XUY＝V,X∩Y＝f，使得E中每條邊的兩個(gè)端點(diǎn)必有一個(gè)端點(diǎn)屬于X，另一個(gè)端點(diǎn)屬于Y，則稱G為二部圖(偶圖)，有時(shí)記作G＝(X,Y,E)。例如圖8-9中的(a)是明顯的二部圖，點(diǎn)集X：{v1,v3,v5)，Y：{v2,v4,v6}，(b)也是二部圖，但是不像

(a)那樣明顯，改畫為(c)時(shí)可以清楚地看出。v1v2v6v5v3v4(a)v4v1v3v2(b)v1v2v4v3(c)圖8-93/14/202352.頂點(diǎn)的次

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

任何圖中，頂點(diǎn)次數(shù)的總和等于邊數(shù)的2倍。證明：由于每條邊必與兩個(gè)頂點(diǎn)關(guān)聯(lián)，在計(jì)算點(diǎn)的次時(shí)，每條邊均被計(jì)算了兩次，所以頂點(diǎn)次數(shù)的總和等于邊數(shù)的2倍。懸掛點(diǎn)懸掛邊孤立點(diǎn)奇點(diǎn)偶點(diǎn)偶點(diǎn)3/14/20236定理2

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

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

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

=(V′,E′)是G的一個(gè)子圖。特別地，若V′=V，則G′稱為G的生成子圖。3/14/20237二、連通圖e7v5v4v3v2v1v6e1e3e4e5e6e8e9e10e2圖8-12圖8-12中，S={v6,e6,v5,e7,v1,e8,v5,e7,v1,e9,v4,e4,v3}為一條連結(jié)v6,v3的鏈。S1={v6,e6,v5,e7,v1,e8,v5,e5,v4,e4,v3}為一條連結(jié)v6,v3的簡(jiǎn)單鏈。S2={v6,e6,v5,e5,v4,e4,v3}為初等鏈。定義9

無(wú)向圖G中,連結(jié)vi0與vik的一條鏈，當(dāng)vi0與vik是同一個(gè)點(diǎn)時(shí),稱此鏈為圈.圈中只有重復(fù)點(diǎn)而無(wú)重復(fù)邊者為簡(jiǎn)單圈，既無(wú)重復(fù)點(diǎn)也無(wú)重復(fù)邊者為初等圈，有向圖當(dāng)鏈(圈)上的邊方向相同時(shí),稱為道路(回路)。{v1,e7,v5,e8,v1,e9,v4,e10,v2,e2,v1}為一個(gè)圈。3/14/20239對(duì)于有向圖可以類似于無(wú)向圖定義鏈和圈，初等鏈、圈，簡(jiǎn)單鏈、圈，此時(shí)不考慮邊的方向。而當(dāng)鏈（圈）上的邊方向相同時(shí)，稱為道路（回路）。圖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}為一個(gè)圈。S3={v1,e2

,v2

,e10

,v4

,e5

,v5

,e7,v1}為一個(gè)回路。e7v5v4v3v1v6v2e10e11e3e2e5e9e8e1e6圖8-13e4定義10一個(gè)圖中任意兩點(diǎn)間至少有一條鏈相連，則稱此圖為連通圖。任何一個(gè)不連通圖都可以分為若干個(gè)連通子圖，每一個(gè)連通子圖稱為原圖的一個(gè)分圖。3/14/202310三、圖的矩陣表示定義11網(wǎng)絡(luò)(賦權(quán))圖G=(V,E),其邊(vi,vj)有權(quán)wij，構(gòu)造矩陣A=(aij)nn，其中例2圖示8-14所示的圖其權(quán)矩陣為：稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。6v5v4v3v2v1754238圖8-1494v1v1v2v3v4v5v2v4v53/14/202311四、歐拉回路與中國(guó)郵路問題1.歐拉回路與道路定義13連通圖G中，若存在一條道路，經(jīng)過每邊一次且僅一次，則稱這條路為歐拉道路。若存在一條回路，經(jīng)過每邊一次且僅一次，則稱這條回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖（E圖）。定理3

無(wú)向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中無(wú)奇點(diǎn)。推論1無(wú)向連通圖G為歐拉圖，當(dāng)且僅當(dāng)G的邊集可劃分為若干個(gè)初等回路。推論2無(wú)向連通圖G有歐拉道路，當(dāng)且僅當(dāng)G中恰有兩個(gè)奇點(diǎn)。定理4

連通有向圖G是歐拉圖，當(dāng)且僅當(dāng)它每個(gè)頂點(diǎn)的出次等于入次。連通有向圖G有歐拉道路，當(dāng)且僅當(dāng)這個(gè)圖中除去兩個(gè)頂點(diǎn)外，其余每一個(gè)頂點(diǎn)的出次等于入次，且這兩個(gè)頂點(diǎn)中，一個(gè)頂點(diǎn)的入次比出次多1，另一個(gè)頂點(diǎn)的入次比出次少1。3/14/2023132.中國(guó)郵路問題一個(gè)郵遞員，負(fù)責(zé)某一地區(qū)的信件投遞。他每天要從郵局出發(fā)，走遍該地區(qū)所有街道再返回郵局，問應(yīng)如何安排送信的路線可以使所走的總路程最短？國(guó)際上通稱這個(gè)問題為中國(guó)郵路問題。用圖論的語(yǔ)言描述：給定一個(gè)連通圖，每邊有非負(fù)權(quán)l(xiāng)(e)，要求一條回路過每邊至少一次，且滿足總權(quán)最小。中國(guó)郵路問題也可以轉(zhuǎn)為如下問題：在連通圖G=(V,E)中，求一個(gè)邊集E1∈E，把G中屬于E1的邊均變?yōu)槎剡叺玫綀DG*=G+E1，使其滿足G*無(wú)奇點(diǎn),且L(E1)=Sl(e)(e∈E1)最小。定理5

己知圖G*=G+E1無(wú)奇點(diǎn),則L(E1)=Sl(e)(e∈E1)最小的充分必要條件為：（1）每條邊最多重復(fù)一次；（2）對(duì)圖G中每個(gè)初等圈來(lái)講，重復(fù)邊的長(zhǎng)度和不超過圈長(zhǎng)的一半。定理給出了中國(guó)郵路問題的一種算法，稱為“奇偶點(diǎn)圖上作業(yè)法”，下面舉例說(shuō)明這個(gè)算法。3/14/202314例4求解圖8-16所示網(wǎng)絡(luò)的中國(guó)郵路問題第一步：確定初始可行方案。先檢查圖中是否有奇點(diǎn)，如無(wú)奇點(diǎn)則己是歐拉圖，找出歐拉回路即可。如有奇點(diǎn)，由前知奇點(diǎn)個(gè)數(shù)必為偶數(shù)，所以可以兩兩配對(duì)。每對(duì)點(diǎn)間選一條路，使這條路上均為二重邊。圖8-16中有四個(gè)奇點(diǎn)v2,v4,v6,v8，將v2與v4,v6,v8配對(duì)，聯(lián)結(jié)v2與v4的路有好幾條，任取一條，如{v2,v3,v6,v9,v8,v7,v4}，類似地，對(duì)v6與v8取{v6,v3,v2,v1,v4,v7,v8}。得到圖8-17，已是歐拉圖。對(duì)應(yīng)這個(gè)可行方案，重復(fù)邊的總長(zhǎng)為：2l23+2l36+l69+l98+2l87+2l74+l41+l12=51v3v1v2v6v9v8v7v4v5圖8-17v3v1v2v6v9v8v7v4v524344955644圖8-1633/14/202315再檢查圖8-19，圈{v2v3v6v9v8v5v2}總長(zhǎng)度為24，而重復(fù)邊長(zhǎng)為13。再次調(diào)整得圖8-20，重復(fù)邊總長(zhǎng)度為15。檢查圖8-20,條件(1),(2)均滿足，得到最優(yōu)方案。圖中任一歐拉回路即為最優(yōu)郵遞路線。v3v1v2v6v9v8v7v4v52434495544圖8-20v3v1v2v6v9v8v7v4v544335599圖8-1864v3v1v2v6v9v8v7v4v52434495546圖8-1943/14/202317§8-2 樹一、樹的概念和性質(zhì) 例5乒乓球單打比賽抽簽后,可用圖來(lái)表示相遇情況,如圖8-21所示。

ECGKABDFHIJLMN運(yùn)動(dòng)員圖8-21銷售科檢驗(yàn)科新產(chǎn)品開發(fā)科技術(shù)科生產(chǎn)科設(shè)備科供應(yīng)科動(dòng)力科人事科總工程師財(cái)務(wù)科生產(chǎn)副廠長(zhǎng)經(jīng)營(yíng)副廠長(zhǎng)圖8-22廠長(zhǎng)定義14不含圈的無(wú)向連通圖稱為樹。樹中次為1的點(diǎn)稱為樹葉，次大于1的點(diǎn)稱為分枝點(diǎn)。例6某企業(yè)的組織結(jié)構(gòu)可用圖8-22表示樹葉分枝點(diǎn)樹返回第八章目錄3/14/202318定理6

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

圖8-23樹枝弦3/14/202319圖8-24740261012813591113(b)012345698101112137(a)(2)廣探法步驟如下：①在點(diǎn)集V中任取一點(diǎn)v,給v以標(biāo)號(hào)0。②令所有標(biāo)號(hào)為i的點(diǎn)集為Vi，檢查[Vi，V\Vi]中的邊端點(diǎn)是否均已標(biāo)號(hào)。對(duì)所有未標(biāo)號(hào)之點(diǎn)均標(biāo)以i+1，記下這些邊。③對(duì)標(biāo)號(hào)為i+1的點(diǎn)重復(fù)步驟②。直到全部點(diǎn)得到標(biāo)號(hào)為止。圖8-25(a)中粗線邊就是用廣探法生成的樹，也可表示為圖8-25(b)圖8-254211112222333(b)02343201122211(a)33/14/202321例7一個(gè)鄉(xiāng)有9個(gè)自然村，其間道路如圖8-26(a)所示，要以v0村為中心建有線廣播網(wǎng)絡(luò)，如要求沿道路架設(shè)廣播線，應(yīng)如何架設(shè)？2.破圈法在圖G中任意取一個(gè)圈,從圈上任意舍棄一條邊，將這個(gè)圈破掉,重復(fù)這個(gè)步驟直到圖G中沒有圈為止。v6v1v2v3v4v5v7v8v0(b)(a)v6v1v2v3v4v5v7v8v0圖8-26解：用破圈法，任取一圈(v1,v2,v2,v1)，從中去掉邊(v1,v2)，再選圈(v1,v8,v0,v1)去掉邊(v1,v8)，…，依同樣方法進(jìn)行，直到無(wú)圈。圖8-26(b)就是一種方案?！痢痢痢痢痢痢痢?/14/202322321三、最小生成樹問題定義16

連通圖G=(V,E)，每條邊上有非負(fù)權(quán)L(e)。一棵生成樹所有樹枝上權(quán)的總和，稱為這個(gè)生成樹的權(quán)。具有最小權(quán)的生成樹稱為最小生成樹，簡(jiǎn)稱最小樹。最小樹的兩種算法算法1：(Kruskal算法)此法類似于求生成樹的“避圈法”，步驟如下：每步從未選的邊中選取邊e，使它與已選邊不構(gòu)成圈，且e是未選邊中的最小權(quán)邊，直到選夠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)=53/14/202323定義19在根樹中,若每個(gè)頂點(diǎn)的出次小于或等于m,稱這棵樹為m叉樹,若每個(gè)頂點(diǎn)的出次恰好等于m或零,則稱這棵樹為完全m叉樹。當(dāng)m=2時(shí)，稱為二叉樹、完全二叉樹。圖8-29所示的樹是根樹，其中v1為根，v1,v2,v3,v4,v8為分枝點(diǎn)，其余各點(diǎn)為葉，頂點(diǎn)v2,v3,v4的層次為1,頂點(diǎn)v11的層次為3等等。圖8-29??????v11v1v2v3v4v5v6v7v8v9v10??????(a)?(b)?????圖8-30例如圖8-30中(a)為完全三叉樹、(b)為四叉樹。實(shí)際問題中常討論葉子上帶權(quán)的二叉樹,令有s個(gè)葉子的二叉樹T各葉子的權(quán)分別為pi,根到各葉子的距離(層次)為li(i=1,…,s),這樣二叉樹的總權(quán)數(shù)：3/14/2023254??????122333滿足總權(quán)最小的二叉樹稱為最優(yōu)二叉樹(霍夫曼樹）。算法步驟為：⑴將s個(gè)葉子按權(quán)由小至大排序,不失一般性，設(shè)p1≤p2≤…≤ps。⑵將二個(gè)具有最小權(quán)的葉子合并成一個(gè)分枝點(diǎn)，其權(quán)為p1+p2,將新的分枝點(diǎn)作為一個(gè)葉子。令s←s-1，若s=1停止，否則轉(zhuǎn)(1)。例9s=6其權(quán)分別為4,3,3,2,2,1,求最優(yōu)二叉要樹。解：該樹構(gòu)造過程見圖8-31?？倷?quán)為1×4+2×4+2×3+3×2+3×2+4×2=38圖8-31??????1223334569??????122333456915421?????233356此算法得到的樹為最優(yōu)二叉樹，直觀意義：葉子的距離是依權(quán)的遞減而增加，所以總權(quán)最小。3/14/202326§8-3最短路問題設(shè)G=(V,E)為連通圖，圖中各邊(vi,vj)有權(quán)l(xiāng)ij(lij=∞表示vi,vj間無(wú)邊)，vs,vt為圖中任意兩點(diǎn)，求一條道路m，使它是從vs到vt的所有路中總權(quán)最小的路。即有些最短路問題也可以是求網(wǎng)絡(luò)中某指定點(diǎn)到其余所有結(jié)點(diǎn)的最短路，或求網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路。一、Dijkstra算法

基本步驟，采用標(biāo)號(hào)法。可用兩種標(biāo)號(hào)：T標(biāo)號(hào)與P標(biāo)號(hào)，T標(biāo)號(hào)為試探性標(biāo)號(hào)，P為永久性標(biāo)號(hào)，給vi點(diǎn)一個(gè)P標(biāo)號(hào)時(shí)，表示從vs到vi點(diǎn)的最短路權(quán)，vi點(diǎn)的標(biāo)號(hào)不再改變。給vi點(diǎn)一個(gè)T標(biāo)號(hào)時(shí)，表示從vs到vi點(diǎn)的估計(jì)最短路權(quán)的上界，是一種臨時(shí)標(biāo)號(hào)，凡沒有得到P標(biāo)號(hào)的點(diǎn)都有T標(biāo)號(hào)。算法每一步都把某一點(diǎn)的T標(biāo)號(hào)改為P標(biāo)號(hào)，當(dāng)終點(diǎn)vt得到P標(biāo)號(hào)時(shí)，全部計(jì)算結(jié)束。對(duì)于有n個(gè)頂點(diǎn)的圖，最多經(jīng)n-1步就可以得到從始點(diǎn)到終點(diǎn)的最短路。返回第八章目錄3/14/202329Dijkstra算法步驟：(1)給vs以P標(biāo)號(hào)，P(vs)=0，其余各點(diǎn)均給T標(biāo)號(hào)T(vi)=+∞。(2)若vi點(diǎn)為剛得到標(biāo)號(hào)的點(diǎn)，考慮這樣的點(diǎn)vj：(vi,vj)屬于E，且vj為T標(biāo)號(hào)。對(duì)vj的標(biāo)號(hào)進(jìn)行如下的更改：T(vj)=min[T(vj),P(vi)+lij](3)比較所有具有T標(biāo)號(hào)的點(diǎn)，把最小者改為P標(biāo)號(hào)，即：當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號(hào)。若全部點(diǎn)均為P標(biāo)號(hào)則停止。否則用代vi轉(zhuǎn)回（2）。￣vP(vi)＝min[T(vi)]￣3/14/202330例12用Dijkstra算法求圖8-34中v1點(diǎn)到v8點(diǎn)的最短路。圖8-34

v1

v2

v3

v4

v5

v6

v7

v84444555667719

解：(1)首先給v1以P標(biāo)號(hào)，P(v1)=0，給其余所有點(diǎn)T標(biāo)號(hào)，T(vi)=+∞(i=2,…,8)(2)由于(v1,v2),(v1,v3)邊屬于E,且為T標(biāo)號(hào),所以修改這兩個(gè)點(diǎn)的標(biāo)號(hào)： 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標(biāo)號(hào),T(v2)最小,所以令P(v2)=4。(4)v2為剛得到P標(biāo)號(hào)的點(diǎn),考察邊(v2,v4),(v2,v5)的端點(diǎn)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標(biāo)號(hào),T(v3)最小,所以令P(v3)=6。(6)考慮點(diǎn)v3，有3/14/202331 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標(biāo)號(hào)中,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標(biāo)號(hào)中,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標(biāo)號(hào)中,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標(biāo)號(hào)中,T(v7)最小,令P(v7)=14(14)考察v7,

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

3/14/202332(15)因只有一個(gè)T標(biāo)號(hào)T(v8),令P(v8)=15,計(jì)算結(jié)束。全部計(jì)算結(jié)果見圖8-35。v1到v8之最短路為v1→v2→v5→v7→v8路長(zhǎng)p(v8)=15，同時(shí)得到v1點(diǎn)到其余各點(diǎn)的最短路。圖8-35(0)v1v2(4)v3(6)

v4(9)

v5(8)

v6(13)

v7(14)

v8(15)

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

5

v2

vs

v1

8

-5圖8-363/14/202333二、逐次逼近算法本算法可用于網(wǎng)絡(luò)中有帶負(fù)權(quán)的邊時(shí)，求某指定點(diǎn)到網(wǎng)絡(luò)中任意點(diǎn)的最短路。算法的基本思路：如果v1到vj的最短路總沿著該路從v1先到某一點(diǎn)vi，然后再沿邊(vi,vj)到達(dá)vj，則v1到vi這條路必然也是v1到vi的最短路。若令P1j表示從v1到vj的最短路長(zhǎng)，P1i為v1到vi的最短路長(zhǎng)，則必有下列方程：即用v1到vj的直接距離做初始解，若v1與vj間無(wú)邊，則記v1,vj間的最短路長(zhǎng)為+∞。從第二步起，使用迭代公式3/14/202334例13求圖8-37中v1點(diǎn)到各點(diǎn)的最短距離。v2v5-1-3v1v3v4v6v7v82-2-344423567圖8-37可以看出P1j(2)表示從v1點(diǎn)兩步到vj的最短路長(zhǎng)。全部計(jì)算過程可用表8-1表示。3/14/202335表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迭代進(jìn)行到第六步時(shí)，發(fā)現(xiàn)P1j(6)=P1j(5)(j=1,…,8)則停止。表中最后一列數(shù)字分別表示v1點(diǎn)到各點(diǎn)的最短路長(zhǎng)。如果需要知道v1點(diǎn)到各點(diǎn)的最短路徑,可采取“反向追蹤”的辦法。3/14/202336如需要求出v1點(diǎn)到v8點(diǎn)的最短路徑,已知P18=10而P18=min{P1i+li8},在表中尋求滿足等式的vi點(diǎn)，易知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)的實(shí)際意義為從v1到vj點(diǎn)、至多含有k-1個(gè)中間點(diǎn)的最短路權(quán)，所以在含有n個(gè)點(diǎn)的圖中，如果不含有總權(quán)小于零的回路，求從v1點(diǎn)到任一點(diǎn)的最短路權(quán)，用上述算法最多經(jīng)過n-1次迭代必定收斂。顯然如果圖中含有總權(quán)小于零的回路，最短路權(quán)沒有下界。3/14/202337例14設(shè)備更新問題某工廠使用一臺(tái)設(shè)備，每年年初工廠都要作出決定，如果繼續(xù)使用舊的，要付維修費(fèi)；若購(gòu)買一臺(tái)新設(shè)備，要付購(gòu)買費(fèi)。試制定一個(gè)5年的更新計(jì)劃，使總支出最少。若已知設(shè)備在各年的購(gòu)買費(fèi)及不同機(jī)器役齡時(shí)的殘值與維修費(fèi)，如表8-2所示第1年第2年第3年第4年第5年購(gòu)買費(fèi)1112131414機(jī)器役齡0—11—22—33—44—5維修費(fèi)5681118殘值63210解：把這個(gè)問題化為最短路問題用點(diǎn)vi表示第i年年初購(gòu)進(jìn)一臺(tái)新的設(shè)備，虛設(shè)一個(gè)點(diǎn)v6，表示第五年年底。邊(vi,vj)表示第i年初購(gòu)進(jìn)的設(shè)備一直使用到第j年年初(即第j-1年年底)。3/14/202338邊(vi,vj)上的數(shù)字表示第i年初購(gòu)進(jìn)設(shè)備，一直使用到第j年初所需支付的購(gòu)買、維修的全部費(fèi)用（可由表8-2計(jì)算得到）。例如(v1,v4)邊上的28是第一年初購(gòu)買費(fèi)11加上三年的維修費(fèi)5,6,8,減去3年役齡機(jī)器的殘值2；(v2,v4)邊上的20是第二年初購(gòu)買費(fèi)12減去機(jī)器殘值3與使用二年維修費(fèi)5,6之和，見圖8-38。圖8-38v6v1v2v3v4v521??????1213141515202922411928304059第1年第2年第3年第4年第5年購(gòu)買費(fèi)1112131414機(jī)器役齡0—11—22—33—44—5維修費(fèi)5681118殘值63210這樣設(shè)備更新問題就變?yōu)椋呵髲膙1到v6的最短路問題，計(jì)算結(jié)果表明：v1→v3→v6為最短路，路長(zhǎng)為49。即在第一年、第三年初各購(gòu)買一臺(tái)新設(shè)備為最優(yōu)決策。這時(shí)5年的總費(fèi)用為49。3/14/202339例15已知某地區(qū)的交通網(wǎng)絡(luò)如圖8-39所示，其中點(diǎn)代表居民小區(qū)，邊表示公路，lij為小區(qū)間公路距離，問區(qū)中心醫(yī)院應(yīng)建在哪個(gè)小區(qū)，可使離醫(yī)院最遠(yuǎn)的小區(qū)居民就診時(shí)所走的路程最近？解：這是個(gè)選址問題，實(shí)際要求出圖的中心，可以化一系列求最短路問題。先求出v1到其它各點(diǎn)的最短路長(zhǎng)dj，D(v1)=max(d1,d2,…,d7),表示若醫(yī)院建在v1，則離醫(yī)院最遠(yuǎn)的小區(qū)距離為D(v1)。v1v2v3v4v5v6v730202030151815圖8-396025再依次計(jì)算v2,v3,…,v7到其余各點(diǎn)的最短路，類似求出D(v2),D(v3),…D(v7).D(vi)(i=1,…,7)中最小者即為所求，計(jì)算結(jié)果見表8-3。3/14/202340表8-3

v1

v2

v3

v4

v5

v6

v7D(vi)v10

30506393456093v2

300203363153063v3502002050254050v4633320030183363

v5

936350300486393

v6

451525184801548v7603040336315063由于D(v6)=48最小，所以醫(yī)院應(yīng)建在v5，此時(shí)離醫(yī)院最遠(yuǎn)的小區(qū)（v6）距離為48。3/14/202341三、Floyd算法此法可直接求出網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路。為計(jì)算方便,令網(wǎng)絡(luò)的權(quán)矩陣為D=(dij)n×n,lij為vi到vj的距離。算法基本步驟： ⑴輸入權(quán)矩陣D(0)＝D ⑵計(jì)算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的最短路長(zhǎng)。3/14/202342例16求圖8-40所示的圖中任意兩點(diǎn)間的最短路。解圖8-40中有四條無(wú)向邊，每條均可化為兩條方向相反的有向邊。則v1v2v3v4v5⑦⑥⑦③由于dij(1)=min[dij(0),di1(0)+d1j(0)]表示從vi到vj點(diǎn)或直接有邊或借v1點(diǎn)為中間點(diǎn)時(shí)的最短路長(zhǎng)。圓圈中元素為更新的元。6v1v2v3v4v522221445103圖8-4083/14/202343⑦⑥⑥⑥⑦⑤④Dij(2)與Dij(3)分別表示從vi到vj最多經(jīng)中間點(diǎn)v1,v2與v1,v2,v3的最短路長(zhǎng)。由于Dij(5)表示從vi點(diǎn)到vj點(diǎn)，最多經(jīng)由中點(diǎn)v1,v2,…,v5,的最短路長(zhǎng).所以D(5)就給出了任意兩點(diǎn)間不論幾步到達(dá)的最短路長(zhǎng)。⑥3/14/202344如果希望計(jì)算結(jié)果不僅給出任意兩點(diǎn)的最短路長(zhǎng)，而且給出具體的最短路徑，則在運(yùn)算過程中要保留下標(biāo)信息，即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等等。3/14/202345§8-4最大流問題一、最大流有關(guān)概念如果把圖8-41看做輸油管道網(wǎng),vs為起點(diǎn),vt為終點(diǎn),v1,

v2,

v3,v4為中轉(zhuǎn)站，邊上的數(shù)表示該管道的最大輸油能力，問應(yīng)如何安排各管道輸油量，才能使從vs到vt的總輸油量最大。所謂最大流問題就是：給一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的最大容量的前提下，求出發(fā)點(diǎn)到收點(diǎn)的最大流量。vtv1v2v3v4vs圖8-4144324222133定義20設(shè)有向連通圖G=(V,E)，G的每條邊(vi,vj)上有非負(fù)數(shù)cij稱為邊的容量，僅有一個(gè)入次為0的點(diǎn)vs稱為發(fā)點(diǎn)（源），一個(gè)出次為0的點(diǎn)vt稱為收點(diǎn)(匯),其余點(diǎn)為中間點(diǎn),這樣的網(wǎng)絡(luò)G稱為容量網(wǎng)絡(luò),常記做G=(V,E,C)返回第八章目錄3/14/202346對(duì)任一G中的邊(vi,vj)有流量fij，稱集合f={fij}為網(wǎng)絡(luò)G上的一個(gè)流，稱滿足下列條件的流f為可行流：⑴容量限制條件：對(duì)G中每條邊(vi,vj)，有0≤fij≤cij⑵平衡條件：對(duì)中間點(diǎn)vi，有即中間點(diǎn)vi的物資輸入量與輸出量相等。對(duì)收、發(fā)點(diǎn)vt,vs，有即從vs點(diǎn)發(fā)出的物資總量等于vt點(diǎn)的輸入量。W為網(wǎng)絡(luò)流的總流量?？尚辛骺偸谴嬖诘模鏵={0}就是一個(gè)流量為0的可行流。所謂最大流問題就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。一個(gè)流f={fij}，當(dāng)fij=

cij，則稱流f對(duì)邊

(vi,vj)是飽和的，否則稱f對(duì)(vi,vj)不飽和。最大流問題實(shí)際是個(gè)線性規(guī)劃問題，但是利用它與圖的緊密關(guān)系，能更為直觀簡(jiǎn)便地求解。3/14/202347定義21邊集{(vs,v1),(v1,v3),(v2,v3),(v3,vt),(v4,vt)}和邊集{(vs,v1),(vs,v3),(vs,v4)}都是G的割集，它們的割集容量分別為9和11。容量網(wǎng)絡(luò)G的割集有多個(gè)，其中割集容量最小者稱為網(wǎng)絡(luò)G的最小割集容量（簡(jiǎn)稱最小割）。vtv1v2v3v4vs圖8-41443242221333/14/202348二、最大流—最小割定理由割集的定義不難看出，在容量網(wǎng)絡(luò)中割集是由vs到vt的必經(jīng)之路，無(wú)論拿掉哪個(gè)割集，vs到vt便不再相通，所以任何一個(gè)可行流的流量不會(huì)超過任一割集的容量，也即網(wǎng)絡(luò)的最大流與最小割容量（最小割）滿足下面定理。定理11(最大流-最小割定理)任一個(gè)網(wǎng)絡(luò)G中，從vs到vt的最大流的流量等于分離vs、vt的最小割的容量。3/14/202349證明：設(shè)f*是一個(gè)最大流，流量為W，用下面的方法定義點(diǎn)集S*：令vs∈S*若點(diǎn)vi∈S*，且fij*＜cij，則令vj∈S*，若點(diǎn)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。3/14/202350取d=min{dij}，顯然d＞0， 把f*修改為f1*：不難驗(yàn)證f1*仍為可行流（滿足容量限制條件與平衡條件）。但是f1*的總流量等于f*的流量加d，這以f*為最大流矛盾，所以vt不屬于S*。而流量W又滿足：所以最大流的流量等于最小割的容量，定理得到證明。3/14/202351定義22容量網(wǎng)絡(luò)G，若m為網(wǎng)絡(luò)中從vs到vt的一條鏈，給m定向?yàn)閺膙s到vt，m上的邊凡與m同向稱為前向邊，凡與m反向稱為后向邊，其集合分別用m+和m-表示，f是一個(gè)可行流，如果滿足：則稱m為從vs到vt的（關(guān)于f的）可增廣鏈。推論可行流f是最大流的充要條件是不存在從vs到vt的（關(guān)于f的）可增廣鏈?？稍鰪V鏈的實(shí)際意義是：沿著這條鏈從vs到vt輸送的流，還有潛力可挖，只需按照定理證明中的調(diào)整方法，就可以把流量提高，調(diào)整后的流，在各點(diǎn)仍滿足平衡條件及容量限制條件，即仍為可行流。這樣就得到了一個(gè)尋求最大流的方法：從一個(gè)可行流開始，尋求關(guān)于這個(gè)可行流的可增廣鏈，若存在，則可以經(jīng)過調(diào)整，得到一個(gè)新的可行流，其流量比原來(lái)的可行流要大，重復(fù)這個(gè)過程，直到不存在關(guān)于該流的可增廣鏈時(shí)就得到了最大流。3/14/202352三、求最大流的標(biāo)號(hào)算法設(shè)已有一個(gè)可行流，標(biāo)號(hào)的方法可分為兩步：第1步是標(biāo)號(hào)過程，通過標(biāo)號(hào)來(lái)尋找可增廣鏈；第2步是調(diào)整過程，沿可增廣鏈調(diào)整以增加流量。1、標(biāo)號(hào)過程（1）給發(fā)點(diǎn)以標(biāo)號(hào)（△，∞）。（2）選擇一個(gè)已標(biāo)號(hào)的頂點(diǎn)vi，對(duì)于vi的所有未給標(biāo)號(hào)的鄰接點(diǎn)vj按下列規(guī)則處理：a)若邊(vj,vi)∈E，且fji＞0，則令dj=min(fji,di)，并給vj以標(biāo)號(hào)(-vi,dj)。b)若邊(vi,vj)∈E，且fij＜cij時(shí)，令dj=min(cij-fij,di)，并給vj以標(biāo)號(hào)(+vi,dj)。（3）重復(fù)（2）直到收點(diǎn)vt被標(biāo)號(hào)或不再有頂點(diǎn)可標(biāo)號(hào)時(shí)為上止。如若vt得到標(biāo)號(hào)，說(shuō)明存在一條可增廣鏈，轉(zhuǎn)（第２步）調(diào)整過程。若vt未獲得標(biāo)號(hào)，標(biāo)號(hào)過程已無(wú)法進(jìn)行時(shí)，說(shuō)明f已是最大流。3/14/2023532.調(diào)整過程例17圖8-43表明一個(gè)網(wǎng)絡(luò)及初始可行流，每條邊上的有序數(shù)表示(cij，fij),求這個(gè)網(wǎng)絡(luò)的最大流。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標(biāo)以(D,∞)。檢查vs的鄰接點(diǎn)v1,v2,v3,發(fā)現(xiàn)v2點(diǎn)滿足(vs,v2)∈E，且fs2=2＜cs2=4,令dv2=min[cij-fij,di]=min[2,+∞],給v2以標(biāo)號(hào)[+vs,2]。同理給v3點(diǎn)以標(biāo)號(hào)[+vs,1]。(D,∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)(+v4,2)3/14/202354由于vt已得到標(biāo)號(hào)，說(shuō)明存在可增廣鏈，見圖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)(+v4,2)(+v2,2)(+vs,2)(-v5,2)

(△,∞)圖8-44(3,3)(+vs,1)v1vsvtv5????????v2v3v4v6(2,2)(3,2)(2,2)(4,4)(5,4)(3,2)(3,3)(4,4)(5,5)(5,4)

(△,∞)圖8-45(3,1)3/14/202355重新開始標(biāo)號(hào)過程，尋找可增廣鏈，當(dāng)標(biāo)到v3點(diǎn)為[+vs,1]以后，與vs,v3點(diǎn)鄰接的v1,v2,v6點(diǎn)都不滿足標(biāo)號(hào)條件，所以標(biāo)號(hào)過程無(wú)法再繼續(xù)，而vt點(diǎn)并未得到標(biāo)號(hào)，如圖8-45。(+vs,1)v1vsvtv5????????v2v3v4v6(2,2)(3,2)(2,2)(4,4)(5,4)(3,2)(3,3)(4,4)(5,5)(5,4)

(△,∞)圖8-45(3,1)這時(shí)W=fs1+fs2+fs3

=f4t+f5t+f6t=11即為最大流的流量，算法結(jié)束。用標(biāo)號(hào)法在得到最大流的同時(shí)，可得到一個(gè)最小割。即如圖8-45中虛線所示。3/14/202356由此也可以體會(huì)到最小割的意義，網(wǎng)絡(luò)從發(fā)點(diǎn)到收點(diǎn)的各通路中，由容量決定其通過能力，最小割則是這些路中的咽喉部分，或者叫瓶頸，其容量最小，它決定了整個(gè)網(wǎng)絡(luò)的最大通過能力。要提高整個(gè)網(wǎng)絡(luò)的運(yùn)輸能力，必須首先改造這個(gè)咽喉部分的通過能力。求最大流的標(biāo)號(hào)算法還可用于解決多發(fā)點(diǎn)網(wǎng)絡(luò)的最大流問題，設(shè)容量網(wǎng)絡(luò)G有若干個(gè)發(fā)點(diǎn)x1,x2,…,xm;若干個(gè)收點(diǎn)y1,y2,…yn,可以添加兩個(gè)新點(diǎn)vs,vt，用容量為∞的有向邊分別連結(jié)vs與x1,x2,…,xm,y1,y2,…yn,與vt，得到新的網(wǎng)絡(luò)G′，G′為只有一個(gè)發(fā)點(diǎn)vs，一個(gè)收點(diǎn)vt的網(wǎng)絡(luò)，求解G′的最大流問題即可得到G的解，如圖8-46。xmynx1x2????????vty1y2vs+∞+∞………圖8-463/14/202357四、最大匹配問題考慮工作分配問題。有n個(gè)工人，m件工件，每個(gè)工人能力不同，各能勝任其中幾項(xiàng)工作。假設(shè)每件工作只需一人做，每人只做一件工作，怎樣分配才能使盡量多的工作有人做，更多的人有工作？這個(gè)問題可以用圖的語(yǔ)言描述，如圖8-47。其中x1,x2,…,xn表示工人，y1,y2,…ym表示工作，邊(xi,yj)表示第xi個(gè)人能勝任第yj項(xiàng)工作，這樣就得到了一個(gè)二部圖G，用點(diǎn)集X表示{x1,x2,…,xn}，點(diǎn)集y表示{y1,y2,…ym},得到一個(gè)二部圖G=(X,Y,E)。ymx1x2x3xny1y2y3……圖8-47上述的工作分配問題就是要在圖G中找一個(gè)邊集E的子集，使得集中任何兩條邊沒有公共端點(diǎn)，最好的方案就是要使此邊集的邊數(shù)盡可能多，這就是匹配問題。3/14/202358定義23二部圖G=(X,Y,E),M是邊集E的子集，若M中的任意兩條邊都沒有公共端點(diǎn)，則稱M為圖G的一個(gè)匹配（也稱對(duì)集）。M中任一條邊的端點(diǎn)v稱為（關(guān)于M的）飽和點(diǎn)，G中其它頂點(diǎn)稱為非飽和點(diǎn)。若不存在另一匹配M1，使得|M1|>|M|(|M|表示集合M中的邊數(shù)），則稱M為最大匹配。y1y2y3x1x2x3x4y5y4圖8-48例如圖8-48中用粗線標(biāo)出的各邊組成圖G的一個(gè)匹配M={(x1,y1),(x2,y5),(x3,y2),(x4,y3)}，且為最大匹配。圖8-48還有另一個(gè)最大匹配由邊(x1,y1),(x2,y5),(x3,y4),(x4,y3),組成。即一個(gè)圖的最大匹配中所含邊數(shù)是確定的，但匹配方案可以不同。3/14/202359例18設(shè)有5待業(yè)者，5項(xiàng)工作，他們各自能勝任工作情況如圖8-49所示，要求設(shè)計(jì)一個(gè)就業(yè)方案，使盡可能多的人能就業(yè)。解

按前述方法增加虛擬的發(fā)、收點(diǎn)vs,vt，用求最大流的標(biāo)號(hào)法求解得到圖8-49，在圖中略去容量，只標(biāo)出流量。邊(x1,y2),(x2,y1),(x3,y5),(x4,y4)上的流量都是1，所以讓x1,x2,x3,x5分別干y1,y2,y5,y4工作可得最大就業(yè)方案，即最多可以安排四個(gè)人就業(yè)。vt????????????x1x2x3x4x5y5y4y3y2y1vs11111111圖8-493/14/202360例19有5批貨物，要用船只從x1,x2地分別運(yùn)往y1,y2y3地。規(guī)定每批貨物出發(fā)日期如表8-4所示，又知船只航行所需時(shí)間（天）如表8-5所示。每批貨物只需一條船裝運(yùn)，船只在空載和重載時(shí)航行時(shí)間同，要求制定一個(gè)計(jì)劃，以最少的船只完成這5項(xiàng)運(yùn)輸任務(wù)。設(shè)ai、bi分別為每項(xiàng)運(yùn)輸任務(wù)的出發(fā)日期及完成日期(i=1,2,3,4,5)。則由表8-4和表8-5知：表8-4每批貨物的出發(fā)日期y1y1y3x1510/x2/121，8表8-5船只航行所需時(shí)間y1y1y3x1232x2112i任務(wù)aibi1

x1→y1572

x1→y2