運籌學胡運權第五版課件(第6章)

第6章圖與網(wǎng)絡分析GraphandNetworkAnalysis

圖是一種模型，如公路鐵路交通圖，水或煤氣管網(wǎng)圖，通訊聯(lián)絡圖等。

圖是對現(xiàn)實的抽象，用點和線的連接組合表示?！?.1圖的基本概念和模型

圖不同于幾何圖形。一、基本概念1、圖(graph)：由V,E構成的有序二元組，用以表示對某些現(xiàn)實對象及其聯(lián)系的抽象，記作G=｛V,E｝。 其中V稱為點集，記做V=｛v1,v2,···,vn｝

E稱為邊集，記做E=｛e1,e2,···,em｝點(vertex)：表示所研究的對象，用v表示；邊(edge)：表示對象之間的聯(lián)系，用e表示。網(wǎng)絡圖(賦權圖)：點或邊具有實際意義(權數(shù))的圖，記做N。零圖：邊集為空集的圖。v1v2v3v4v5e1e2e3e4e5e6e7e8特別的，若邊e的兩個端點重合，則稱e為環(huán)。

若兩個端點之間多于一條邊，則稱為多重邊。2、圖的階：即圖中的點數(shù)。例如右圖為一個五階圖3、若圖中邊e=[vi,vj],則vi,vj稱為e的端點，

e稱為vi,vj的關聯(lián)邊。若vi與vj是一條邊的兩個端點，則稱vi與vj相鄰；若邊ei與ej有公共的端點，則稱ei與ej相鄰。簡單圖：無環(huán)、無多重邊的圖。例如：e6=[v2,v3]4、點v的次（或度，degree）與點v關聯(lián)的邊的條數(shù)，記為dG(v)或d(v)。v1v2v3v4e1e2e3e4e5e6e7v5

懸掛點次為1的點，如v5

懸掛邊懸掛點的關聯(lián)邊，如e8e8

孤立點次為0的點

偶點次為偶數(shù)的點，如v2

奇點

次為奇數(shù)的點,如v55、鏈：圖中保持關聯(lián)關系的點和邊的交替序列，其中點可重復，但邊不能重復。路：點不能重復的鏈。圈：起點和終點重合的鏈?；芈罚浩瘘c和終點重合的路。連通圖：任意兩點之間至少存在一條鏈的圖。完全圖：任意兩點之間都有邊相連的簡單圖。

n階完全圖用Kn表示，邊數(shù)=注意：完全圖是連通圖，但連通圖不一定是完全圖。v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9如圖(v1,e1,v2,e2,v3,e3,v4,e5,v5,e6,v3,e7,v6,e8,v7)是一條鏈,但不是路(v1,e1,v2,e2,v3,e7,v6,e8,v7)是一條路(v1,e1,v2,e2,v3,e3,v4,e4,v1)是一個回路(v4,e4,v1,e1,v2,e2,v3,e6,v5,e9,v7,e8,v6,e7,v3,e3,v4)是一個圈本圖是一個連通圖。7、已知圖G1=｛V1,E1｝,G2={V2,E2},若有V1V2，E1E2，則稱G1是G2的一個子圖；若V1=V2，E1E2且

E1≠E2

，則稱G1是G2的一個部分圖。6、偶圖（二分圖）：若圖G的點集V可以分為兩個互不相交的非空子集V1和V2，而且在同一個子集中的點均互不相鄰，則圖G稱為偶圖。完全偶圖：V1中的每個點均和V2中的每個點相鄰的偶圖。若完全偶圖中V1有m個點，V2有n個點，則該圖共有mn條邊。注意：部分圖是子圖，子圖不一定是部分圖。二、應用例有甲、乙、丙、丁、戊、己六名運動員報名參加A、B、C、D、E、F六個項目的比賽。如表中所示，打“√”的項目是各運動員報名參加比賽的項目。問：六個項目的比賽順序應如何安排，才能做到使每名運動員不連續(xù)地參加兩項比賽？甲乙丙丁戊己項目人A B C D E F√√√√√√√√√√√√√√√√解：構造一個六階圖如下：

點：表示運動項目。邊：若兩個項目之間有同一名運動員報名參加，則對應的兩個點之間連一條邊。ABCDEFA—C—B—F—E—D為滿足題目要求，應該選擇不相鄰的點來安排比賽的順序：或D—E—F—B—C—A§6.2樹圖和圖的最小部分樹1、樹（tree）：無圈的連通圖稱為樹圖，簡稱為樹,用T(V,E)或T表示。一、樹圖的概念2、樹的性質(zhì)（1）樹中必有懸掛點。證明（反證法）：設樹中任何點的次均不為1.

