運(yùn)籌學(xué)第7章

1、Chapter6 圖與網(wǎng)絡(luò)分析( Graph Theory and Network Analysis ),,圖的基本概念與模型樹與圖的最小樹最短路問題網(wǎng)絡(luò)的最大流,本章主要內(nèi)容：,學(xué)習(xí)要點(diǎn)：1.掌握一般圖論及其基本概念； 2.能夠應(yīng)用最短路算法求解實(shí)際問題； 3.掌握最大流最小割理論。,6.1 圖的基本概念和模型,長(zhǎng),江,漢,江,武昌,漢口,漢陽(yáng),您能從武漢理工大學(xué)出發(fā)走

2、過(guò)每座橋且只走一次然后回到學(xué)校嗎?,圖的基本概念與模型,18世紀(jì)，Königsberg是俄羅斯的一個(gè)城市（現(xiàn)為加里寧格勒）。市內(nèi)有七座橋。人們?cè)诖松⒉?，問：“能否從某處出發(fā)，經(jīng)過(guò)每座橋一次且恰好一次又回到出發(fā)點(diǎn)？”,1736年，Euler巧妙地將此問題化為圖的不重復(fù)一筆畫問題，并證明了該問題不存在肯定回答，發(fā)表了第一篇論文。,七橋問題,圖的基本概念與模型,這個(gè)問題是基于一個(gè)現(xiàn)實(shí)生活中的事例:位于當(dāng)時(shí)東普魯士柯尼斯堡(今日俄羅斯

3、加里寧格勒)有一條河，河中心有兩個(gè)小島。小島與河的兩岸有七條橋連接。如何才能在所有橋都恰巧只走一遍的前提下，回到原出發(fā)點(diǎn)？,圖的基本概念與模型,不少數(shù)學(xué)家都嘗試去解析這個(gè)事例。而這些解析，最后發(fā)展成為了數(shù)學(xué)中的圖論。 萊昂哈德·歐拉(Leonhard Euler)在1736年圓滿地解決了這一問題，證明這種方法并不存在。他在圣彼得堡科學(xué)院發(fā)表了圖論史上第一篇重要文獻(xiàn)。歐拉把實(shí)際的抽象問題簡(jiǎn)化為平面上的點(diǎn)與線組合，每

4、一座橋視為一條線，橋所連接的地區(qū)視為點(diǎn)。這樣若從某點(diǎn)出發(fā)后最后再回到這點(diǎn)，則這一點(diǎn)的線數(shù)必須是偶數(shù)。,圖的基本概念與模型,A,C,B,D,A,C,B,D,如何才能在所有橋都恰巧只走一遍的前提下，回到原出發(fā)點(diǎn)？,求從圖中任一點(diǎn)出發(fā)，通過(guò)每條邊一次，最后回到起點(diǎn)。,橋所連接的地區(qū)視為點(diǎn),每一座橋視為一條線,圖的基本概念與模型,如果通奇數(shù)座橋的地方不止兩個(gè)，那么滿足要求的路線便不存在了。 如果只有兩個(gè)地方通奇數(shù)座橋，則可從其

5、中一地出發(fā)可找到經(jīng)過(guò)所有橋的路線。 若沒有一個(gè)地方通奇數(shù)座橋，則從任何一地出發(fā)，所求的路線都能實(shí)現(xiàn)。,圖的基本概念與模型,中國(guó)郵路問題,一郵遞員送信，要走完他所負(fù)責(zé)的全部街道分送信件，最后返回郵局。郵遞員都會(huì)本能地以盡可能少的行程完成送信任務(wù)。如何走路線最短。,1962年，由我國(guó)數(shù)學(xué)家管梅谷提出，國(guó)際上稱為中國(guó)郵遞員問題。問題：求一個(gè)圈，過(guò)每邊至少一次，并使圈的長(zhǎng)度最短。,圖的基本概念與模型,Hamilton圖,游戲

6、：用正十二面體上20個(gè)頂點(diǎn)表示20個(gè)城市，要求參加游戲者沿著各邊行走，走遍每一個(gè)城市且僅走一次，最后回到出發(fā)城市。,問題：如何判斷一個(gè)圖是否具有這樣的性質(zhì)。如果有，這樣的行走路線如何確定。,,the dodecahedron is Hamiltonian,顯然這樣的路線存在且不唯一,圖的基本概念與模型,在一個(gè)棋盤中，若馬（馬走日步）能否從某一點(diǎn)出發(fā)跳遍棋盤上每一點(diǎn)恰好一次，再回到出發(fā)點(diǎn)？對(duì)于4×4，5×5，或8&#

7、215;8的棋盤上馬的跳動(dòng)如何？,圖的基本概念與模型,,幻方問題,圖的基本概念與模型,某團(tuán)體舉行舞會(huì)，其中有n 個(gè)男士與n 個(gè)女士，每個(gè)男士恰好認(rèn)識(shí) r 個(gè)女士，每個(gè)女士也恰好認(rèn)識(shí) r 個(gè)男士。問：在這個(gè)團(tuán)中，能否做到：每個(gè)男士與其認(rèn)識(shí)的女士跳舞，每個(gè)女士也與其認(rèn)識(shí)的男士跳舞。,比如：任意6個(gè)人，一定有3個(gè)人相互認(rèn)識(shí)或者有3個(gè)人相互不認(rèn)識(shí),鴿籠原理和Ramsey數(shù),圖的基本概念與模型,四色猜想,能否用四種顏色給地圖染色，使相鄰的國(guó)家

