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

運(yùn)籌學(xué)第十章圖與網(wǎng)絡(luò)分析第一頁(yè)，共四十三頁(yè)，編輯于2023年，星期三有向圖：由點(diǎn)及弧所構(gòu)成的圖，記為D=(V,A)，V,A分別是D的點(diǎn)集合和弧集合。一個(gè)方向是從vi指向vj的弧記為(vi,vj)圖G或D中的點(diǎn)數(shù)記為p(G)或p(D)，邊(弧)數(shù)記為q(G)(q(D))，簡(jiǎn)記為p,q。若邊e=[u,v]∈E，則稱u,v為e的端點(diǎn)，也稱u,v是相鄰的，稱e是點(diǎn)u(及點(diǎn)v)的關(guān)聯(lián)邊。若在圖G中，某個(gè)邊的兩個(gè)端點(diǎn)相同，則稱e是環(huán)。第二頁(yè)，共四十三頁(yè)，編輯于2023年，星期三若兩個(gè)點(diǎn)之間有多于一條的邊，稱這些邊為多重邊。簡(jiǎn)單圖：一個(gè)無(wú)環(huán)，無(wú)多重邊的圖。多重圖：一個(gè)無(wú)環(huán)、但允許有多重邊的圖。給定一個(gè)圖G=(V,E)，如果圖G’=(V’,E’)，使V’=V及E’E，則稱G’是G的一個(gè)支撐子圖。點(diǎn)v的次：以點(diǎn)v為端點(diǎn)邊的個(gè)數(shù)，記為dG(v)或d(v)。懸掛點(diǎn)：次為1的點(diǎn)。懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊。第三頁(yè)，共四十三頁(yè)，編輯于2023年，星期三弧立點(diǎn)：次為零的點(diǎn)。定理1：圖G=(V,E)中，所有點(diǎn)的次之和是邊數(shù)的兩倍，即Σd(v)=2qvV奇點(diǎn)：次為奇數(shù)的點(diǎn)。否則稱為偶點(diǎn)。定理2：任一圖中，奇點(diǎn)的個(gè)數(shù)為偶數(shù)。給定一個(gè)圖G=(V,E)，一個(gè)點(diǎn)邊的交錯(cuò)序列(vi1,ei1,vi2,ei2,…,vik-1,eik-1,vik)，如果滿足eit=[vit,vit+1](t=1,2,…,k-1)，則稱為一條聯(lián)結(jié)vi1第四頁(yè)，共四十三頁(yè)，編輯于2023年，星期三和vik的鏈，記為(vi1,vi2,…,vik)，稱點(diǎn)vi2,vi3,…,vik-1為鏈的中間點(diǎn)。鏈(vi1,vi2,…,vik)中，若vi1=vik,，則稱之為一個(gè)圈，記為(vi1,vi2,…,vik-1,vi1)。若鏈(vi1,vi2,…,vik)中，點(diǎn)vi1,vi2,…,vik都是不同的，則稱之為初等鏈；若圈(vi1,vi2,…,vik-1,vi1)中，vi1,vi2,…,vik-1都是不同的，則稱之為初等圈。若鏈(圈)中含的邊均不相同，則稱之為簡(jiǎn)單圈。第五頁(yè)，共四十三頁(yè)，編輯于2023年，星期三連通圖：圖G中，若任何兩個(gè)點(diǎn)之間，至少有一條鏈。連通分圖(分圖)：若G是不連通圖，它的每個(gè)連通的部分。基礎(chǔ)圖：給定一個(gè)有向圖D=(V,A)，從D中去掉所有弧上的箭頭，所得到的無(wú)向圖。記之為G(D)。給定D中的一條弧a=(u,v)，稱u為a的始點(diǎn)，v為a的終點(diǎn)，稱弧a是從u指向v的。設(shè)(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一個(gè)點(diǎn)弧交錯(cuò)序列，如果這個(gè)序列在基礎(chǔ)圖G(D)第六頁(yè)，共四十三頁(yè)，編輯于2023年，星期三

中所對(duì)應(yīng)的點(diǎn)邊序列是一條鏈，則稱這個(gè)點(diǎn)弧交錯(cuò)序列是D的一條鏈。如果(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一條鏈，并且對(duì)t=1,2,…,k-1，均有ait=(vit,vit+1)，稱之為從vi1到vik的一條路。若路的第一個(gè)點(diǎn)和最后一點(diǎn)相同，則稱之為回路。第七頁(yè)，共四十三頁(yè)，編輯于2023年，星期三§2樹(shù)2.1樹(shù)及其性質(zhì)定義1一個(gè)無(wú)圈的連通圖稱為樹(shù)定理1設(shè)圖G=(V,E)是一個(gè)樹(shù)，p(G)≥2，則G中至少有兩個(gè)懸掛點(diǎn)。定理2圖G=(V,E)是一個(gè)樹(shù)的充分必要條件是G中不含圈，且恰有p-1條邊。定理3圖G=(V,E)是一個(gè)樹(shù)的充分必要條件是G是連通圖，并且q(G)=p(G)-1。定理4圖G是樹(shù)的充分必要條件是任意兩個(gè)頂點(diǎn)之間恰有一條鏈。第八頁(yè)，共四十三頁(yè)，編輯于2023年，星期三推論：(1).從一個(gè)樹(shù)中去掉一條邊，則余下的圖是不連通的。(2).在樹(shù)中不相鄰的兩個(gè)點(diǎn)間添上一條邊，則恰好得到一個(gè)圈。2.2圖的支撐樹(shù)定義2設(shè)圖T=(V,E’)是圖的支撐子圖，如果圖T=(V,E’)是一個(gè)樹(shù)，則稱T是G的一個(gè)支撐樹(shù)。定理5：圖G有支撐樹(shù)的充分必要條件是圖G是連通的。第九頁(yè)，共四十三頁(yè)，編輯于2023年，星期三[證]必要性：顯然。充分性：設(shè)圖G是連通圖，如果G不含圈，那么G本身是一個(gè)樹(shù)，從而G是它自身的一個(gè)支撐子圖G1。如果G含圈，任取一個(gè)圈，從圈中任意地去掉一條邊，得到圖G的一個(gè)支撐子圖G1。如果G1不含圈，那么G1是G的一個(gè)支撐樹(shù)(因G1是連通的)；如果G1仍含圈，那么從G1中任取一個(gè)圈，從圈中再任意去掉一條邊，得到圖G的一個(gè)支撐子圖G2，如此重復(fù)，最終可以得到G的一個(gè)支撐子圖Gk,它不含圈，于是Gk是G的一個(gè)支撐樹(shù)。第十頁(yè)，共四十三頁(yè)，編輯于2023年，星期三2.3最小支撐樹(shù)問(wèn)題定義3給圖G=(V,E)，對(duì)G中的每一條邊[vi,vj]，相應(yīng)地有一個(gè)數(shù)wij，則稱這樣的圖G為賦權(quán)圖，wij稱為邊[vi,vj]上的權(quán)。設(shè)有一個(gè)連通圖G=(V,E)，每一邊e=(vi,vj)有一個(gè)非負(fù)權(quán)w(e)=wij(wij≥0)定義4:如果T=(V,E’)是G的一個(gè)支撐樹(shù)，稱E’中所有邊的權(quán)之和為支撐樹(shù)T的權(quán)，記為w(T)，即w(T)=Σwij

(vi,vj)∈T第十一頁(yè)，共四十三頁(yè)，編輯于2023年，星期三如果支撐樹(shù)T*的權(quán)w(T*)是G的所有支撐樹(shù)的權(quán)中最小者，則稱T*是G的最小支撐樹(shù)(簡(jiǎn)稱最小樹(shù))w(T*)=minw(T)T求最小樹(shù)的方法：方法一(避圈法)開(kāi)始選一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈。第十二頁(yè)，共四十三頁(yè)，編輯于2023年，星期三方法二(破圈法)任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊。在余下的圖中，重復(fù)這個(gè)步驟，一直到一個(gè)不含圈的圖為止，這時(shí)的圖便是最小樹(shù)。例用破圈法求下圖的最小樹(shù)12222312222333445第十三頁(yè)，共四十三頁(yè)，編輯于2023年，星期三§3最短路問(wèn)題Dijkstra算法的基本思想：若{vs,v1,…,vk}是從vs到vk的最短路，則{vs,v1,…,vi}是從vs到vi的最短路。T(臨時(shí))標(biāo)號(hào)：從vs到某一節(jié)點(diǎn)最短距離的上界。P(永久)標(biāo)號(hào)：從vs到某一節(jié)點(diǎn)的最短距離。第十四頁(yè)，共四十三頁(yè)，編輯于2023年，星期三步驟：給vs標(biāo)上永久標(biāo)號(hào)P(vs)=0，其余節(jié)點(diǎn)標(biāo)上臨時(shí)標(biāo)號(hào)T(vj)=∞(1)若節(jié)點(diǎn)vi是剛得到P標(biāo)號(hào)的點(diǎn)。把與vi有弧(邊)直接相連而且有屬于T標(biāo)號(hào)的節(jié)點(diǎn)，改為下列T標(biāo)號(hào)T(vj)=min{T(vj),P(vi)+dij}(2)把T標(biāo)號(hào)中標(biāo)號(hào)最小的節(jié)點(diǎn)vj0的臨時(shí)標(biāo)號(hào)T(vj0)改為P(vj0),直至算法終止;否則轉(zhuǎn)(1)第十五頁(yè)，共四十三頁(yè)，編輯于2023年，星期三例求節(jié)點(diǎn)v1到節(jié)點(diǎn)v5的最短距離及其路線vSv1v2v3v4v5122233344[解]P(vs)=0T(vj)=∞,j=1,…,5第一步：T(v1)=min{T(v1),P(vs)+ds1}=min{∞,0+4}=4(1)與節(jié)點(diǎn)vs直接相連的臨時(shí)標(biāo)號(hào)的節(jié)點(diǎn)為v1,v2，將這兩個(gè)節(jié)點(diǎn)的臨時(shí)標(biāo)號(hào)改為第十六頁(yè)，共四十三頁(yè)，編輯于2023年，星期三T(v2)=min{T(v2),P(vs)+ds2}=min{∞,0+3}=3(2)在所有T標(biāo)號(hào)中，最小的為T(mén)(v2)=3,于是令P(v2)=3第二步：(1)與節(jié)點(diǎn)v2直接相連的臨時(shí)標(biāo)號(hào)的節(jié)點(diǎn)為v3和v4，把這兩個(gè)節(jié)點(diǎn)的T標(biāo)號(hào)改為T(mén)(v1)=min{T(v1),P(v2)+d21}=min{4,3+2}=4T(v4)=min{T(v4),P(v2)+d24}=min{∞,3+2}=5(2).在所有T變化中，T(v1)=4最小，于是令P(v1)=4第十七頁(yè)，共四十三頁(yè)，編輯于2023年，星期三第三步：(1).與節(jié)點(diǎn)v1相連的臨時(shí)標(biāo)號(hào)的節(jié)點(diǎn)為v3,v4，把這兩個(gè)節(jié)點(diǎn)的T標(biāo)號(hào)改為T(mén)(v3)=min{T(v3),P(v1)+d13}=min{∞,4+3}=7T(v4)=min{T(v4),P(v1)+d14}=min{5,4+1}=5(2).在T標(biāo)號(hào)中，T(v4)=5最小，令P(v4)=5第四步：(1).與節(jié)點(diǎn)v4相連的T標(biāo)號(hào)有v3,v5把這兩個(gè)節(jié)點(diǎn)的T標(biāo)號(hào)改為第十八頁(yè)，共四十三頁(yè)，編輯于2023年，星期三T(v3)=min{T(v3),P(v4)+d43}=min{7,5+2}=7T(v5)=min{T(v5),P(v5)+d45}=min{∞,5+4}=9(2).T(v3)最小,P(v3)=7第五步：(1).與v3相連的臨時(shí)標(biāo)號(hào)有v5T(v5)=min{T(v5),P(v3)+d35}=min{9,7+3}=9(2).P(v5)=9最短路線：vs→v1→v4→v5vs→v2→v4→v5第十九頁(yè)，共四十三頁(yè)，編輯于2023年，星期三下面介紹當(dāng)賦權(quán)有向圖中，存在具負(fù)權(quán)的弧時(shí)，求最短路的方法。令d(1)(vs,vj)=wsj對(duì)t=2,3,…,d(t)(vs,vj)=min{d(t-1)(vs,vi)+wij}(j=1,2,…,p)若進(jìn)行到某一步,例如第k步,對(duì)所有j=1,2,…,p,有d(k)(vs,vj)=d(k-1)(vs,vj)i第二十頁(yè)，共四十三頁(yè)，編輯于2023年，星期三則{d(k)(vs,vj)}j=1,2,…,p即為到各點(diǎn)的最短路的權(quán)。例求下圖所示有向圖中從v1到各點(diǎn)的最短路。v1v4v2v3v5v6v7v825-34674-23-1-342第二十一頁(yè)，共四十三頁(yè)，編輯于2023年，星期三

wijd(t)(v1,vj)v1v2v3v4v5v6v7v8v1v2v3

v4v5v6v7v8025-30-2406400-30720320t=1t=2t=3t=4t=5t=6025-3020-3611020-36615020-3361410020-336910020-336910說(shuō)明：表中空格處為+。第二十二頁(yè)，共四十三頁(yè)，編輯于2023年，星期三例設(shè)備更新問(wèn)題制訂一設(shè)備更新問(wèn)題，使得總費(fèi)用最小第1年第2年第3年第4年第5年購(gòu)買費(fèi)1314161924使用年數(shù)0-11-22-33-44-5維修費(fèi)810131827[解]設(shè)以vi(i=1,2,3,4,5)表示“第i年初購(gòu)進(jìn)一臺(tái)新設(shè)備”這種狀態(tài)，以v6表示“第5年末”這種狀態(tài)；以弧(vi,

vj)表示“第i年初購(gòu)置的一臺(tái)設(shè)備一直使用到第j年初”這一方案，以wij表示這一方案所需購(gòu)置費(fèi)和維護(hù)費(fèi)之和。第二十三頁(yè)，共四十三頁(yè)，編輯于2023年，星期三這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問(wèn)題就可歸結(jié)為從圖中找出一條從v1到v6的最短路問(wèn)題。用Dijkstra標(biāo)號(hào)法，求得最短路為v1v3v6

即第一年初購(gòu)置的設(shè)備使用到第三年初予以更新，然后一直使用到第五年末。這樣五年的總費(fèi)用最少，為78。第二十四頁(yè)，共四十三頁(yè)，編輯于2023年，星期三v1v2v3v5v6v4214432228962316345244734273732(0)(21)(31)(44)(62)(78)第二十五頁(yè)，共四十三頁(yè)，編輯于2023年，星期三§4最大流問(wèn)題如下是一運(yùn)輸網(wǎng)絡(luò)，弧上的數(shù)字表示每條弧上的容量，問(wèn)：該網(wǎng)絡(luò)的最大流量是多少？vsv2v1v3v4vt432312234第二十六頁(yè)，共四十三頁(yè)，編輯于2023年，星期三4.1基本概念和基本定理(1)網(wǎng)絡(luò)與流定義1給定一個(gè)有向圖D=(V,A),在V中有一個(gè)發(fā)點(diǎn)vs和一收點(diǎn)vt，其余的點(diǎn)為中間點(diǎn)。對(duì)于每一條弧(vi,vj),對(duì)應(yīng)有一個(gè)c(vi,vj)0,(cij)稱為弧的容量。這樣的有向圖稱為網(wǎng)絡(luò)。記為D=(V,A,C)。網(wǎng)絡(luò)的流：定義在弧集合A上的一個(gè)函數(shù)f={f(vi,vj)}，稱f(vi,vj)為弧(vi,vj)上的流量。(fij)第二十七頁(yè)，共四十三頁(yè)，編輯于2023年，星期三(2)可行流與最大流定義2滿足下列條件的流稱為可行流：1)0fijcij2)對(duì)于每一is,tfij=fji(vi,vj)A(vj,vi)A對(duì)于發(fā)點(diǎn)vs和收點(diǎn)vt，fsj–fjs=v(f)(vs,vj)A(vj,vs)A第二十八頁(yè)，共四十三頁(yè)，編輯于2023年，星期三ftj–fjt=–v(f)(vt,vj)A(vj,vt)A式中v(f)稱為這個(gè)可行流的流量，即發(fā)點(diǎn)的凈輸出量（或收點(diǎn)的凈輸入量）。最大流問(wèn)題：求一流{fij}滿足0fijcijv(f)i=sfij–fji=0is，t–v(f)i=t且使v(f)達(dá)到最大。第二十九頁(yè)，共四十三頁(yè)，編輯于2023年，星期三(3)增廣鏈給定可行流f={fij}，使fij=cij的弧稱為飽和弧，使fij<cij的弧稱為非飽和弧，把fij=0的弧稱為零流弧，fij>0的弧稱為非零流弧。若是網(wǎng)絡(luò)中連接發(fā)點(diǎn)vs和收點(diǎn)vt的一條鏈，定義鏈的方向是從vs到vt，則鏈上的弧被分成兩類：前向弧：弧的方向與鏈的方向一致全體+后向弧：弧的方向與鏈的方向相反全體—第三十頁(yè)，共四十三頁(yè)，編輯于2023年，星期三定義3設(shè)f是一可行流，是從vs到vt的一條鏈，若滿足下列條件，則稱之為（關(guān)于流f的）一條增廣鏈：在弧(vi,vj)+上，0fij<cij在弧(vi,vj)—上，0<fijcij(4)截集與截量設(shè)S，TV，ST=，我們把始點(diǎn)在S，終點(diǎn)在T中的所有弧構(gòu)成的集合，記為（S，T）。定義4給定網(wǎng)絡(luò)D=(V,A,C)，若點(diǎn)集V被剖分為兩個(gè)非空集合V1和V1，使vsV1，第三十一頁(yè)，共四十三頁(yè)，編輯于2023年，星期三vtV1，則把弧集(V1,V1)稱為是（分離vs和vt的）截集。截集是從vs到vt的必經(jīng)之路。定義5給定一截集(V1,V1)，把截集(V1,V1)中所有弧的容量之和稱為這個(gè)截集的容量(截量),記為C(V1,V1)。v(f)C(V1,V1)若對(duì)于一可行流f*，網(wǎng)絡(luò)中有一截集(V1*,V1*)，使得v(f*)=C(V1*,V1*)，則f必是最大流，而(V1*,V1*)，必定是容量最小的截集，即最小截集。第三十二頁(yè)，共四十三頁(yè)，編輯于2023年，星期三定理1可行流f*是最大流的充要條件是不存在關(guān)于f*的最大流。若f*是最大流，則網(wǎng)絡(luò)中必存在一個(gè)截集(V1*,V1*)，使得v(f*)=C(V1*,V1*)定理2任一網(wǎng)絡(luò)D中，從vs到vt的最大流的流量等于分離vs，vt的最小截集的截量。4.2尋找最大流的標(biāo)號(hào)法(FordFulkerson)思想：從一可行流出發(fā)，檢查關(guān)于此流是否存在增廣鏈。若存在增廣鏈，則增大流第三十三頁(yè)，共四十三頁(yè)，編輯于2023年，星期三量，使此鏈變?yōu)榉窃鰪V鏈；這時(shí)再檢查是非還有增廣鏈，若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。過(guò)程：1)標(biāo)號(hào)過(guò)程標(biāo)號(hào)過(guò)程開(kāi)始時(shí)，總先給vs標(biāo)上(0,+),這時(shí)vs是標(biāo)號(hào)而未檢查的點(diǎn)，其余都是未標(biāo)號(hào)的點(diǎn)。一般，取一個(gè)標(biāo)號(hào)而未檢查的點(diǎn)vi，對(duì)一切未標(biāo)號(hào)的點(diǎn)vj；(1)若在弧(vi,vj)上，fij<cij，則給vj標(biāo)號(hào)(vi,l(vj))，這里l(vj)=min[l(vi)，cij–fij]。這時(shí)點(diǎn)第三十四頁(yè)，共四十三頁(yè)，編輯于2023年，星期三vj成為標(biāo)號(hào)而未檢查的點(diǎn)。(2)若在弧(vj,vi)上，fji>0，則給vj標(biāo)號(hào)(–vi,l(vj))，這里l(vj)=min[l(vi)，fji]。這時(shí)點(diǎn)vj成為標(biāo)號(hào)而未檢查的點(diǎn)。于是vi成為標(biāo)號(hào)而已檢查過(guò)的點(diǎn)。重復(fù)上述步驟，一旦vt被標(biāo)上號(hào)，表明得到一條從vs到vt的增廣鏈，轉(zhuǎn)入調(diào)整階段。若所有標(biāo)號(hào)都已檢查過(guò)，而標(biāo)號(hào)過(guò)程進(jìn)行不下去，則算法結(jié)束，這時(shí)的可行流就是最大流。第三十五頁(yè)，共四十三頁(yè)，編輯于2023年，星期三

