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

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

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

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

wijd(t)(v1,vj)v1v2v3v4v5v6v7v8v1v2v3

v4v5v6v7v8025-30-2406400-30720320t=1t=2t=3t=4t=5t=6025-3020-3611020-36615020-3361410020-336910020-336910說明：表中空格處為+。第22頁，共43頁，2023年，2月20日，星期日例設備更新問題制訂一設備更新問題，使得總費用最小第1年第2年第3年第4年第5年購買費1314161924使用年數(shù)0-11-22-33-44-5維修費810131827[解]設以vi(i=1,2,3,4,5)表示“第i年初購進一臺新設備”這種狀態(tài)，以v6表示“第5年末”這種狀態(tài)；以弧(vi,

vj)表示“第i年初購置的一臺設備一直使用到第j年初”這一方案，以wij表示這一方案所需購置費和維護費之和。第23頁，共43頁，2023年，2月20日，星期日這樣，可建立本例的網(wǎng)絡模型。于是，該問題就可歸結(jié)為從圖中找出一條從v1到v6的最短路問題。用Dijkstra標號法，求得最短路為v1v3v6

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

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

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

fij(vi,vj)去掉所有的標號，對新的可行流f′={fij′}，重新進入標號過程。v(f′)=v(f)+第36頁，共43頁，2023年，2月20日，星期日可結(jié)合下圖理解其實際涵義。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)第37頁，共43頁，2023年，2月20日，星期日vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例求下列網(wǎng)絡的最大流與最小截集。[解]一、標號過程（1）先給vs標上(0,+)。（2）檢查vs,在弧(vs,v1)上,fs1=7,cs1=9,fs1<cs1,則v1的標號為(vs,l(v1))，其中第38頁，共43頁，2023年，2月20日，星期日l(v1)=min{l(vs)，cs1–fs1}=min{+，9–2}=2（3）檢查v1,在弧(v1,v4)上,f14=7,c14=9,f14<c14,則v4的標號為(v1,l(v4))，其中l(wèi)(v4)=min{l(v1)，c14–f14}=min{2，3-1}=2（4）檢查v4,在弧(v3