8、有不同的顏色。,問題：能否用四種顏色給平面圖的點(diǎn)染色，使有公共邊的點(diǎn)有不同的顏色。,圖的基本概念與模型,公元1852年，格里斯發(fā)現(xiàn)無(wú)論多么復(fù)雜的地圖，只要用四種顏色就能將相鄰的區(qū)域區(qū)分開來(lái)，這就是所謂“四色猜想”。直到公元1976年，才由美國(guó)數(shù)學(xué)家同時(shí)操作三臺(tái)超大型計(jì)算機(jī)作了近200億個(gè)邏輯判斷，花費(fèi)1200個(gè)機(jī)時(shí)，才取得了“四色猜想”的證明。,圖的基本概念與模型,Möbius在1840年的一次演講中提出如下問題：一個(gè)國(guó)王有

9、五個(gè)兒子，要求在他死后將國(guó)土分成五部分，每個(gè)兒子占一部分并建立各自的宮殿。要求每座宮殿之間都有（平面的）路相連且互不相交（不允許立體交叉）。,Tietze研究后指出這是不可能的。因?yàn)?個(gè)頂點(diǎn)的完全圖不是平面圖。平面圖在印刷電路板中有重要的應(yīng)用。,平面圖與網(wǎng)絡(luò),圖的基本概念與模型,點(diǎn)：研究對(duì)象（陸地、路口、國(guó)家、球隊(duì)）；,點(diǎn)間連線：對(duì)象之間的特定關(guān)系（陸地間有橋、路口之間道路、兩國(guó)邊界、兩球隊(duì)比賽及結(jié)果)。,對(duì)稱關(guān)系：橋、道路、邊界

10、；,用不帶箭頭的連線表示，稱為邊。,非對(duì)稱關(guān)系：甲隊(duì)勝乙隊(duì)，用帶箭頭的連線表示，稱為弧。,圖：點(diǎn)及邊（或?。┙M成。,實(shí)際生活中，人們經(jīng)常用“圖”來(lái)表示一些對(duì)象以及這些對(duì)象之間的特定關(guān)系。,如公路或鐵路交通圖、管網(wǎng)圖、通訊聯(lián)絡(luò)圖等。,圖的基本概念與模型,對(duì)所要研究的問題確定具體對(duì)象及這些對(duì)象間的性質(zhì)關(guān)系，并用圖的形式表示出來(lái)，這就是對(duì)所研究原問題建立的模型。圖是反映對(duì)象之間關(guān)系的一種工具。,這里所研究的圖與平面幾何中的圖不同。這里只關(guān)心圖

11、中有多少個(gè)點(diǎn)，點(diǎn)與點(diǎn)之間有無(wú)連線，至于連線的方式是直線還是曲線，點(diǎn)與點(diǎn)的相對(duì)位置如何，都是無(wú)關(guān)緊要的。是組合意義下的圖。圖的理論和方法，就是從形形色色的具體的圖以及與它們相關(guān)的實(shí)際問題中，抽象出共同性的東西，找出其規(guī)律、性質(zhì)、方法，再應(yīng)用到解決實(shí)際問題中去。,圖的基本概念與模型,圖論(Graph Theory)是運(yùn)籌學(xué)中的一個(gè)重要分支，主要研究具有某種二元關(guān)系的離散系統(tǒng)的組合結(jié)構(gòu)和性質(zhì)。隨著電子計(jì)算機(jī)的蓬勃發(fā)展，圖論不僅得到了迅速發(fā)

12、展，而且應(yīng)用非常廣泛。它直觀清晰，使用方便，易于掌握。應(yīng)用領(lǐng)域：物理學(xué)、化學(xué)、控制論、信息論、管理科學(xué)、通信系統(tǒng)、交通運(yùn)輸系統(tǒng)、建筑、計(jì)算機(jī)科學(xué)、生產(chǎn)工藝流程以及軍事后勤保障系統(tǒng)等的問題常用圖論模型來(lái)描述。網(wǎng)絡(luò)規(guī)劃是圖論與線性規(guī)劃的交叉學(xué)科,具有廣泛的應(yīng)用背景，比如，最短路問題、最小樹問題、最大流問題、最優(yōu)匹配問題等.,圖的基本概念與模型,圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之

13、間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。,圖的基本概念與模型,圖的定義：若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，則圖G可以定義為點(diǎn)和邊的集合，記作：,其中: V——點(diǎn)集 E——邊集,※ 圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以及哪些點(diǎn)之間有連線。,當(dāng)V, E為有限集合時(shí)，G稱為有限圖，否則，稱為無(wú)限圖.,端點(diǎn),關(guān)聯(lián)邊,相鄰,若有邊e可表示為e=[vi,vj]，稱vi和vj是邊e的端點(diǎn)，反之稱邊e

14、為點(diǎn)vi或vj的關(guān)聯(lián)邊。若點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；若邊ei和ej具有公共的端點(diǎn)，稱邊ei和ej相鄰。,圖的基本概念與模型,在一個(gè)圖的幾何實(shí)現(xiàn)中，兩條邊的交點(diǎn)可能不是圖的頂點(diǎn)。例如,,,,,,,,,有時(shí)也用 m(G)=|E| 表示圖 G 中的邊數(shù)，用 n(G)=|V| 表示圖 G 中的頂點(diǎn)個(gè)數(shù)，簡(jiǎn)記為m, n.,圖 G 中的點(diǎn)數(shù)記為 p(G)，邊數(shù)記為q(G) .此時(shí)，圖 G 可以表示為G = ( p, q ).

