第4篇-圖論之基本概念

1、第4篇 圖論 主講人：任長安 計(jì)算機(jī)與信息科學(xué)系 2009.07,引言,圖論是在民間游戲當(dāng)中孕育和誕生的，作為數(shù)學(xué)的一個分支已有兩百多年的歷史。圖論的起源可以追溯到1736年由瑞士數(shù)學(xué)家歐拉(Leonhard Euler，1707-1783)撰寫的一篇解決“哥尼斯堡七橋問題”的論文。哥尼斯堡是東普魯士的一座城，流經(jīng)該城的Pregel河將城市分為彼此之間由七座橋相連接的四個部分，如圖1（a）所示。當(dāng)時，一些好奇的市民嘗試這樣一個有趣的游戲：從一個地方出發(fā)，通過每座橋一次且僅一次，最后回到出發(fā)地，這樣的路線是否存在？,引言,歐拉在論文中給出了解決這個問題的很容易理解的簡單證明，他將這個問題轉(zhuǎn)化為圖

2、1（b）所示的問題，將被河流分割的城市四個部分用點(diǎn)從A、B、C、D來表示，而將七座橋用稱為邊的線段來表示，于是問題轉(zhuǎn)化為：任何一點(diǎn)出發(fā)，是否存在通過每條邊一次且僅一次又回到出發(fā)點(diǎn)的路？歐拉的結(jié)論是不存在這樣的路。顯然，問題的結(jié)果并不重要，最為重要的是歐拉解決這個問題的中間步驟，即抽象為圖的形式來分析這個問題，當(dāng)時來說，這是一種全新的思考方式，由此歐拉在他的論文中提出了一個新的數(shù)學(xué)分支，即圖論，因此，歐拉也常常被圖論學(xué)家稱為“圖論之父”。,引言,圖1 哥尼斯堡七橋問題,引言,在歐拉之后，圖論得到了迅速的發(fā)展。一些圖論中的著名問題如四色問題(1852年)和哈密爾頓環(huán)游世界問題(1856年)也大量出

3、現(xiàn)。同時出現(xiàn)了以圖為工具去解決其它領(lǐng)域中一些問題的成果。1847年德國的克?；舴?G.R.Kirchoff)將樹的概念和理論應(yīng)用于工程技術(shù)的電網(wǎng)絡(luò)方程組的研究。1857年英國的凱萊(A.Cayley)也獨(dú)立地提出了樹的概念，并應(yīng)用于有機(jī)化合物的分子結(jié)構(gòu)的研究中。1936年匈牙利的數(shù)學(xué)家哥尼格(D.Konig) 發(fā)表了第一部集圖論二百年研究成果于一書的圖論專著有限圖與無限圖理論，這是現(xiàn)代圖論發(fā)展的里程碑，標(biāo)志著圖論已經(jīng)作為一門獨(dú)立的學(xué)科。,引言,現(xiàn)代電子計(jì)算機(jī)的出現(xiàn)與廣泛應(yīng)用極大地促進(jìn)了圖論的發(fā)展和應(yīng)用。在計(jì)算機(jī)科學(xué)中計(jì)算機(jī)科學(xué)的核心之一就是算法的設(shè)計(jì)與理論分析，而算法是以圖論與組合數(shù)學(xué)為基礎(chǔ)；

4、圖論與組合數(shù)學(xué)關(guān)系也非常密切，已正式成為計(jì)算機(jī)諸多分支中一種有力的基礎(chǔ)工具。因而，作為計(jì)算機(jī)專業(yè)人員，了解和掌握圖論的基本原理和方法是必要的?，F(xiàn)在，它已成為系統(tǒng)科學(xué)、管理科學(xué)、運(yùn)籌學(xué)、化學(xué)、經(jīng)濟(jì)學(xué)、網(wǎng)絡(luò)理論、信息論、控制論等學(xué)科和理論研究中的重要數(shù)學(xué)工具，受到數(shù)學(xué)界和工程技術(shù)界越來越多廣泛的重視。,主要內(nèi)容,1 圖的基本概念及表示 2 圖的應(yīng)用 3 樹,第8章 圖的基本概念及表示,圖是人們?nèi)粘Ｉ钪谐Ｒ姷囊环N信息載體，其突出的特點(diǎn)是直觀、形象。我們所討論的圖（graph）與人們通常所熟悉的圖，例如圓、橢圓、函數(shù)圖標(biāo)等是不相同的。圖論中所謂的圖是指某類具體離散事物集合和該集合中的每對事物間以某種