因為樹無孤立點，所以樹的點的次≥2.

不妨設樹有n個點，記為v1,v2,…,vn

因為d(v1)≥2,不妨設v1與v2,v3相鄰。又因為樹沒有圈，且d(v2)≥2,可設v2與v4相鄰，…,依次下去，vn必然與前面的某個點相鄰，圖中有圈，矛盾！注意：樹去掉懸掛點和懸掛邊后余下的子圖還是樹。（2）n階樹必有n-1條邊。證明（歸納法）：當n=2時，顯然；設n=k-1時結論成立。當n=k時，樹至少有一個懸掛點。去掉該懸掛點和懸掛邊，得到一個k-1階的樹，它有k-2條邊，則原k階樹有k-1條邊。即n=k時結論也成立。綜上，n階樹有n-1條邊。

（3）任何有n個點、n-1條邊的連通圖是樹。證明（反證法）：假設n個點，n-1條邊的連通圖中有圈，則在該圈中去掉一條邊得到的子圖仍連通，若子圖仍有圈，則繼續(xù)在相應圈中去掉一條邊，…，直到得到無圈的連通圖，即為樹。但是該樹有n個點，邊數(shù)少于n-1,矛盾！

注意：①樹是邊數(shù)最多的無圈圖。②樹是邊數(shù)最少的連通圖。在樹中不相鄰的兩個點之間添上一條邊，則恰得到一個圈。

從樹中去掉一條邊，則余下的圖不連通。3、圖的最小部分樹（1）部分樹：若G1是G2的一個部分圖，且G1為樹，則稱G1是G2的一個部分樹（或支撐樹）。G2：ABCD547365576G1：ACBD注意：圖G有部分樹的必要條件是G是連通圖。部分樹不是唯一的。（2）最小部分樹（或最小支撐樹）圖G為網(wǎng)絡圖，若T是部分樹中權和最小者，則稱T是G的最小部分樹(或稱最小支撐樹).二、最小部分樹的求法1、原理（1）圖中與點v關聯(lián)的最短邊（即權最小的邊）一定包含在最小部分樹中。（2）將圖中的點分成兩個互不相交的非空子集，則兩個子集之間連線的最短邊一定包含在最小部分樹中。SABCDET252414317557即求圖中的最小部分樹例：要在下圖所示的各個位置之間建立起通信網(wǎng)絡，試確定使總距離最佳的方案。2、求法方法一：避圈法將圖中所有的點分V為V兩部分，

V——最小部分樹中的點的集合

V——非最小部分樹中的點的集合⑴任取一點vi加粗，令vi∈V，其他點在V中 ⑵在V與V相連的邊中取一條最短的邊(vi,vj)，加粗(vi,vj)，令vj∈V ，并在V中去掉vj⑶重復⑵，至所有的點均在V之內(nèi)?！叭⌒∵叀盨ABCDET252414317557最小部分樹長Lmin=14例：要在下圖所示的各個位置之間建立起通信網(wǎng)絡，試確定使總距離最佳的方案。SABCDET252414317557××

××××最小部分樹長Lmin=14方法二：破圈法⑴任取一圈，去掉其中一條最長邊；⑵在余下的圖中重復(1)，直至圖中沒有任何圈為止。“去大邊”§6.3最短路問題1、最短路問題從已知的網(wǎng)絡圖中找出兩點之間距離最短（即權和最?。┑穆贰?、相關記號（1）dij表示圖中兩個相鄰點i和j之間的距離（即權）。易見dii=0

約定：當i和j不相鄰時，dij=∞（2）Lij表示圖中點i和j之間的最短距離（即最小權和）。易見Lii=0

即在已知的網(wǎng)絡圖中，從給定點s出發(fā)，要到達目的地t。問：選擇怎樣的行走路線，可使總行程最短？3、狄克斯屈拉（Dijkstra）標號算法（1）適用范圍用于求某兩個點之間的最短距離。（2）原理最短路上任何片段是最短路。v1v2v3v4v5（3）思想按離出發(fā)點s的距離由近至遠逐步標出最短距離Lsi以及最佳行進路線。SABCDET2524143175575例求圖中S到T的最短路及最短距離。（4）步驟在網(wǎng)絡圖中求s到t的最短路。第一步從s出發(fā)，將Lss=0標記在s旁邊的方框內(nèi)（表示點s已標記）；第二步找出與s相鄰且距離最小的點，設為r，計算Lsr=Lss+dsr，并將結果標記在r旁邊的方框內(nèi)（表示點r已標記），同時標記邊sr；第三步從已標記的點出發(fā)，找出這些點的所有未標記鄰點，分別計算已標記點的方框數(shù)與其鄰點的距離之和，利用“疊加最小”的原則確定下一個被標記點，設為p，并將最小的和標記在p旁邊的方框內(nèi)（表示點p已標記）,同時標記相應邊；第四步重復第三步，直到t得到標記為止。SABCDET25241431755702447891413594最短路：SABEDT最短距離：LST=13例求圖中S到T的最短路及最短距離。V1V2V3V4V5V6V752276742136例求圖中v1到v7的最短路。05277610例求圖中任意兩點之間的最短距離。V1V2V3V4V6V7522767421364、矩陣算法