15、,通常，圖的頂點(diǎn)可用平面上的一個(gè)點(diǎn)來(lái)表示，邊可用平面上的線段來(lái)表示（直的或曲的），而邊僅在端點(diǎn)處相交， 這樣畫出的平面圖形稱為圖的圖示。,平面圖,環(huán), 多重邊, 簡(jiǎn)單圖,如果邊e的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)之間多于一條，稱為多重邊，如右圖中的e4和e5，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱作簡(jiǎn)單圖。只有一個(gè)頂點(diǎn)的圖稱為平凡圖；邊集是空集的圖稱為空?qǐng)D。,圖的基本概念與模型,完全圖是每一對(duì)不同頂點(diǎn)都恰有一邊的簡(jiǎn)單圖；具有 n

16、 個(gè)頂點(diǎn)的完全圖記為K n.,完全圖,K3,K4,K5,K5,n-方體Qn,,,,,n方體,n 維立方體n = 3 的情形，上底下底是兩個(gè)2維立方體。對(duì)應(yīng)頂點(diǎn)連線后( 同時(shí)把上底中頂點(diǎn)標(biāo)號(hào)末位加號(hào)0，下底中頂點(diǎn)標(biāo)號(hào)末位加號(hào)1 ) 得到3維立方體。,G的補(bǔ)圖(complement)： 設(shè)G 是一個(gè)圖，以V (G) 為頂點(diǎn)集，以{(x, y) | (x, y) ? E(G)}為邊集的圖稱為G 的補(bǔ)圖，記為GC。,次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn),與某

17、一個(gè)點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為點(diǎn)vi的次（也叫做度），記作d(vi)。右圖中d(v1)＝４,d(v3)=5,d(v5)=1。次為奇數(shù)的點(diǎn)稱作奇點(diǎn)，次為偶數(shù)的點(diǎn)稱作偶點(diǎn)，次為1的點(diǎn)稱為懸掛點(diǎn)，次為0的點(diǎn)稱作孤立點(diǎn)。,圖的次: 一個(gè)圖的次等于各點(diǎn)的次之和。,圖的基本概念與模型,鏈，圈，連通圖,圖中某些點(diǎn)和邊的交替序列，若其中各邊互不相同，且對(duì)任意vi,t-1和vit均相鄰稱為鏈。用μ表示：,起點(diǎn)與終點(diǎn)重合的鏈稱作圈。如果每一對(duì)頂點(diǎn)之間至少存

18、在一條鏈，稱這樣的圖為連通圖，否則稱圖不連通。,圖的基本概念與模型,二部圖（偶圖）,圖G=(V,E)的點(diǎn)集V可以分為兩各非空子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任意兩個(gè)頂點(diǎn)均不相鄰，稱這樣的圖為偶圖。,(a),(b),(c),,(a)明顯為二部圖，(b)也是二部圖，但不明顯，改畫為(c)時(shí)可以清楚看出。,圖的基本概念與模型,完全二分圖是具有二分劃(X,Y)的二分圖，并且X的每個(gè)頂點(diǎn)與Y的每個(gè)頂點(diǎn)都相連。完全二分

19、圖記為Km,n,K3,3 K2,4,子圖，部分圖(支撐子圖),圖G1={V1、E1}和圖G2={V2，E2}如果有 稱G1是G2的一個(gè)子圖。若有 ，則稱G1是G2的一個(gè)部分圖(支撐子圖)。,(a),(b),（G圖）,圖的基本概念與模型,頂點(diǎn)導(dǎo)出子圖,設(shè)W是圖G的一個(gè)非空頂點(diǎn)子集,以W為頂

20、點(diǎn)集，以二端點(diǎn)均在W中的邊的全體為邊集的子圖稱為由W導(dǎo)出的G的子圖，簡(jiǎn)稱導(dǎo)出子圖，記為G[W]。導(dǎo)出子圖G[V- W]記為G-W，即,它是從G中刪除W中頂點(diǎn)以及與這些頂點(diǎn)相關(guān)聯(lián)的邊所得到的子圖。,,,,,,,,e1,e3,e2,G,v3,v4,v5,v2,v1,,,,e3,e2,v3,v4,v2,G[v2 ,v3 ,v4 ],G-{v1 ,v5 },,,,,,,邊導(dǎo)出子圖,設(shè)F是圖G的非空邊子集，以F為邊集，以F中邊的端點(diǎn)全體為頂點(diǎn)集