5、方式相聯(lián)系的數(shù)學(xué)模型。如果我們用點(diǎn)表示具體事物，用連線表示一對具體事物之間的聯(lián)系，那么，一個圖就是由一個表示具體事物的點(diǎn)的集合和表示事物之間聯(lián)系的一些線的集合所構(gòu)成，至于點(diǎn)的位置和連線的長短曲直是無關(guān)緊要的。 本章主要介紹圖論的基本概念、圖的運(yùn)算、連通性以及圖的矩陣表示。,第8章 圖的基本概念及表示,主要內(nèi)容： 8.1 圖的基本概念 8.2 圖的運(yùn)算 8.3 路徑與圖的連通性 8.4 圖的矩陣表示,8.1 圖的基本概念,例8.1 時間安排問題。某大學(xué)計(jì)算機(jī)學(xué)院的某教研組共有10名教師，他們分別參加7個班級的討論課，每個班級可能同時需要多位教師參加，有的教師可能需要參加多個班級的討論，每個班級必

6、須單獨(dú)開展討論課。參加各個班級討論課的教師情況如下（數(shù)字為教師編號）： c1=1，2，3，c2=1，3，4，5，c3=2，5，6，7，c4=2，6，7，c5=4，7，8，9，c6=8，9，10，c7=1，3，9，10。 這樣，一位教師如果給多個班級都授課，則在討論課時間安排方面則不能沖突，如教師1不能同時參加班級c1與班級c2的討論課。這種情況可以用圖8.1直觀地表示。,8.1 圖的基本概念,圖8.1 討論課時間安排圖,在圖8.1中，共用了7個小圓圈來表示班級，圓圈之間的線段表示存在同一個教師參加該二班級的討論課，這樣就不能安排該二班級同時開展討論課。顯然，這就給上述問題構(gòu)建了一個直觀的圖的模

7、型。,8.1 圖的基本概念,如從圖中容易看到：c1代表的班級不能與c2、c7代表的班級同時開展討論課，因此，至少需要安排三個時段，而c1與c5，c6間沒有邊存在，因此c5、c6均可以與c1在同一時段開展討論，但c5、c6之間有邊存在，故只能c5、c6之一與c1可以在同一時段開展討論課，等等，依此類推，可以得到各班級開展討論課時段的安排，但顯然，這是比較繁瑣的工作，因此，需要一些圖的術(shù)語來描述這個問題，而且如果能根據(jù)圖的一些相關(guān)性質(zhì)來設(shè)計(jì)一個好的算法才是最佳的選擇。,8.1 圖的基本概念,一、圖的定義 定義8.1 由集合V和E組成的數(shù)學(xué)結(jié)構(gòu)G=叫圖。其中V=v1，v2，vn為結(jié)點(diǎn)的集合；E的元素

8、為 (vi,vj )，稱為有向邊(無向邊)。并稱vi與vj相關(guān)聯(lián)(相鄰)，若E，則稱vi為始點(diǎn)，vj為終點(diǎn)。 由無向邊構(gòu)成的圖稱為無向圖，由有向邊構(gòu)成的圖稱為有向圖。,8.1 圖的基本概念,定義8.2 如果兩個結(jié)點(diǎn)之間有多條邊（對于有向圖，則有多條同方向的邊），則稱這些邊為平行邊，兩相鄰結(jié)點(diǎn)a，b間平行邊的條數(shù)稱為邊的重?cái)?shù)。含有平行邊或環(huán)的圖稱為多重圖，不含平行邊和環(huán)的圖稱為簡單圖。,8.1 圖的基本概念,二、結(jié)點(diǎn)的度數(shù) 定義8.3 設(shè)圖G是有向圖，v是圖G中的結(jié)點(diǎn)，以v為始點(diǎn)的有向邊的條數(shù)稱為v的出度，記個deg(v)；以v為終點(diǎn)的有向邊的條數(shù)稱為v的入度，記作deg(v)；結(jié)點(diǎn)v的度為出度