求任意兩點間最短距離的方法v1v2v3v4v5v6v7V1052∞∞∞∞V250∞27∞∞V32∞07∞4∞V4∞27062∞V5∞7∞6013V6∞∞42106v7∞∞∞∞360⑴構造任意兩點間直接到達的最短距離矩陣記做D(0)=dij(0)其中dij(0)=dij注意：D(0)是一個對稱矩陣，且對角線上的元素全是0.D（0）=其中dij（1）=min{

dir（0）+drj（0）}

irjdir（0）drj（0）r⑵構造任意兩點間直接到達、或者最多經(jīng)過1個中間點到達的最短距離矩陣D（1）=dij（1）即dij(1)為D(0)中第i行和第j行對應元素之和的最小值D（1）=v1v2v3v4v5v6v7V10527126∞V250727410V327065410V47260328V512753013V66442104v7∞10108340其中dij（2）=min{

dir（1）+drj（1）}irjdir（1）drj（1）r⑶構造任意兩點間最多可經(jīng)過3個中間點到達的最短距離矩陣D（2）=dij（2）即dij(2)為D(1)中第i行和第j行對應元素之和的最小值D（2）=v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340其中dij（3）=min{

dir（2）+drj（2）

}irjdir（2）drj（2）r⑷構造任意兩點間最多可經(jīng)過7個中間點到達的最短距離矩陣D（3）=dij（3）即dij(3)為D(2)中第i行和第j行對應元素之和的最小值D（3）=v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340=D（2）故D(2)中的元素就是圖中相應兩點之間的最短距離。說明：一般的對于D（k）=dij（k），其中dij（k）=min{dir（k-1）+drj（k-1）}，(k=0,1,2,3,…)最多可經(jīng)過2k-1個中間點收斂條件：當D（k+1）=D（k）時，計算結束；設網(wǎng)絡圖有p個點，即最多有p-2個中間點，則2k-1-1<p-22k-1

k-1<log2(p-1)k∴k<log2(p-1)+1，即計算到k=lg(p-1)/lg2+1時，計算結束。注意狄克斯屈拉算法矩陣算法優(yōu)點既可以求兩點之間的最短距離，又可以確定最短路求任意兩點之間的最短距離缺點求某兩點之間的最短距離不能確定相應兩點之間的最短路

例：下圖中v1—v7表示7個村子，需要聯(lián)合建立一所小學，已知各村小學生的人數(shù)分別為v1—30人，v2—40人，v3—25人，v4—20人，v5—50人，v6—60人，v7—60人。問：學校應建在哪一個村子，可使學生總行程最少？V1V2V3V4V6V752276742136v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340解：用矩陣算法得到任意兩個村子之間的最短距離如下：