21、所構(gòu)成的子圖稱為由F導(dǎo)出的G的子圖，簡(jiǎn)稱G的邊導(dǎo)出子圖。記為G[F]。記 G-F 表示以 E(G)\F 為邊集的G的支撐子圖，它是從G中刪除F 中的邊所得到的子圖。,,,,,,,,e1,e3,e2,G,v3,v4,v5,v2,v1,G[e1 ,e2 ,e3 ],G - e1,,,,,e1,e3,e2,v3,v4,v2,v1,圖的運(yùn)算,or,G2,G1,G2,G1,G2,G1,網(wǎng)絡(luò)（賦權(quán)圖）,設(shè)圖G＝（V，E），對(duì)G的每一條邊(vi,v

22、j)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊(vi,vj)的權(quán)，賦予權(quán)的圖G稱為網(wǎng)絡(luò)(或賦權(quán)圖）。權(quán)可以代表距離、費(fèi)用、通過(guò)能力(容量)等等。端點(diǎn)無(wú)序的賦權(quán)圖稱為無(wú)向網(wǎng)絡(luò)，端點(diǎn)有序的賦權(quán)圖稱為有向網(wǎng)絡(luò)。,圖的基本概念與模型,出次與入次,有向圖中，以vi為始點(diǎn)的邊數(shù)稱為點(diǎn)vi的出次，用d+(vi)表示；以vi為終點(diǎn)的邊數(shù)稱為點(diǎn)vi 的入次，用表示d-(vi) ；vi 點(diǎn)的出次和入次之和就是該點(diǎn)的次。,※ 有向圖中，所有頂點(diǎn)的入次之和等于

23、所有頂點(diǎn)的出次之和。,圖的基本概念與模型,一個(gè)圖是二部圖當(dāng)且僅當(dāng)它不含奇圈。,設(shè)G 是一個(gè)簡(jiǎn)單圖，若δ (G) ≥ 2 ，則G 中必含有圈。,設(shè)G 是簡(jiǎn)單圖，若δ (G) ≥ 3 ,則G 必有偶圈。,設(shè)有2n 個(gè)電話交換臺(tái)，每個(gè)臺(tái)與至少n 個(gè)臺(tái)有直通線路，則該交換系統(tǒng)中任二臺(tái)均可實(shí)現(xiàn)通話。,回答：,事實(shí)上，假如G 不連通，則至少有一個(gè)連通分支的頂點(diǎn)數(shù)不超過(guò)n。在此連通分支中，頂點(diǎn)的度至多是n ? 1。這與δ (G) ≥ n 矛盾。證畢。

24、,證明：構(gòu)造圖G 如下：以交換臺(tái)作為頂點(diǎn)，兩頂點(diǎn)間連邊當(dāng)且僅當(dāng)對(duì)應(yīng)的兩臺(tái)間有直通線路。,問題化為：已知圖G 有2n 個(gè)頂點(diǎn)，且δ (G) ≥ n ，求證G 連通。,,例1,證明： 必要性：設(shè) C = v 0 v 1 … v k v 0 是二部圖G = (X U Y , E) 的一個(gè)圈。無(wú)妨設(shè)v 0 ∈ X ，由二部圖的定義知,v 1 ∈Y ，v 2 ∈ X ， …，一般地，v 2 i ∈ X ，v 2 i +1 ∈ Y ，（ i =

25、 0,1,…）。又因v 0 ∈ X ，故v k ∈ Y ，因而k 是奇數(shù)。注意到圈C 上共有k + 1條邊，因此是偶圈。,充分性：設(shè)G 不含奇圈。取u ∈V (G) ，令X = {v ∈V (G) | d(u, v)＝odd}，Y = {v ∈V (G) | d(u, v)＝even}。,（1）如果 P = Q + v 2 v 1或 Q = P + v 1 v 2 ，則 v 1, v 2到u 的距離奇偶性相反， v 1 , v 2分

26、屬于X和Y。（2）否則，設(shè)u′是P 與Q 的最后一個(gè)公共頂點(diǎn)，因P 的(u, u′) 段和Q 的(u, u′) 段都是u到u′的最短路，故這兩段長(zhǎng)度相等。,假如P，Q 的奇偶性相同，則P 的(u′ , v 1 ) 段和Q 的(u′ , v 2 ) 段奇偶性相同，這兩段與邊e 構(gòu)成一個(gè)奇圈，與定理?xiàng)l件矛盾?？梢奝，Q 的奇偶性不同，從而 v 1, v 2分屬于X 和Y。,任取一條邊 e = v 1 v 2 ，欲證 v 1, v 2分屬于

27、X 和Y。 設(shè)P，Q 分別是u 到 v 1, v 2的最短路。,這便證明了G 是一個(gè)二部圖。 證畢。,由定理可知圖 (a) 所示的圖不是二分圖，因?yàn)樗粋€(gè)長(zhǎng)為3的圈 ,圖 (b) 所示的圖是一個(gè)二分圖，它不含長(zhǎng)為奇數(shù)的圈.,證明：設(shè)G 中的最長(zhǎng)路為 P = v0v1 …v k 。因d (v 0) ≥ 2 ，故存在與 v 1相異的頂點(diǎn)v 與 v 0相鄰。若v ? P ，則得到比P 更長(zhǎng)的

28、路，這與P 的取法矛盾。因此必定v ∈ P ，從而G 中有圈。證畢。,證明：設(shè) P =v0v1 …v k是G 的最長(zhǎng)路。 因?yàn)閐 (v 0) ≥ 3 ， 所以存在兩個(gè)與 v 1相異的頂點(diǎn)v′, v" 與 v 0相鄰。v′, v"必都在路P 上，否則會(huì)得到比P 更長(zhǎng)的路。無(wú)妨設(shè)v ′ = v i , v" = v j , (i < j ) 。 若i, j 中有奇數(shù)，比如