9、和入度之和，記為deg(v) 。 例如，計(jì)算圖8.3中結(jié)點(diǎn)v的度數(shù)。 解： v的入度deg(v)=2， v的出度deg(v)=3， v的度deg(v)=5,圖 8.3,8.1 圖的基本概念,定義8.4 設(shè)圖G是無向圖，v是圖G中的結(jié)點(diǎn)，所有與v關(guān)聯(lián)的邊的條數(shù)，稱為點(diǎn)v的度數(shù)，記作deg(v)。 例如，計(jì)算圖8.4中結(jié)點(diǎn)v的度數(shù)。 解：v的度deg(v)=4,圖 8.4,8.1 圖的基本概念,定理8.1 在任何有向圖中，所有結(jié)點(diǎn)的入度之和等于所有結(jié)點(diǎn)出度之和。 證明：因?yàn)橐粭l邊產(chǎn)生一個入度和出度。 所以所有結(jié)點(diǎn)的入度之和等于出度之和(等于邊數(shù))。 定理8.2 在任何圖中，所有結(jié)點(diǎn)的度數(shù)之和一定等

10、于邊數(shù)的2倍。 證明：因?yàn)槿魏我粭l邊都產(chǎn)生2個度，所以有 。,8.1 圖的基本概念,定理8.3 在任何圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)個數(shù)必為偶數(shù)。 證明：設(shè)V1和V2分別是G中偶數(shù)度數(shù)和奇數(shù)度數(shù)的結(jié)點(diǎn)集。 由于 是偶數(shù)之和，必為偶數(shù)。 而2|E|是偶數(shù)，故得 是偶數(shù)，即|V2|是偶數(shù)。,8.1 圖的基本概念,三、完全圖 定義8.5 對于簡單無向圖G，若G的任意兩個結(jié)點(diǎn)之間都有邊相連，稱G為完全圖，記為Kn，n為結(jié)點(diǎn)數(shù)。 例如，k3，k4，k5如圖8.5所示， Kn的邊數(shù)為：,圖8.5,8.1 圖的基本概念,定義8.6 對于有向圖G，若看成無向圖是完全圖，則稱為有向完全圖。 例如，圖8.6顯示的就是一個

11、有向完全圖。 例8.1 求解下列各題： 1) 無向完全圖Kn有28條邊， 則它的頂點(diǎn)數(shù)n為多少？ 2) 圖G的度數(shù)列為2，2，3，5，6，則邊數(shù)m為多少? 3) 圖G有12條邊，度數(shù)為3的頂點(diǎn)有6個，余者度數(shù)均小于 3，問G至少由幾個頂點(diǎn)？,圖 8.6,8.1 圖的基本概念,1）因?yàn)闊o向完全圖Kn的邊數(shù) ，故n=8。 2) 2m=deg(v)=2+2+3+5+6=18，可得m=9。 3)由deg(v)=2m=24，度數(shù)為3的頂點(diǎn)有6個占去18度，還有6度由其余頂點(diǎn)占有，而由題意，其余頂點(diǎn)的度數(shù)可為0，1，2，當(dāng)均為2時所用頂點(diǎn)數(shù)最少，所以應(yīng)有3個頂點(diǎn)占有此6度，即G中至少有9個頂點(diǎn)。,8.1

