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

第五章圖與網(wǎng)絡(luò)圖論的基本概念

圖論在網(wǎng)絡(luò)分析中的應(yīng)用最小樹問題最短路問題最大流問題

……圖論的起源

歐拉(Euler)在1736年發(fā)表圖論方面的第一篇論文，解決了著名的哥尼斯堡七橋問題，因此奠定了圖論的基礎(chǔ)。1734年,七橋問題(德國哥尼斯堡)民間流傳難題:一個(gè)人如何一次走遍七座橋且每座橋只走一次?1736年數(shù)學(xué)家歐拉證明了鑒別準(zhǔn)則:一筆劃問題(歐拉定理)在實(shí)際生活中，人們?yōu)榱朔从骋恍ο笾g的關(guān)系，常常在紙上用點(diǎn)和線畫出各種各樣的示意圖。課本例1：圖5－3是我國幾個(gè)城市之間的鐵路交通圖，反映了這幾個(gè)城市間的鐵路分布情況。這里用點(diǎn)代表城市，用點(diǎn)和點(diǎn)之間的聯(lián)線代表這兩個(gè)城市之間的鐵路線。諸如此類的還有電話線分布圖、煤氣管道圖、航空線圖等等。課本例2：圖5-4是五個(gè)球隊(duì)之間比賽的勝負(fù)情況，也可以用圖表示出來。從以上幾個(gè)例子可見可以用由點(diǎn)及點(diǎn)與點(diǎn)的聯(lián)線所構(gòu)成的圖，去反映實(shí)際生活中，某些對象之間的某個(gè)特定的關(guān)系，通常用點(diǎn)代表研究的對象（如城市、球隊(duì)等等），用點(diǎn)與點(diǎn)的聯(lián)線表示這兩個(gè)對象之間有特定的關(guān)系（如兩個(gè)城市間有鐵路線、兩個(gè)球隊(duì)比賽勝負(fù)等）。圖是反映對象之間關(guān)系的一種工具因此，可以說，在一般情況下，圖中點(diǎn)的相對位置如何，點(diǎn)與點(diǎn)之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系，并不是重要的。如例2，也可以用下圖所示的圖去反映五個(gè)球隊(duì)的比賽情況，這與課本上的圖沒有本質(zhì)的區(qū)別。所以，圖論中的圖與幾何圖、工程圖等是不同的。甲丙丁戊乙圖論中的圖與幾何圖、工程圖是不一樣的，圖中點(diǎn)的相對位置、點(diǎn)與點(diǎn)之間連線的長短曲直，對于反映對象之間的關(guān)系并不是重要的。

一、圖與網(wǎng)絡(luò)的基本概念

1、無向圖：由點(diǎn)和邊構(gòu)成的圖，記作G=（V,E）。其中V是點(diǎn)的集合，E是邊的集合。

有向圖：由點(diǎn)和弧組成，記作D=（V，A）。

2、環(huán)（自環(huán)邊）：多重邊（平行邊）：3、簡單圖：不含環(huán)和多重邊的圖；多重圖：含有多重邊但無環(huán)的圖；自環(huán)圖：具有環(huán)但無多重邊的圖；一般圖：允許存在環(huán)和多重邊的圖。v1v2v4v3e1e5e2e3e4v1v2v4v3e1e5e2e3e4v1v2v4v3e1e5e6e2e3e44、次（度）：以v為頂點(diǎn)的邊的條數(shù)稱為v的次.

表示為:d(v)。

懸掛點(diǎn)、懸掛邊：