29、i 是奇數(shù)，則路P 上 v 0到v i的一段與邊 v 0 v i 構(gòu)成一個(gè)偶圈； 若i, j 都是偶數(shù)，則路P 上v i到 v j的一段與邊 v 0 v i 及v 0 v j構(gòu)成一個(gè)偶圈。證畢。,圖的模型應(yīng)用,有甲，乙，丙，丁，戊，己6名運(yùn)動(dòng)員報(bào)名參加A，B，C，D，E，F(xiàn) 6個(gè)項(xiàng)目的比賽。下表中打√的是各運(yùn)動(dòng)員報(bào)告參加的比賽項(xiàng)目。問6個(gè)項(xiàng)目的比賽順序應(yīng)如何安排，做到每名運(yùn)動(dòng)員都不連續(xù)地參加兩項(xiàng)比賽。,圖的基本概念與模型,例

30、1,解：用圖來(lái)建模。把比賽項(xiàng)目作為研究對(duì)象，用點(diǎn)表示。如果2個(gè)項(xiàng)目有同一名運(yùn)動(dòng)員參加，在代表這兩個(gè)項(xiàng)目的點(diǎn)之間連一條線，可得下圖。,在圖中找到一個(gè)點(diǎn)序列，使得依次排列的兩點(diǎn)不相鄰，即能滿足要求。如：1) A,C,B,F,E,D2) D,E,F,B,C,A,圖的基本概念與模型,一個(gè)班級(jí)的學(xué)生共計(jì)選修A、B、C、D、E、F六門課程，其中一部分人同時(shí)選修D(zhuǎn)、C、A，一部分人同時(shí)選修B、C、F，一部分人同時(shí)選修B、E，還有一部分人同時(shí)選

31、修A、B，期終考試要求每天考一門課，六天內(nèi)考完，為了減輕學(xué)生負(fù)擔(dān)，要求每人都不會(huì)連續(xù)參加考試，試設(shè)計(jì)一個(gè)考試日程表。,思考題,圖的基本概念與模型,思考題解答：以每門課程為一個(gè)頂點(diǎn)，共同被選修的課程之間用邊相連，得圖，按題意，相鄰頂點(diǎn)對(duì)應(yīng)課程不能連續(xù)考試，不相鄰頂點(diǎn)對(duì)應(yīng)課程允許連續(xù)考試，因此，作圖的補(bǔ)圖，問題是在圖中尋找一條哈密頓道路，如C—E—A—F—D—B，就是一個(gè)符合要求的考試課程表。,圖的基本概念與模型,,,,,,,A,F,

32、E,D,C,B,,,,,,,,,圖的基本概念與模型,,,A,F,E,D,C,B,,,,,,,,,,,,,,,,,,圖的基本概念與模型,圖的基本性質(zhì)：,定理1 任何圖中，頂點(diǎn)次數(shù)之和等于所有邊數(shù)的2倍。,定理2 任何圖中，次為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè)。,證明：由于每條邊必與兩個(gè)頂點(diǎn)關(guān)聯(lián)，在計(jì)算點(diǎn)的次時(shí)，每條邊均被計(jì)算了兩次，所以頂點(diǎn)次數(shù)的總和等于邊數(shù)的2倍。,證明：設(shè)V1和V2分別為圖G中奇點(diǎn)與偶點(diǎn)的集合。由定理1可得：,2m為偶數(shù)，且偶

33、點(diǎn)的次之和 也為偶數(shù)，所以 必為偶數(shù)，即奇數(shù)點(diǎn)的個(gè)數(shù)必為偶數(shù)。,圖的基本概念與模型,圖的矩陣描述：如何在計(jì)算機(jī)中存儲(chǔ)一個(gè)圖呢？現(xiàn)在已有很多存儲(chǔ)的方法，但最基本的方法就是采用矩陣來(lái)表示一個(gè)圖，圖的矩陣表示也根據(jù)所關(guān)心的問題不同而有：鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等,1. 鄰接矩陣對(duì)于圖G=（V，E），| V |=n， | E |=m，有n?n階方矩陣A=(aij) n?n，其中,圖的基本概

34、念與模型,下圖所表示的圖可以構(gòu)造鄰接矩陣A如下,圖的基本概念與模型,例2,2. 關(guān)聯(lián)矩陣對(duì)于圖G=(V,E), | V |=n, | E |=m, 有m?n階矩陣M=(mij) m?n，其中:,3. 權(quán)矩陣,對(duì)于賦權(quán)圖G=(V,E), 其中邊 有權(quán) , 構(gòu)造矩陣B=(bij) n?n 其中：,圖的基本概念與模型,可見：（1）M(G)和A(G)的元素是0，1 或2。若G 是簡(jiǎn)單圖，則只有0 和1；,

35、（2）A(G)是對(duì)稱矩陣；,（3）M(G)中每列之和＝2；M(G)中第i 行之和＝vi 的度； 若G 中無(wú)環(huán)邊，則A(G)中第i 行（列）之和＝M(G)中第i 行之和＝vi 的度。,v1v2v3v4v5v6v7v8,,下圖所表示的圖可以構(gòu)造鄰接矩陣M如下:,M=（mij）=,1 0 1 0 0 0 0 0 0 0

36、 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0

37、 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0

38、0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0,圖的基本概念與模型,例3,下圖所表示的圖可以構(gòu)造權(quán)矩陣B如下:,圖的基本概念與模型,例4,6.2 樹與圖的最小樹,樹是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。

