運籌學(xué)基礎(chǔ)及應(yīng)用第五演示

運籌學(xué)基礎(chǔ)及應(yīng)用第五運籌學(xué)基礎(chǔ)及應(yīng)用第五版胡運權(quán)ppt課件

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

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

圖不同于幾何圖形。一、基本概念1、圖(graph)：由V,E構(gòu)成的有序二元組，用以表示對某些現(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)絡(luò)圖(賦權(quán)圖)：點或邊具有實際意義(權(quán)數(shù))的圖，記做N。零圖：邊集為空集的圖。v1v2v3v4v5e1e2e3e4e5e6e7e8特別的，若邊e的兩個端點重合，則稱e為環(huán)。

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

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

懸掛點次為1的點，如v5

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

孤立點次為0的點

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

奇點

次為奇數(shù)的點,如v55、鏈：圖中保持關(guān)聯(lián)關(guān)系的點和邊的交替序列，其中點可重復(fù)，但邊不能重復(fù)。路：點不能重復(fù)的鏈。圈：起點和終點重合的鏈?；芈罚浩瘘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},若有V1

V2，E1

E2，則稱G1是G2的一個子圖；若V1=V2，E1

E2且

E1≠E2

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

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

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

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

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

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

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

從樹中去掉一條邊，則余下的圖不連通。3、圖的最小部分樹（1）部分樹：若G1是G2的一個部分圖，且G1為樹，則稱G1是G2的一個部分樹（或支撐樹）。G2：ABCD547365576G1：ACBD注意：圖G有部分樹的必要條件是G是連通圖。部分樹不是唯一的。若兩個端點之間多于一條邊，則稱為多重邊。如圖(v1,e1,v2,e2,v3,e3,v4,e5,v5,e6,v3,e7,v6,e8,v7)是一條鏈,但不是路在所有各邊中找到邊權(quán)最小的一條，將其作為最小部分樹中的第一邊；v1v2v3v4⑵構(gòu)造任意兩點間直接到達(dá)、或者最多經(jīng)過1個中間點到達(dá)的最短距離矩陣D（1）=dij（1）第二種做法求解過程：從剩余的子圖中任找一回路，同樣去掉回路中邊權(quán)最大的一條邊，得一新的子圖；簡單圖：無環(huán)、無多重邊的圖。即n=k時結(jié)論也成立。4、矩陣算法

求任意兩點間最短距離的方法1圖的基本概念和模型則2k-1-1<p-22k-1完全偶圖：V1中的每個點均和V2中的每個點相鄰的偶圖。②樹是邊數(shù)最少的連通圖。在剩余的邊中，找到邊權(quán)最小的邊，查看其是否與前面的邊形成圈，如果沒有，則在最小部分樹中添加該邊，如果形成了圈，則不再考慮該邊；（2）最小部分樹（或最小支撐樹）圖G為網(wǎng)絡(luò)圖，若T是部分樹中權(quán)和最小者，則稱T是G的最小部分樹(或稱最小支撐樹).二、最小部分樹的求法1、原理（1）圖中與點v關(guān)聯(lián)的最短邊（即權(quán)最小的邊）一定包含在最小部分樹中。（2）將圖中的點分成兩個互不相交的非空子集，則兩個子集之間連線的最短邊一定包含在最小部分樹中。SABCDET252414317557即求圖中的最小部分樹例：要在下圖所示的各個位置之間建立起通信網(wǎng)絡(luò)，試確定使總距離最小的方案。2、求法方法一：避圈法將圖中所有的點分V為V兩部分，

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

V——非最小部分樹中的點的集合⑴任取一點vi，令vi∈V，其他點在V中 ⑵在V與V相連的邊中取一條最短的邊(vi,vj)，加粗(vi,vj)，令vj∈V ，并在V中去掉vj⑶重復(fù)⑵，至所有的點均在V之內(nèi)。“取小邊”

避圈法另一種做法：1.在所有各邊中找到邊權(quán)最小的一條，將其作為最小部分樹中的第一邊；在剩余的邊中，仍然找到邊權(quán)最小的作為最小部分樹的第二條邊；2.在剩余的邊中，找到邊權(quán)最小的邊，查看其是否與前面的邊形成圈，如果沒有，則在最小部分樹中添加該邊，如果形成了圈，則不再考慮該邊；

3.重復(fù)進(jìn)行第二步，直到找到第n-1條邊為止。（因為有n個頂點的樹中一定有n-1條邊）

例：分別用兩種避圈法構(gòu)造下圖的最小部分樹。

第一種解法：

1.在點集中任選一點，不妨取S，令V={S}