12、圖的基本概念,例8.2證明在n（n2）個人的團(tuán)體中，總有兩個人在此團(tuán)體中恰好有相同個數(shù)的朋友。 分析：以結(jié)點(diǎn)代表人，二人若是朋友，則在結(jié)點(diǎn)間連上一條邊，這樣可得無向簡單圖G，每個人的朋友數(shù)即該結(jié)點(diǎn)的度數(shù)，于是問題轉(zhuǎn)化為：n階無向簡單圖G中必有兩個頂點(diǎn)的度數(shù)相同。 證明：用反證法。 設(shè)G中各頂點(diǎn)的度數(shù)均不相同，則度數(shù)列為0，1，2，n-1，說明圖中有孤立頂點(diǎn)，與有n-1度頂點(diǎn)相矛盾（因?yàn)槭呛唵螆D），所以必有兩個頂點(diǎn)的度數(shù)相同。,8.1 圖的基本概念,四、圖的同構(gòu) 定義8.7 設(shè)圖G= 和G=，若存在雙射f：VV且f(V)= V，(vi，vj)E當(dāng)且僅當(dāng)(f(vi)，f(vj) E(E當(dāng)且僅當(dāng)E)

13、， 則稱圖G和G同構(gòu)，記作GG。 例，下面列出了一些同構(gòu)圖，如圖8.7所示，,8.1 圖的基本概念,構(gòu)造映射g(vi)=vi(i=1，2，5，6)，可使(vi，vj)和(g(vi)，g(vj)一一對應(yīng)，即兩圖同構(gòu)。兩圖同構(gòu)的必要條件：,圖 8.7,8.1 圖的基本概念,1) 結(jié)點(diǎn)數(shù)相等; 2) 邊數(shù)相等; 3) 度數(shù)相同的結(jié)點(diǎn)數(shù)相等。 但不是充分條件。 如圖8.8所示， 上圖所示兩圖雖然滿足結(jié)點(diǎn)數(shù)相等、邊數(shù)相等和度數(shù)相同的結(jié)點(diǎn)數(shù)相等這三個條件，但并不同構(gòu)。,8.2 圖的運(yùn)算,由于圖由結(jié)點(diǎn)集、邊集組成，也是一種關(guān)系的標(biāo)識，因此對圖可作種種與集合運(yùn)算相類似的運(yùn)算。通過對圖的運(yùn)算，可以得到一些具有實(shí)

14、際應(yīng)用意義的新圖，如許多網(wǎng)絡(luò)拓樸結(jié)構(gòu)是通過圖的運(yùn)算得到的。 一、圖的基本運(yùn)算 (1) 刪除運(yùn)算 從圖G中刪除一邊e所得到的子圖，記為G-e。從圖G中刪除一個結(jié)點(diǎn)v及其關(guān)聯(lián)的邊所得到的子圖，記為G-v。類似地，G-E表示從G中刪除邊集E的子集E所得到的子圖，記為G-E=(V，E-E)。G-V表示從G中刪除結(jié)點(diǎn),8.2 圖的運(yùn)算,集V的子集V以及與它們關(guān)聯(lián)的邊所得的子圖。 (2)邊收縮運(yùn)算 設(shè)圖G中邊e=(vi，vj)，刪去邊e，并把vi與vj合并成一個新點(diǎn)vi-j，使原來與vi或vj關(guān)聯(lián)的邊變?yōu)榕c點(diǎn)vi-j關(guān)聯(lián)的邊，稱邊e被收縮，得到的新圖稱為G關(guān)于邊e的收縮圖，記為G/e或G/vivj。如圖8

15、.9，圖（b）是對圖(a)的邊（d，e）收縮后得到的圖。,8.2 圖的運(yùn)算,(3) 并與和運(yùn)算 設(shè)G1=(V1，E1)，G2=(V2，E2)是兩個給定的圖，則定義： G1與G2的并為G1G2=(V1V2，E1E2)； G1與G2的和G1+G2是在G1與G2的并的基礎(chǔ)上需增加G1的每個結(jié)點(diǎn)與G2的每個結(jié)點(diǎn)連接得到的共計(jì)mn條邊，m，n分別為G1，G2的階。如圖8.10所示，圖(a)為K2K3，圖(b)為K2+K3。,8.2 圖的運(yùn)算,圖 8.10,8.2 圖的運(yùn)算,二、補(bǔ)運(yùn)算 定義8.8 設(shè)G=為任意的n階無向簡單圖，則由G的所有結(jié)點(diǎn)及使G成為完全圖的添加邊所組成的圖，稱為G的補(bǔ)圖。記為 。 例