39、在自然和社會(huì)領(lǐng)域應(yīng)用極為廣泛。,乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下圖所示。,運(yùn)動(dòng)員,樹與圖的最小樹,某企業(yè)的組織機(jī)構(gòu)圖也可用樹圖表示。,樹與圖的最小樹,樹是一個(gè)不包含圈的簡(jiǎn)單連通圖。樹中度為1的點(diǎn)稱為樹葉，度大于1的點(diǎn)稱為分枝點(diǎn)。具有k個(gè)連通分支的不包含圈的圖稱為k-樹，或森林。下是具有六個(gè)頂點(diǎn)的樹，圖中的每棵樹都只有5條邊，并且至少有2個(gè)頂點(diǎn)的次數(shù)是1。,樹：無(wú)圈的連通圖即為樹,性質(zhì)1：任何樹中必存在次為1的點(diǎn)。

40、性質(zhì)2：n 個(gè)頂點(diǎn)的樹必有n-1 條邊。性質(zhì)3：樹中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。性質(zhì)4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)5：樹無(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)圈。,樹與圖的最小樹,圖的最小部分樹(支撐樹),如果G2是G1的部分圖，又是樹圖，則稱G2是G1的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝。一般圖G1含有多個(gè)部分樹，其中樹枝總長(zhǎng)最小的部分樹，稱為該圖的最小部分樹（或最小支撐樹）。,G1,

41、G2,樹與圖的最小樹,求樹的方法：破圈法和避圈法,破圈法,,,,樹與圖的最小樹,,部分樹,樹與圖的最小樹,避圈法,樹與圖的最小樹,賦權(quán)圖中求最小樹的方法：破圈法和避圈法,破圈法：任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。,,,,,,,,,,,v1,v2,v3,v4,v5,v6,4,3,5,2,1,,,,,,,,,,,邊數(shù)＝n-1=5,樹與圖的最小樹,得到最小樹：,Min C(T)=15,樹與圖的最小樹,避圈法:去掉G中所有邊，得到n個(gè)孤

42、立點(diǎn)；然后加邊。加邊的原則為：從最短邊開始添加，加邊的過(guò)程中不能形成圈，直到點(diǎn)點(diǎn)連通(即:n-1條邊)。,樹與圖的最小樹,,,,,,,,,,,,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min C(T)=15,樹與圖的最小樹,練習(xí)：應(yīng)用破圈法求最小樹,樹與圖的最小樹,樹與圖的最小樹,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,樹

43、與圖的最小樹,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,樹

44、與圖的最小樹,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,

45、,,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,m

46、in=1+4+9+3+17+23=57,樹與圖的最小樹,,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,練習(xí)：應(yīng)用避圈法求最小樹,樹與圖的最小樹,,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,樹與圖的最小樹,,,,,,,,,,,,,,,,,,,,

47、v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,樹與圖的最小樹,,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,樹與圖的最小樹,,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,樹與圖的最小樹

48、,,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,樹與圖的最小樹,,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,min=1+4+9+3+17+23=57,樹與圖的最小樹,課堂練習(xí)：,Min C(T)=12,Min C(T)=15,答案：,樹與圖的

49、最小樹,,,,,,,,,,,3,4,1,2,2,3,2,3,2,4,2,Min C(T)=12,Min C(T)=18,樹與圖的最小樹,6.3 最短路問題,如何用最短的線路將三部電話連起來(lái)？此問題可抽象為設(shè)△ABC為等邊三角形，連接三頂點(diǎn)的路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個(gè)，其中最短路線者顯然是二邊之和（如AB∪AC）。,,,,A,B,C,,最短路問題,,,,,,,A,B,C,P,但若增加一個(gè)周轉(zhuǎn)站（新點(diǎn)P），連接4點(diǎn)的新網(wǎng)絡(luò)

50、的最短路線為PA＋PB＋PC。最短新路徑之長(zhǎng)比原來(lái)只連三點(diǎn)的最短路徑要短。這樣得到的網(wǎng)絡(luò)不僅比原來(lái)節(jié)省材料，而且穩(wěn)定性也更好。,最短路問題,問題描述：就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路。有些問題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。,最短路問題,渡河游戲一老漢帶了一只狼、一只羊、一棵白菜想要從南

51、岸過(guò)河到北岸，河上只有一條獨(dú)木舟，每次除了人以外，只能帶一樣?xùn)|西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，問應(yīng)該怎樣安排渡河，才能做到既把所有東西都運(yùn)過(guò)河去，并且在河上來(lái)回次數(shù)最少？這個(gè)問題就可以用求最短路方法解決。,最短路問題,例1,定義：1）人—M（Man），狼—W（Wolf）， 羊—G（Goat）， 草—H（Hay）2） 點(diǎn)—— vi 表示河岸的狀態(tài)3） 邊—— ek 表示由狀態(tài) vi 經(jīng)一次渡河到狀態(tài) vj

52、4） 權(quán)——邊 ek 上的權(quán)定為 1,我們可以得到下面的加權(quán)有向圖,最短路問題,狀態(tài)說(shuō)明：v1,u1 =( M,W,G,H ); v2,u2 =(M,W,G); v3,u3 =(M,W,H); v4,u4=(M,G,H); v5,u5 =(M,G),此游戲轉(zhuǎn)化為在下面的二部圖中求從 v1 到 u1 的最短路問題。,,v1,v2,v3,v4,v5,u5,u4,u3,u2,u1,,,,,,,,,,,,,,,,,,,,,,,,,,最短路問