2.找到和S相鄰的邊中，權(quán)值最小的[S,A]。

3.V={S,A}

4.重復(fù)第2，3步，找到下一個點。

第二種做法求解過程：

方法二：破圈法求解步驟：

1.從圖N中任取一回路，去掉這個回路中邊權(quán)最大的邊，得到原圖的一個子圖N1。

2.從剩余的子圖中任找一回路，同樣去掉回路中邊權(quán)最大的一條邊，得一新的子圖；3.重復(fù)第2步，直到圖中不再含有回路為止。

用破圈法求解上例：

1.任意找到一回路，不妨取DETD，去掉邊權(quán)最大的邊[T,E];

2.從剩余的子圖中任找一回路，同樣去掉回路中邊權(quán)最大的一條邊，得一新的子圖；依次類推。

破圈法的另一種解法：

1.從剩余圖中找到邊權(quán)最大的一條邊，如果將其刪除后圖仍然是連通的，則刪除此邊，否則不再考慮此邊；

2.重復(fù)上述步驟，直到剩余邊數(shù)為n-1為止。

用此法求解上述問題：割的容量=9+9=18當(dāng)n=k時，樹至少有一個懸掛點。圖是對現(xiàn)實的抽象，用點和線的連接組合表示。用破圈法求解上例：為滿足題目要求，應(yīng)該選擇不相鄰的點來安排比賽的順序：從剩余的子圖中任找一回路，同樣去掉回路中邊權(quán)最大的一條邊，得一新的子圖；奇點次為奇數(shù)的點,如v5注意：圖G有部分樹的必要條件是G是連通圖。例求圖中S到T的最短路及最短距離。①對發(fā)點s標(biāo)號：s（0，+∞）在樹中不相鄰的兩個點之間添上一條邊，則恰得到一個圈。（1）部分樹：若G1是G2的一個部分圖，且G1為樹，則稱G1是G2的一個部分樹（或支撐樹）。2、點v的標(biāo)號v(x,ε(v))例求圖中S到T的最短路及最短距離。其中dij（3）=min{dir（2）+drj（2）}

注意：

1.一個圖的最小部分樹不唯一，該題中用幾種解法得到的結(jié)果都是相同的，是特殊情況；

2.不同解法得到的最小部分樹所包含的邊雖然可能不相同，但是，每個最小部分樹中所有邊權(quán)的總和一定都是相同的，即都達(dá)到了最小?！?.3最短路問題1、最短路問題從已知的網(wǎng)絡(luò)圖中找出兩點之間距離最短（即權(quán)和最?。┑穆?。2、相關(guān)記號（1）dij表示圖中兩個相鄰點i和j之間的距離（即權(quán)）。易見dii=0

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

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

A

B

E

D

T最短距離：LST=13例求圖中S到T的最短路及最短距離。V1V2V3V4V5V6V752276742136例求圖中v1到v7的最短路。05277610例求圖中任意兩點之間的最短距離。V1V2V3V4V6V7522767421364、矩陣算法

求任意兩點間最短距離的方法⑴構(gòu)造任意兩點間直接到達(dá)的最短距離矩陣記做D(0)=

dij(0)

其中dij(0)=dij注意：D(0)是一個對稱矩陣，且對角線上的元素全是0.D（0）=v1v2v3v4v5v6v7V1052∞∞∞∞V250∞27∞∞V32∞07∞4∞V4∞27062∞V5∞7∞6013V6∞∞42106v7∞∞∞∞360其中dij（1）=min{

dir（0）+drj（0）}

irjdir（0）drj（0）r⑵構(gòu)造任意兩點間直接到達(dá)、或者最多經(jīng)過1個中間點到達(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)造任意兩點間最多可經(jīng)過3個中間點到達(dá)的最短距離矩陣D（2）=

dij（2）

即dij(2)為D(1)中第i行和第j行對應(yīng)元素之和的最小值D（2）=v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340設(shè)樹中任何點的次均不為1.①容量限制條件：對所有弧，0fijcij割的容量=9+9=18當(dāng)n=2時，顯然；（因為有n個頂點的樹中一定有n-1條邊）從剩余的子圖中任找一回路，同樣去掉回路中邊權(quán)最大的一條邊，得一新的子圖；則2k-1-1<p-22k-13、狄克斯屈拉（Dijkstra）標(biāo)號算法當(dāng)D（k+1）=D（k）時，計算結(jié)束；A—C—B—F—E—D6、流（flow）：加在網(wǎng)絡(luò)中弧(vi,vj)上的一組負(fù)載量，用f(vi,vj)或fij表示。問：選擇怎樣的行走路線，可使總行程最短？（3）任何有n個點、n-1條邊的連通圖是樹。4、矩陣算法