先將每一行的元素乘以該村子的學生人數(shù)，得到小學建在相應村子時，該村學生上學時單程所走的路程。再將每一列的元素累加，得到小學建在相應村子時，七個村子的學生上學時單程所走的總路程。小學建在下列村子時，七個村子的學生上學時單程所走的路程v1v2v3v4v5v6v701506021021018030020002808020016032050175015012510020014040120060401203502502501500501503602402401206002406004804803601802400總路程17001335143010708357701330故小學應該建在v6村。v1Sv2v3v4T§6.4網(wǎng)絡的最大流v1Sv2v3v4T一、基本概念和基本結論2、圖的分類（1）無向圖（簡稱圖）記做G=(V,E)，V、E分別為點集和邊集。（2）有向圖記做D=(V,A），V、A分別為點集和弧集。注意：以下討論的是有向圖。3、弧的容量（簡稱容量）：弧(vi,vj)上可通過負載的最大能力。用c(vi,vj)或cij表示。1、圖中兩點vi與vj之間的連線有兩種情況（1）邊（edge）:未規(guī)定方向的連線，記做vi,vj,其中vi,vj稱為端點（2）?。╝rc）:規(guī)定方向的連線，記做(vi,vj)，其中vi稱為起點，vj稱為終點4、容量網(wǎng)絡（簡稱網(wǎng)絡）：每條弧都有容量的網(wǎng)絡。8v1Sv2v3v4T799265105例如：5、容量網(wǎng)絡中點的分類發(fā)點（源點）：用S表示，“只出不入”收點（匯點）：用T表示，“只入不出”中間點：“有入有出”注意：任意容量網(wǎng)絡總可以轉換為只有一個發(fā)點和一個收點的情況。6、流（flow）：加在網(wǎng)絡中弧(vi,vj)上的一組負載量，用f(vi,vj)或fij表示。8(8)v1sv2v3v4t7(5)9(4)9(9)2(0)6(1)5(5)10(8)5(4)其中cij(fij)該流為可行流10、網(wǎng)絡的最大流：即使V(f)達到最大的可行流。8、零流：加在每條弧上的流量全為0。易見：零流一定是可行流。每個容量網(wǎng)絡都有可行流。9、總流量：從發(fā)點s到收點t的流量,記做V(f)7、可行流(記做f)：能夠在網(wǎng)絡中通過的流，必須滿足以下兩個條件： ①容量限制條件：對所有弧，0

fijcij②中間點平衡條件：對任何一個中間點，流入量=流出量

12、割的容量：割集中各弧的容量之和。13、最小割：所有割集中容量之和最小的一個割集。11、割集（簡稱割）：一組弧的集合，割斷這些弧能使從s到t的流中斷。定理：網(wǎng)絡的最大流量等于它的最小割集的容量。8(8)v1sv2v3v4t7(5)9(4)9(9)2(0)6(1)5(5)10(8)5(4)例如：割集={(v1,v3),(v2,v4)}割的容量=9+9=1814、前向弧（或正向?。涸趶陌l(fā)點s到收點t的一條鏈中，指向為s到t的弧稱為前向弧，記做μ+。16、增廣鏈：對于從s到t的一條鏈，如果在前向弧上滿足流量小于容量，即fij<cij（即前向弧不飽和），后向弧上滿足流量大于0，即fij>0（即后向弧不為0），則稱這樣的鏈為增廣鏈。15、后向弧（或逆向?。涸趶陌l(fā)點s到收點t的一條鏈中，指向為t到s的弧稱為后向弧，記做μ-。st6(4)5(3)4(4)8(7)μ+μ+μ+μ-這是一條增廣鏈定理：當網(wǎng)絡中不存在增廣鏈時，網(wǎng)絡達到最大流狀態(tài)。二、網(wǎng)絡最大流的求法

標號算法(Ford-Fulkerson標號算法)1、基本思想：尋找增廣鏈；若無增廣鏈，則已經(jīng)得到最大流和最小割，結束；若有增廣鏈，則改善流量分布，再重復尋找，直到不存在增廣鏈為止。2、點v的標號v(x,ε(v))

其中x是使v得到標號的已標號點，

ε(v)是從x到v的流量的最大可調(diào)值。標號算法下規(guī)定:前向弧是已標號點指向未標號點的弧,后向弧是未標號點指向已標號點的弧.3、步驟：①對發(fā)點s標號：s（0，+∞）

從已標號點i出發(fā)，看與其相鄰的未標號點j之間的弧， 對前向弧μ+若滿足fij<cij，則對點j標號（i,ε(j)），其中ε(j)=min{ε(i)，cij-fij}對后向弧μ-若滿足fji＞0，則對點j標號（i,ε(j)），其中ε(j)=min{ε(i)，fji}（注：若有多個可標號點，可任選。）若出現(xiàn)其他情況，則點j不標號。前向弧不飽和，要標號后向弧不為0，要標號③當t得到標號時，從t開始沿已標號點用反向追蹤法得到增廣鏈，利用ε(t)調(diào)整流量：對前向弧μ+，新流量fij=fij+ε(t)

對后向弧μ-，新流量fij=fij-ε(t)

其余弧上的流量不變。④去掉所有標號，重復①。

若標號中斷，即t沒有得到標號，則該流為所求的網(wǎng)絡最大流（此時最小割集為已標號點與未標號點之間的前向?。?，結束；否則重復②，繼續(xù)標號，直到收點t得到標號，轉③。8(8)v1sv2v3v4t7(5)9(4)9(9)2(0)6(1)5(5)10(8)(0,+∞)(s,2)(v2,2)(v1,2)(v3,1)(v4,1)5(4)cijfij例求網(wǎng)絡的最大流。最大可調(diào)量為17(6)5(3)9(5)6(0)10(9)8(8)v1sv2v3v4t7(6)9(5)9(9)2(0)6(0)5(5)10(9)