53、題,求最短路有兩種算法:,狄克斯屈拉(Dijkstra)標(biāo)號(hào)算法 逐次逼近算法,最短路問題,狄克斯屈拉(Dijkstra)標(biāo)號(hào)算法的基本思路：若序列{ vs，v1…..vn-1，vn }是從vs到vt間的最短路，則序列{ vs，v1…..vn-1 } 必為從vs 到vn-1的最短路。,假定v1→v2 →v3 →v4是v1 →v4的最短路，則v1 →v2 →v3一定是v1 →v3的最短路，v2 →v3 →v4也一定是v2 →v

54、4的最短路。,最短路問題,Dijkstra算法基本步驟,Dijkstra算法的基本思想是從vs出發(fā)，逐步地向外探尋最短路，采用標(biāo)號(hào)法。執(zhí)行過(guò)程中，與每個(gè)點(diǎn)對(duì)應(yīng)，記錄下一個(gè)數(shù)（稱為這個(gè)點(diǎn)的標(biāo)號(hào)），它或者表示從vs到該點(diǎn)的最短路長(zhǎng)（稱為P標(biāo)號(hào)），或者是從vs到該點(diǎn)的最短路長(zhǎng)的上界（稱為T標(biāo)號(hào)）。算法每一步都把某個(gè)頂點(diǎn)的T 標(biāo)號(hào)改為P 標(biāo)號(hào)， 當(dāng)終點(diǎn)vt 得到 P 標(biāo)號(hào)時(shí)，計(jì)算結(jié)束。最多n-1步。,最短路問題,網(wǎng)絡(luò)圖的最短路圖的起點(diǎn)是v

55、s，終點(diǎn)是vt ，以vi為起點(diǎn)vj為終點(diǎn)的弧記為 (i, j)，距離為dij。,P標(biāo)號(hào)(點(diǎn)標(biāo)號(hào))：b(j) —起點(diǎn)vs到點(diǎn)vj的最短路長(zhǎng)；T標(biāo)號(hào)(邊標(biāo)號(hào))：k(i,j)=b(i)+dij。,最短路問題,步驟：,2. 找出所有vi已標(biāo)號(hào)vj未標(biāo)號(hào)的弧集合 B={(i, j)} 如果這樣的弧不存在或vt已標(biāo)號(hào)則計(jì)算結(jié)束；,3. 計(jì)算集合B中弧k(i，j)=b(i)+dij的標(biāo)號(hào);,4. 選一個(gè)點(diǎn)標(biāo)號(hào)

56、 在終點(diǎn)vl處標(biāo)號(hào)b(l), 返回到第2步。,1. 令起點(diǎn)的標(biāo)號(hào)；b(s)＝0。,最短路問題,求連接 vs、vt 的最短路.,開始，給vs以 P 標(biāo)號(hào)，P(vs)=0,其余各點(diǎn)給 T 標(biāo)號(hào) T(vi)=+∞.,Step 1:,迭代 1,Dijkstra算法基本步驟：,例2,最短路問題,,若 vi 為剛得到 P 標(biāo)號(hào)的點(diǎn),考慮這樣的點(diǎn) vj :

57、 (vi ,vj)∈E 且vj 為 T 標(biāo)號(hào)。,Step 2:,對(duì)vj的T 標(biāo)號(hào)進(jìn)行如下更改T(vj)=min[T(vj),P(vi)+wij],2,4,5,迭代 1,,考察vs ,,T(v2)=min[T(v2),P(vs)+ws2]= min[+∞,0+5]=5,T(v1)=min[T(v1),P(vs)+ws1]= min[+∞,0+2]=2,最短路問題,比較所有具有 T 標(biāo)號(hào)的點(diǎn)，把最小者改為P 標(biāo)號(hào)，,Step 3:,2,4

58、,5,即 P(vi)=min[T(vi)].,當(dāng)存在兩個(gè)以上最小者時(shí),可同時(shí)改為P 標(biāo)號(hào)。若全部點(diǎn)為P標(biāo)號(hào),則停止。否則用vi代替vi轉(zhuǎn)step 2.,-,2,,迭代 1,全部T標(biāo)號(hào)中,T(v1)最小,令P(v1)=2,記錄路徑(vs ,v1).,最短路問題,9,4,若 vi 為剛得到 P 標(biāo)號(hào)的點(diǎn),考慮這樣的點(diǎn) vj : (vi ,vj)∈E 且vj 為 T 標(biāo)號(hào)。,Step 2:,對(duì)vj的T 標(biāo)號(hào)進(jìn)行

59、如下更改T(vj)=min[T(vj),P(vi)+wij],,,迭代 2,,考察v1 ,,T(v4)=min[T(v4),P(v1)+w14]= min[+∞,2+7]=9,T(v2)=min[T(v2),P(v1)+w12]= min[5,2+2]=4,最短路問題,4,4,,迭代 2,比較所有具有 T 標(biāo)號(hào)的點(diǎn)，把最小者改為P 標(biāo)號(hào)，,Step 3:,即 P(vi) =min[T(vi)].,-,-,,,全部 T 標(biāo)號(hào)中,T(v

60、2),T(v3)最小,令P(v2)=4, P(v3)=4,記錄路徑(v1 ,v2), (v1 ,v4),.,最短路問題,,7,,,迭代 3,若 vi 為剛得到 P 標(biāo)號(hào)的點(diǎn),考慮這樣的點(diǎn) vj : (vi ,vj)∈E 且vj 為 T 標(biāo)號(hào)。,Step 2:,對(duì)vj的T 標(biāo)號(hào)進(jìn)行如下更改T(vj)=min[T(vj),P(vi)+wij],,,,最短路問題,,7,,迭代 3,,比較所有具有 T 標(biāo)號(hào)的