求任意兩點間最短距離的方法用c(vi,vj)或cij表示。其中dij（3）=min{

dir（2）+drj（2）

}irjdir（2）drj（2）r⑷構(gòu)造任意兩點間最多可經(jīng)過7個中間點到達(dá)的最短距離矩陣D（3）=

dij（3）

即dij(3)為D(2)中第i行和第j行對應(yīng)元素之和的最小值D（3）=v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340=D（2）故D(2)中的元素就是圖中相應(yīng)兩點之間的最短距離。說明：一般的對于D（k）=

dij（k），其中dij（k）=min

{dir（k-1）+drj（k-1）}，(k=0,1,2,3,…)最多可經(jīng)過2k-1個中間點收斂條件：當(dāng)D（k+1）=D（k）時，計算結(jié)束；設(shè)網(wǎng)絡(luò)圖有p個點，即最多有p-2個中間點，則2k-1-1<p-2

2k-1

k-1<log2(p-1)

k∴k<log2(p-1)+1，即計算到k=

lg(p-1)/lg2+1

時，計算結(jié)束。注意狄克斯屈拉算法矩陣算法優(yōu)點既可以求兩點之間的最短距離，又可以確定最短路求任意兩點之間的最短距離缺點求某兩點之間的最短距離不能確定相應(yīng)兩點之間的最短路

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

先將每一行的元素乘以該村子的學(xué)生人數(shù)，得到小學(xué)建在相應(yīng)村子時，該村學(xué)生上學(xué)時單程所走的路程。再將每一列的元素累加，得到小學(xué)建在相應(yīng)村子時，七個村子的學(xué)生上學(xué)時單程所走的總路程。小學(xué)建在下列村子時，七個村子的學(xué)生上學(xué)時單程所走的路程v1v2v3v4v5v6v701506021021018030020002808020016032050175015012510020014040120060401203502502501500501503602402401206002406004804803601802400總路程17001335143010708357701330故小學(xué)應(yīng)該建在v6村。v1Sv2v3v4T§6.4網(wǎng)絡(luò)的最大流v1Sv2v3v4T一、基本概念和基本結(jié)論2、圖的分類（1）無向圖（簡稱圖）記做G=(V,E)，V、E分別為點集和邊集。（2）有向圖記做D=(V,A），V、A分別為點集和弧集。注意：以下討論的是有向圖。3、弧的容量（簡稱容量）：弧(vi,vj)上可通過負(fù)載的最大能力。用c(vi,vj)或cij表示。1、圖中兩點vi與vj之間的連線有兩種情況（1）邊（edge）:未規(guī)定方向的連線，記做

vi,vj,其中vi,vj稱為端點（2）弧（arc）:規(guī)定方向的連線，記做(vi,vj)，其中vi稱為起點，vj稱為終點4、容量網(wǎng)絡(luò)（簡稱網(wǎng)絡(luò)）：每條弧都有容量的網(wǎng)絡(luò)。8v1Sv2v3v4T799265105例如：5、容量網(wǎng)絡(luò)中點的分類發(fā)點（源點）：用S表示，“只出不入”收點（匯點）：用T表示，“只入不出”中間點：“有入有出”注意：任意容量網(wǎng)絡(luò)總可以轉(zhuǎn)換為只有一個發(fā)點和一個收點的情況。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。易見：零流一定是可行流。每個容量網(wǎng)絡(luò)都有可行流。9、總流量：從發(fā)點s到收點t的流量,記做V(f)7、可行流(記做f)：能夠在網(wǎng)絡(luò)中通過的流，必須滿足以下兩個條件： ①容量限制條件：對所有弧，0

fij

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

12、割的容量：割集中各弧的容量之和。13、最小割：所有割集中容量之和最小的一個割集。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ā)點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)μ+μ+μ+μ-這是一條增廣鏈定理：當(dāng)網(wǎng)絡(luò)中不存在增廣鏈時，網(wǎng)絡(luò)達(dá)到最大流狀態(tài)。二、網(wǎng)絡(luò)最大流的求法

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

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

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

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

ij=fij+ε(t)

對后向弧μ-，新流量f

ij=fij-ε(t)

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

若標(biāo)號中斷，即t沒有得到標(biāo)號，則該流為所求的網(wǎng)絡(luò)最大流（此時最小割集為已標(biāo)號點與未標(biāo)號點之間的前向弧），結(jié)束；否則重復(fù)②，繼續(xù)標(biāo)號，直到收點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)5(3)(0