孤立點(diǎn)：v1v3v2v4v6v5e1e3e5e6e4e8e7e2例：孤立點(diǎn)懸掛點(diǎn)懸掛邊注意：頂點(diǎn)V4的度為4。5、奇點(diǎn)、偶點(diǎn)：度為奇數(shù)的頂點(diǎn)稱為奇點(diǎn)；相應(yīng)的，度為偶數(shù)的頂點(diǎn)為偶點(diǎn)。補(bǔ)充：兩個(gè)定理定理1定理1：在圖G=(V,E)中，所有點(diǎn)的次之和是邊數(shù)的兩倍。即定理2定理2：任一個(gè)圖中，奇點(diǎn)的個(gè)數(shù)為偶數(shù)。證明：設(shè)V1和V2分別是G中奇點(diǎn)和偶點(diǎn)的集合，由定理1，有因是偶數(shù)，也是偶數(shù)故必也是偶數(shù)，從而V1的個(gè)數(shù)是偶數(shù).。練習(xí)下列序列為某個(gè)網(wǎng)絡(luò)圖所有頂點(diǎn)的次的序列，說明它們能否形成一個(gè)簡單圖。（1）2，4，2，3，1，3（2）7，3，5，4，1（3）2，3，3，4，46、子圖：生成子圖（支撐子圖）：v1v2v7V3v5V4V68533312624v2v7V3v5V4V65331262v1v2v7V3v5V4V6533126247、鏈：在圖中，任意兩頂點(diǎn)之間可以構(gòu)成一條由有限個(gè)點(diǎn)與邊（?。┙M成的連續(xù)序列，在序列中點(diǎn)與邊（?。┙惶娉霈F(xiàn)，稱這樣的一個(gè)序列為一條鏈。圈：一條封閉的鏈。v1v3v2v4e1e3e2e5e4簡單鏈：只重復(fù)點(diǎn)、無重復(fù)邊初等鏈：無重復(fù)點(diǎn)、無重復(fù)邊8、路：在一條路中，所有弧的方向均一致?；芈罚阂粭l封閉的路。在無向圖中，鏈與路的概念是一致的；在有向圖中，路一定是鏈，但鏈不一定是路。9、連通圖：圖G中，若任何兩個(gè)不同的點(diǎn)之間，至少存在一條鏈，則稱圖G為連通圖。否則，為非連通圖。v1v4v6v2v5v3連通圖與非連通圖二、樹與最小樹問題樹是一類很有用的簡單圖。樹的定義：一個(gè)無圈的連通無向圖稱為樹。v1v4v2v5v3連通圖v1v4v2v5v3樹樹有以下顯而易見的性質(zhì)：1樹中任意兩頂點(diǎn)間必有且僅有一條路。2在樹中去掉任何一條邊，則圖就不連通。3在樹的兩個(gè)不相鄰的頂點(diǎn)間加一條邊，就得到一個(gè)圈。4含有P個(gè)頂點(diǎn)的樹有p-1條邊。在任一圖G=（V，E）中，當(dāng)點(diǎn)集V確定后，樹圖是G中邊數(shù)最少的連通圖。練習(xí)：下圖中1表示某生產(chǎn)隊(duì)的水源地，其它圖形表示水稻田，用堤埂分割為很多小塊。為了用水灌溉，需要挖開一些堤埂。問最少挖開多少堤埂，才能使水澆灌到每小塊稻田。123456789101112將水源地及每小塊稻田各用一個(gè)點(diǎn)來表示，邊表示它們之間有堤埂相連，那么連接這些點(diǎn)的樹圖的邊數(shù)即為至少要挖開的堤埂數(shù)。生成樹與最小生成樹

生成樹：如果圖G的生成子圖G’是樹，則稱G’為G的生成樹。定理：圖G有生成樹的充要條件是G是連通圖。若將樹作為圖的一個(gè)子圖來考慮14262315例：連通圖G4623生成子圖1是一個(gè)樹4635生成子圖2是一個(gè)樹4223生成子圖3是一個(gè)樹1421生成子圖4是一個(gè)樹1635生成子圖5是一個(gè)樹由樹的定義可知：圖G的生成子圖1、2、3、4、5都是一棵樹，稱為支撐樹。那么，什么是最小生成樹（最小樹）呢？最小樹：已知賦權(quán)無向圖G=(V,E,W)的生成樹為T=(V,E‘)(E’∈E),一棵生成樹所有邊上權(quán)的總和，稱為生成樹的權(quán)。具有最小權(quán)的生成樹T*，稱為最小樹。即：求最小樹的方法有破圈法和避圈法。v1v7v4v3v2v5v620159162532817412336方法一：破圈法步驟：1、先任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊，若在同一個(gè)圈中有幾條都是權(quán)最大邊，則任選其中的一條邊去掉。2、在余下的子圖中，重復(fù)上述步驟，直至沒有圈為止。v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v6201591625328174123v1v7v4v3v2v5v6201591625328174123v1v7v4v3v2v5v61591625328174123v1v7v4v3v2v5v61591625328174123v1v7v4v3v2v5v6925328174123v1v7v4v3v2v5v6925328174123v1v7v4v3v2v5v69328174123v1v7v4v3v2v5v69328174123v1v7v4v3v2v5v693174123總權(quán)數(shù)=1+4+9+3+17+23=57v1v7v4v3v2v5v620159162532817412336方法二：避圈法避圈法：開始選一條最小權(quán)的邊，在以后的每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈，如果同時(shí)有幾條都是最小權(quán)的邊，則可從中任選一條。v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v620159162532817412336總權(quán)數(shù)=1+4+9+3+17+23=57v1v4v5v3v223464524練習(xí)：上圖表示5個(gè)村莊的線路圖，每邊旁的數(shù)字表示村莊之間線路的長度，現(xiàn)要求沿線路架設(shè)有線廣播線，不僅使各村都能聽到有線廣播，而且使廣播線總長度最短。v1v4v5v3v2224v1v4v5v3v223423答案：總長為11隨堂測試1：求最小樹v1v2v4v3v5v6v7v8782344764622315132：有一運(yùn)輸問題如下，試求最優(yōu)運(yùn)輸方案：答案：出現(xiàn)了退化現(xiàn)象。最小元素法求初始方案經(jīng)過兩次調(diào)整，計(jì)算三次檢驗(yàn)數(shù)，最后得到了含退化最優(yōu)解的運(yùn)輸方案：x11=8,x23=4,x24=5,x31=0,x33=1,x32=6;Z*=75

200

150

100

日銷量（需求量噸）

250

75

65

80

乙

200