16、如，圖G和其補(bǔ)圖 如圖8.11所示，,圖8.11,8.2 圖的運(yùn)算,三、子圖 定義8.9 給定圖G1=和G2=，如果滿足： 1)若V1V2 ，E1E2 ，E1中的邊所關(guān)聯(lián)的頂點(diǎn)均在V1中，則稱G1為G2的子圖。 2)若V1=V2 ，E1E2 ，E1中的邊所關(guān)聯(lián)的頂點(diǎn)均在V1中，則稱G1為G2的生成子圖或支撐子圖。,8.2 圖的運(yùn)算,例，如圖8.12所示， 從圖中可看出，上圖中G1和G2都是G的子圖，但只有G2是G的生成子圖。,圖8.12,8.3 路徑與圖的連通性,右圖是中國鐵路交通圖的一部分，如果一個旅客要從成都乘火車到北京，那么他一定會經(jīng)過其它車站；而旅客不可能從成都乘火車到達(dá)臺北。這就引出

17、了圖的通路與連通的概念。,8.3 路徑與圖的連通性,一、 通路和回路 給定圖G=中結(jié)點(diǎn)和邊相繼交錯出現(xiàn)的序列=v0e1v1e2v2ekvk。 若中邊ei的兩端點(diǎn)是vi-1和vi（G是有向圖時要求vi-1與vi分別是ei的始點(diǎn)和終點(diǎn)），i=1,2,k，則稱為結(jié)點(diǎn)v0到結(jié)點(diǎn)vk的通路(Entry)。v0和vk分別稱為此通路的始點(diǎn)和終點(diǎn)，統(tǒng)稱為通路的端點(diǎn)。通路中邊的數(shù)目k稱為此通路的長度(Length)。當(dāng)v0=vn時，此通路稱為回路(Circuit)。,8.3 路徑與圖的連通性,若通路中的所有邊互不相同，則稱此通路為簡單通路(Simple Entry)或一條跡；若回路中的所有邊互不相同，則稱此回路

18、為簡單回路(Simple Circuit)或一條閉跡。 若通路中的所有結(jié)點(diǎn)互不相同（從而所有邊互不相同），則稱此通路為基本通路(Basic Entry)或者初級通路、路徑；若回路中除v0=vk外的所有結(jié)點(diǎn)互不相同（從而所有邊互不相同），則稱此回路為基本回路(Basic Circuit)或者初級回路、圈。,8.3 路徑與圖的連通性,說明： 回路是通路的特殊情況。因而，我們說某條通路，它可能是回路。但當(dāng)我們說一初級通路時，一般是指它不是初級回路的情況。 初級通路（回路）一定是簡單通路（回路），但反之不真。因?yàn)闆]有重復(fù)的結(jié)點(diǎn)肯定沒有重復(fù)的邊，但沒有重復(fù)的邊不能保證一定沒有重復(fù)的結(jié)點(diǎn)。 在不會引起誤解

19、的情況下，一條通路v0e1v1e2v2envn也可以用邊的序列e1e2en來表示，這種表示方法對于有向圖來說較為方便。在簡單圖中，一條通路v0e1v1e2v2envn也可以用結(jié)點(diǎn)的序列v0v1v2vn來表示。,8.3 路徑與圖的連通性,例 8.3.1 判斷下圖G1中的回路v3e5v4e7v1e4v3e3v2e1v1e4v3、v3e3v2e2v2e1v1e4v3、v3e3v2e1v1e4v3是否是簡單回路、初級回路？圖G2 中的通路v1e1v2e6v5e7v3e2v2e6v5e8v4、v1e5v5e7v3e2v2e6v5e8v4、v1e1v2e6v5e7v3e3v4是否是簡單通路、初級通路？并求

20、其長度。,8.3 路徑與圖的連通性,判斷一條通（回）路是否是簡單通（回）路、初級通（回）路，主要是看它有無重復(fù)的邊、結(jié)點(diǎn)。 在圖G1中，v3e5v4e7v1e4v3e3v2e1v1e4v3中有重復(fù)的邊e4，因此它不是簡單回路，也不是初級回路； v3e3v2e2v2e1v1e4v3雖然沒有重復(fù)的邊，但有重復(fù)的結(jié)點(diǎn)v2，因此只能是簡單回路，而不是初級回路； 而v3e3v2e1v1e4v3中既沒有重復(fù)的邊，也沒有重復(fù)的結(jié)點(diǎn)，因此既是初級回路，也是簡單回路；,8.3 路徑與圖的連通性,在圖G2 中，v1e1v2e6v5e7v3e2v2e6v5e8v4中有重復(fù)的邊e6，因此它既不是簡單通路，也不是初級通