61、點(diǎn)，把最小者改為P 標(biāo)號(hào)，,Step 3:,即 P(vi)=min[T(vi)].,-,,最短路問題,,,,迭代 4,,,若 vi 為剛得到 P 標(biāo)號(hào)的點(diǎn),考慮這樣的點(diǎn) vj : (vi ,vj)∈E 且vj 為 T 標(biāo)號(hào)。,Step 2:,對(duì)vj的T 標(biāo)號(hào)進(jìn)行如下更改T(vj)=min[T(vj),P(vi)+wij],8,14,,最短路問題,,,迭代 4,,,8,-,比較所有具有 T 標(biāo)號(hào)的點(diǎn)，把最

62、小者改為P 標(biāo)號(hào)，,Step 3:,即 P(vi)=min[T(vi)].,,最短路問題,,,,迭代 5,,,13,,若 vi 為剛得到 P 標(biāo)號(hào)的點(diǎn),考慮這樣的點(diǎn) vj : (vi ,vj)∈E 且vj 為 T 標(biāo)號(hào)。,Step 2:,對(duì)vj的T 標(biāo)號(hào)進(jìn)行如下更改T(vj)=min[T(vj),P(vi)+wij],,最短路問題,,,迭代 5,,,13,,比較所有具有 T 標(biāo)號(hào)的點(diǎn)，把最小者改為P 標(biāo)

63、號(hào)，,Step 3:,即 P(vi)=min[T(vi)].,當(dāng)存在兩個(gè)以上最小者時(shí),可同時(shí)改為P 標(biāo)號(hào)。若全部點(diǎn)為P標(biāo)號(hào),則停止。否則用vi代替vi轉(zhuǎn)step 2.,-,,最短路問題,,,最短路,,,,,Dijkstra算法不僅找到了所求最短路，而且找到了從 vs 點(diǎn)到其他所有頂點(diǎn)的最短路；這些最短路構(gòu)成了圖的一個(gè)連通無(wú)圈的支撐子圖，即圖的一個(gè)支撐樹。,最短路問題,從上例知，只要某點(diǎn)已標(biāo)號(hào)，說(shuō)明已找到起點(diǎn)vs到該點(diǎn)的最短路線及最

64、短距離，因此可以將每個(gè)點(diǎn)標(biāo)號(hào)，求出vs到任意點(diǎn)的最短路線，如果某個(gè)點(diǎn)vj不能標(biāo)號(hào)，說(shuō)明vs不可達(dá)vj 。,最短路問題,算法適用條件：Dijkstra算法只適用于全部權(quán)為非負(fù)情況，如果某邊上權(quán)為負(fù)的，算法失效。此時(shí)可采用逐次逼近算法。,如右圖所示中按dijkstra算法可得P(v1)=5為從vs→v1的最短路長(zhǎng)顯然是錯(cuò)誤的，從vs→v2→v1路長(zhǎng)只有3。,v2,vs,v1,5,-5,8,最短路問題,例2,Ford算法基本思想：為

65、逐次逼近的方法。每次求出從出發(fā)點(diǎn)v0到其余點(diǎn)的有限制的最短路，逐次放寬條件。即第一次逼近是找v0到vn的最短路，但限于最短路只允許有一條邊（弧），其距離記為d1(v0 ,vn).簡(jiǎn)記為d 1(vn)。第二次逼近，再找v0到vn的最短路，其限制條件放寬到允許最短路不超過(guò)兩條邊（?。渚嚯x記為d 2(vn)。到第m次逼近,d m(vn)表示由v0到vn的不超過(guò)m條邊（?。┙M成的最短路的距離。最多p-1次。,網(wǎng)絡(luò)有負(fù)權(quán)的最短路,最短路

66、問題,Ford算法基本步驟：,(1) 令m=1,令d1(v0)=0, d1(vi)=w(v0 ,vi).,解：① d1(v0)=0, d1(v1)=2, d1(v2)=1, d1(v3)=-2.,0,2,1,-2,第一次逼近,,,,最短路問題,,,,,,(2) 令,解：② d2(v1)=min{ d1(v1)+w(v1,v1), d1(v2)+w(v2,v1), d1(v3)+w(v3,v1) },0,2,1,-2,當(dāng)vi , v 為

67、同一個(gè)點(diǎn)時(shí)，有w(v ,vi)=0.,=min{ 2+0,1+∞, -2+3 } =1.,1,d2(v2)=min{ d1(v1)+w(v1,v2), d1(v2)+w(v2,v2), d1(v3)+w(v3,v2) },=min{ 2-2,1+0, -2+∞ } =0.,0,d2(v3)=min{ d1(v1)+w(v1,v3), d1(v2)+w(v2,v3),

68、 d1(v3)+w(v3,v3) },=min{ 2+∞,1+1, -2+0} =-2.,第二次逼近,(3)若m+1=p 則停止。否則m=m+1,轉(zhuǎn)(2).,,,最短路問題,解：③ d3(v1)=min{ d2(v1)+w(v1,v1), d2(v2)+w(v2,v1), d2(v3)+w(v3,v1) },0,1,0,-2,=min{ 1+0,0+∞, -2+3 } =1.,d3(v2)=min{ d2(v1)+w(v1,v2)