2)調(diào)整過(guò)程首先按及其它點(diǎn)的第一個(gè)標(biāo)號(hào)，利用“反向追蹤”的方法，找出增廣鏈。令調(diào)整量為=l(vt)令fij+

(vi,vj)+fij′=fij–(vi,vj)—

fij(vi,vj)去掉所有的標(biāo)號(hào)，對(duì)新的可行流f′={fij′}，重新進(jìn)入標(biāo)號(hào)過(guò)程。v(f′)=v(f)+第三十六頁(yè)，共四十三頁(yè)，編輯于2023年，星期三可結(jié)合下圖理解其實(shí)際涵義。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)第三十七頁(yè)，共四十三頁(yè)，編輯于2023年，星期三vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例求下列網(wǎng)絡(luò)的最大流與最小截集。[解]一、標(biāo)號(hào)過(guò)程（1）先給vs標(biāo)上(0,+)。（2）檢查vs,在弧(vs,v1)上,fs1=7,cs1=9,fs1<cs1,則v1的標(biāo)號(hào)為(vs,l(v1))，其中第三十八頁(yè)，共四十三頁(yè)，編輯于2023年，星期三l(v1)=min{l(vs)，cs1–fs1}=min{+，9–2}=2（3）檢查v1,在弧(v1,v4)上,f14=7,c14=9,f14<c14,則v4的標(biāo)號(hào)為(v1,l(v4))，其中l(wèi)(v4)=min{l(v1)，c14–f14}=min{2，3-1}=2（4）檢查v4,在弧(v3