21、路； v1e5v5e7v3e2v2e6v5e8v4雖然沒有重復(fù)的邊，但有重復(fù)的結(jié)點(diǎn)v5，因此只能簡單通路，但不是初級通路； v1e1v2e6v5e7v3e3v4中既沒有重復(fù)的邊，也沒有重復(fù)的結(jié)點(diǎn)，因此既是初級通路，也是簡單通路。 至于通（回）路的長度就是其包含的邊的數(shù)目，這只需要數(shù)一數(shù)就行了。,8.3 路徑與圖的連通性,在圖G1中，v3e5v4e7v1e4v3e3v2e1v1e4v3是一條長度為6的回路，但既不是簡單回路，也不是初級回路； v3e3v2e2v2e1v1e4v3是一條長度為4的簡單回路，但不是初級回路； v3e3v2e1v1e4v3是一條長度為3的初級回路，也是簡單回路；,8.3

22、 路徑與圖的連通性,在圖G2中，v1e1v2e6v5e7v3e2v2e6v5e8v4是一條長度為6的通路，但既不是簡單通路，也不是初級通路； v1e5v5e7v3e2v2e6v5e8v4是一條長度為5的簡單通路，但不是初級通路； v1e1v2e6v5e7v3e3v4是一條長度為4的初級通路，也是簡單通路。,8.3 路徑與圖的連通性,定理8.3.1 在一個具有n個結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj（vivj）存在一條通路，則從vi到vj存在一條長度不大于n-1的通路。 分析 通路的長度為序列中的結(jié)點(diǎn)數(shù)減1，如果結(jié)點(diǎn)不重復(fù)，最多n個，因此通路長度最多n-1；如果結(jié)點(diǎn)有重復(fù)，則在重復(fù)的結(jié)點(diǎn)間構(gòu)成一

23、條回路，刪除這條回路，剩下的仍然是從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj的通路。一直刪下去，直到無重復(fù)結(jié)點(diǎn)為止，這樣定理就得證了。,8.3 路徑與圖的連通性,推論8.3.1 在一個具有n個結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj（vivj）存在一條通路，則從vi到vj存在一條長度不大于n-1的初級通路。 定理8.3.2 在一個具有n個結(jié)點(diǎn)的圖中，如果存在經(jīng)過結(jié)點(diǎn)vi的回路，則存在一條經(jīng)過vi的長度不大于n的回路。 推論8.3.2 在一個具有n個結(jié)點(diǎn)的圖中，如果存在經(jīng)過結(jié)點(diǎn)vi的回路，則存在一條經(jīng)過vi的長度不大于n的初級回路。 通路、回路是討論圖的連通性的基礎(chǔ)，下面分別討論無向圖和有向圖的連通性問題。,8.3 路徑

24、與圖的連通性,二、 無向圖的連通性 無向圖中，如果圖中兩個點(diǎn)之間存在通路，則稱v0和vn是連通的。并規(guī)定一個點(diǎn)與其本身是連通的。 圖中兩點(diǎn)間的連通關(guān)系是等價(jià)關(guān)系。因此頂點(diǎn)集上的等價(jià)連通關(guān)系必然對應(yīng)一個頂點(diǎn)集的一個劃分，一個劃分塊中的任何點(diǎn)之間都是連通的，而不同的劃分塊之間是不連通的。如果劃分塊只有一個，則稱無向圖是連通的。 1、圖的連通性定義 如果G=中任何結(jié)點(diǎn)都是連通的，則稱圖是連通的；否則，稱為G為不連通的。,8.3 路徑與圖的連通性,連通分支：圖G中的任何一個劃分塊，記為：W(G) 2、點(diǎn)割集和邊割集 （1）點(diǎn)割集和割點(diǎn) 設(shè)無向圖G=為連通圖，若有點(diǎn)集V V，使圖G刪除了V的所有結(jié)點(diǎn)后（