100

70

90

甲

日產(chǎn)量（供應(yīng)量噸）

C

B

A單位運(yùn)價(jià)城市煤礦運(yùn)輸問題表上作業(yè)法步驟舉例：

450

200

150

100

日銷量（需求量噸）

250

10075

1506580

乙

200

100100

70

10090

甲

日產(chǎn)量（供應(yīng)量噸）

C

B

A單位運(yùn)費(fèi)城市煤礦（一）最小元素法確定初始調(diào)運(yùn)方案初始運(yùn)輸方案為：x11=100，x13=100，x22=150，x23=100，總運(yùn)輸費(fèi)Z0=36250非基變量X12的檢驗(yàn)數(shù)：非基變量X21的檢驗(yàn)數(shù)：

=（c12+c23）-（c13+c22）

=70+75-(100+65)=-20，=（c21+c13）-（c11+c23）=80+100-（90+75）=15。（二）閉回路法計(jì)算檢驗(yàn)數(shù)由于σ12=-20<0，因此初始方案不是最優(yōu)，需要進(jìn)一步調(diào)整。調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X11=10070σ12

=-20100

X13=100

200

A280

σ21=15

65

X22=15075

X23=100

250銷量

100

150

200

450（三）以σ12=-20

處為起始點(diǎn)，畫出閉回路如下：調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X11=10070X12

=100100

200

A280

65

X22=5075

X23=200

250銷量

100

150

200

450調(diào)整量為100，閉回路上調(diào)整如下：

得到調(diào)整后的運(yùn)輸方案為：

x11=100，x12=100，x22=50，x23=200總運(yùn)輸費(fèi)為：Z1=34250（四）閉回路法重新計(jì)算檢驗(yàn)數(shù)

=100+65-(70+75)=20

=80+70-(90+65)=-5由于σ21=-5<0，因此該方案仍不是最優(yōu)，還需要調(diào)整。調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X11=5070

X12=150100

X13

200

A280

X21=50

65

X2275

X23=200

250銷量

100

150

200

450

再次計(jì)算檢驗(yàn)數(shù)，發(fā)現(xiàn)檢驗(yàn)數(shù)均大于0，于是得到了最優(yōu)方案。（五）以σ21=-5

處為起始點(diǎn)作閉回路，調(diào)整量50，調(diào)整后得到：

結(jié)果最優(yōu)調(diào)運(yùn)方案是：

x11=50，x12=150，x21=50，x23=200

相應(yīng)的最小總運(yùn)輸量為：

Zmin=90×50+70×150+80×50+75×200=34000三、最短路問題

最短路問題是對一個(gè)賦權(quán)網(wǎng)絡(luò)圖中指定的兩點(diǎn)Vs和Vt，找到一條路，使得這條路上所有弧的權(quán)值之和最小，稱之為最短路P*。這條路上所有弧的權(quán)值之和稱為從Vs到Vt的距離。應(yīng)用背景——管道鋪設(shè)、線路安排、廠區(qū)布局、設(shè)備更新等。最短路算法：

1．

D氏標(biāo)號(hào)法（Dijkstra）（1）求解思路——從始點(diǎn)出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。

（2）使用條件——網(wǎng)絡(luò)中所有的弧權(quán)均

非負(fù)，即。（3）選用符號(hào)的意義：

①標(biāo)號(hào)P（固定標(biāo)號(hào)或永久性標(biāo)號(hào)）——從始點(diǎn)到該標(biāo)號(hào)點(diǎn)的最短路權(quán)。②標(biāo)號(hào)T（臨時(shí)性標(biāo)號(hào)）——從始點(diǎn)到該標(biāo)號(hào)點(diǎn)的最短路權(quán)上界。（4）

計(jì)算步驟見教材p92-93標(biāo)號(hào)步驟法列表步驟法例:用狄克斯特拉標(biāo)號(hào)步驟法求解下圖所示最短路問題。4v1v2v3v4v7v6v8456475541v5967（5）D氏標(biāo)號(hào)法（Dijkstra）的特點(diǎn)（獲得的附加信息）：

能得到從（起點(diǎn)）到各點(diǎn)的最短路線和最短路長。5127563425527313571練習(xí)1：求從點(diǎn)1到其它各點(diǎn)的最短路。(標(biāo)號(hào)步驟法)1275634231351(0)(2)(3)(4)(7)(8)(13)1275634223351(0)(2)(3)(4)(7)(8)(13)狄克斯特拉列表法例:用狄克斯拉列表法求解下圖所示最短路問題（無向圖）。4v1v2v3v4v6v5v722561413412步驟考察點(diǎn)T標(biāo)號(hào)點(diǎn)集標(biāo)號(hào)（表P標(biāo)號(hào)）1v1{v2，…，v7}v1

v2v3

v4

v5

v6

v7

0------0+20+5

25----23456v2v3v4v5v6{v3，…，v7}{v4，…，v7}{v5，v6，v7}{v5，v7}2+22+42+6

468--4+14+3

587-

5+45+15+4

8696+2

88{v7}8+18反向追蹤，