運(yùn)籌學(xué)胡運(yùn)權(quán)第五版課件(第6章)

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

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

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

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

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

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

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

懸掛點(diǎn)次為1的點(diǎn)，如v5

懸掛邊懸掛點(diǎn)的關(guān)聯(lián)邊，如e8e8

孤立點(diǎn)次為0的點(diǎn)

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

奇點(diǎn)

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

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)是一個(gè)回路(v4,e4,v1,e1,v2,e2,v3,e6,v5,e9,v7,e8,v6,e7,v3,e3,v4)是一個(gè)圈本圖是一個(gè)連通圖。7、已知圖G1=｛V1,E1｝,G2={V2,E2},若有V1V2，E1E2，則稱G1是G2的一個(gè)子圖；若V1=V2，E1E2且

E1≠E2

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

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

因?yàn)闃錈o孤立點(diǎn)，所以樹的點(diǎn)的次≥2.

不妨設(shè)樹有n個(gè)點(diǎn)，記為v1,v2,…,vn

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

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

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

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

V——最小部分樹中的點(diǎn)的集合

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

××××最小部分樹長Lmin=14方法二：破圈法⑴任取一圈，去掉其中一條最長邊；⑵在余下的圖中重復(fù)(1)，直至圖中沒有任何圈為止?！叭ゴ筮叀薄?.3最短路問題1、最短路問題從已知的網(wǎng)絡(luò)圖中找出兩點(diǎn)之間距離最短（即權(quán)和最?。┑穆?。2、相關(guān)記號（1）dij表示圖中兩個(gè)相鄰點(diǎn)i和j之間的距離（即權(quán)）。易見dii=0

約定：當(dāng)i和j不相鄰時(shí)，dij=∞（2）Lij表示圖中點(diǎn)i和j之間的最短距離（即最小權(quán)和）。易見Lii=0

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

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

dir（0）+drj（0）}

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

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

dir（2）+drj（2）

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

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

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

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

fijcij②中間點(diǎn)平衡條件：對任何一個(gè)中間點(diǎn)，流入量=流出量

12、割的容量：割集中各弧的容量之和。13、最小割：所有割集中容量之和最小的一個(gè)割集。11、割集（簡稱割）：一組弧的集合，割斷這些弧能使從s到t的流中斷。定理：網(wǎng)絡(luò)的最大流量等于它的最小割集的容量。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ā)點(diǎn)s到收點(diǎn)t的一條鏈中，指向?yàn)閟到t的弧稱為前向弧，記做μ+。16、增廣鏈：對于從s到t的一條鏈，如果在前向弧上滿足流量小于容量，即fij<cij（即前向弧不飽和），后向弧上滿足流量大于0，即fij>0（即后向弧不為0），則稱這樣的鏈為增廣鏈。15、后向?。ɑ蚰嫦蚧。涸趶陌l(fā)點(diǎn)s到收點(diǎn)t的一條鏈中，指向?yàn)閠到s的弧稱為后向弧，記做μ-。st6(4)5(3)4(4)8(7)μ+μ+μ+μ-這是一條增廣鏈定理：當(dāng)網(wǎng)絡(luò)中不存在增廣鏈時(shí)，網(wǎng)絡(luò)達(dá)到最大流狀態(tài)。二、網(wǎng)絡(luò)最大流的求法

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

其中x是使v得到標(biāo)號的已標(biāo)號點(diǎn)，

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

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

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

其余弧上的流量不變。④去掉所有標(biāo)號，重復(fù)①。

若標(biāo)號中斷，即t沒有得到標(biāo)號，則該流為所求的網(wǎng)絡(luò)最大流（此時(shí)最小割集為已標(biāo)號點(diǎn)與未標(biāo)號點(diǎn)之間的前向?。Y(jié)束；否則重復(fù)②，繼續(xù)標(biāo)號，直到收點(diǎn)t得到標(biāo)號，轉(zhuǎn)③。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)絡(luò)的最大流。最大可調(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)