25、將V中結(jié)點(diǎn)與其關(guān)聯(lián)的邊都刪除）得到的子圖是不連通的，而刪除了V的任何一個真子集后得到的子圖仍是連通圖，則稱V為G的一個點(diǎn)割集； 如果點(diǎn)割集中只有一個元素，此點(diǎn)稱為割點(diǎn)。 示例：如圖8.15所示，舉例說明圖中的點(diǎn)割集及割點(diǎn)。,8.3 路徑與圖的連通性,圖 8.15,8.3 路徑與圖的連通性,（2）邊割集和橋 設(shè)無向圖G=為連通圖，如果有邊集E E，在圖G中刪除了E 后，得到的子圖是不連通的，而刪除了E的任何一個真子集后得到的子圖仍是連通圖，則稱E為G的一個邊割集； 如果邊割集中只有一個元素，此邊稱為割邊或橋。 示例： 同樣如圖8.15所示，舉例說明圖中的邊割集和橋。,8.3 路徑與圖的連通性,三

26、、有向圖的連通性 無向圖的連通性不能直接推廣到有向圖。 在有向圖中，如果存在從一個點(diǎn)u到另一個點(diǎn)v的路徑，則稱 從u到v可達(dá)。并規(guī)定任何頂點(diǎn)到自身是可達(dá)的。 注：頂點(diǎn)間的可達(dá)關(guān)系是有向圖中基本的頂點(diǎn)間的關(guān)系，是自反的、可傳遞的，但不一定是對稱的，所以不是等價(jià)關(guān)系。 根據(jù)頂點(diǎn)間的可達(dá)關(guān)系，可定義有向圖的連通性。,8.3 路徑與圖的連通性,1、弱連通：在簡單有向圖D中，略去邊的方向得到的無向圖G，如果G是連通的，則有向圖D是弱連通的； 2、單向連通：若D中任何兩個頂點(diǎn)間，至少有一個頂點(diǎn)可達(dá)另一個頂點(diǎn)，則稱D是單向連通的； 3、強(qiáng)連通：若D中任何兩個頂點(diǎn)間都可以相互可達(dá)，則稱D是強(qiáng)連通的； 示例：如

27、下圖8.16所示。,8.3 路徑與圖的連通性,圖 8.16,由上圖可知，a為強(qiáng)連通的，b為單向連通的，c為弱連通的。,8.3 路徑與圖的連通性,思考題 例8.3.2 試尋找3個4階有向簡單圖D1，D2，D3，使得D1為強(qiáng)連通圖；D2為單向連通圖，但不是強(qiáng)連通的；D3為弱連通的，但不是單向連通或強(qiáng)連通。,8.3 路徑與圖的連通性,四、路徑與圖的應(yīng)用問題 1、渡河問題 例8.3.3 一個擺渡人要把一只狼、一只羊和一捆菜運(yùn)過河去。由于船很小，每次擺渡人至多只能帶一樣?xùn)|西。另外，如果人不在旁時，狼就要吃羊，羊就要吃菜。問這人怎樣才能將它們運(yùn)過河去？ 解 用F表示擺渡人，W表示狼，S表示羊，C表示菜。

28、若用FWSC表示人和其它三樣?xùn)|西在河的原岸的狀態(tài)，這樣原岸全部可能出現(xiàn)的狀態(tài)為以下16種：,8.3 路徑與圖的連通性,FWSC FWS FWC FSC WSC FW FS FC WS WC SC F W S C 這里表示原岸什么也沒有，即人、狼、羊、菜都已運(yùn)到對岸去了。 根據(jù)題意我們知道，這16種情況中有6種是不允許的，它們是：WSC、FW、FC、WS、SC、F。如FC表示人和菜在原岸，而狼和羊在對岸，這當(dāng)然是不行的。因此，允許出現(xiàn)的情況只有10種。,8.3 路徑與圖的連通性,以這10種狀態(tài)為結(jié)點(diǎn)，以擺渡前原岸的一種狀態(tài)與擺渡一次后仍在原岸的狀態(tài)所對應(yīng)的結(jié)點(diǎn)之間的聯(lián)線為邊做有向圖G，如圖,圖中給出了兩種方案，方案為圖中的從FWSC到的不同的基本通路，它們的長度均為7，按圖中所指的方案，擺渡人只要擺渡7次就能將它們?nèi)窟\(yùn)到對岸，并且羊和菜完