1、第第1010章章 圖論圖論(Graph Theory ) )第十章第十章 圖論圖論(Graph Theory) 10.1 圖的基本概念圖的基本概念(Graph) 10.2 路與圖的連通性路與圖的連通性(Walks & Connectivity of Graphs) 10.3 圖的矩陣表示圖的矩陣表示(Matrix Notation of Graph)10.4 最短鏈與關(guān)鍵路最短鏈與關(guān)鍵路（Minimal path ） 10.5 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖(Eulerian Graph & Hamilton-ian Graph ) 10.6 平面圖平面圖(Planar

2、Graph)10.7樹(shù)樹(shù)與生成樹(shù)與生成樹(shù)(Trees and Spanning Trees) 10.8 二部圖（二部圖（bipartite graph） 第第1010章章 圖論圖論(Graph Theory ) )10.1 圖的基本概念圖的基本概念 10.1.1 圖的基本概念圖的基本概念 10.1.2 圖的結(jié)點(diǎn)的度數(shù)及其計(jì)算圖的結(jié)點(diǎn)的度數(shù)及其計(jì)算 10.1.3 子圖和圖的同構(gòu)子圖和圖的同構(gòu)第第1010章章 圖論圖論(Graph Theory ) ) 圖圖 10.1.1哥尼斯堡七橋問(wèn)題 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) )10.1.1

3、圖圖 現(xiàn)實(shí)世界中許多現(xiàn)象能用某種圖形表示現(xiàn)實(shí)世界中許多現(xiàn)象能用某種圖形表示,這種圖形這種圖形是由一些點(diǎn)和一些連接兩點(diǎn)間的連線所組成。是由一些點(diǎn)和一些連接兩點(diǎn)間的連線所組成。 【例【例10.1.1】a， b， c， d 4個(gè)籃球隊(duì)進(jìn)行友誼比賽。個(gè)籃球隊(duì)進(jìn)行友誼比賽。 為為了表示個(gè)隊(duì)之間比賽的情況，了表示個(gè)隊(duì)之間比賽的情況， 我們作出圖我們作出圖10.1.1的圖形。的圖形。 在圖中個(gè)小圓圈分別表示這個(gè)籃球隊(duì)，在圖中個(gè)小圓圈分別表示這個(gè)籃球隊(duì)， 稱(chēng)之為結(jié)點(diǎn)。稱(chēng)之為結(jié)點(diǎn)。如果兩隊(duì)進(jìn)行過(guò)比賽，則在表示該隊(duì)的兩個(gè)結(jié)點(diǎn)之間用一如果兩隊(duì)進(jìn)行過(guò)比賽，則在表示該隊(duì)的兩個(gè)結(jié)點(diǎn)之間用一條線連接起來(lái)，稱(chēng)之為邊。這樣利用

4、一個(gè)圖形使各隊(duì)之間條線連接起來(lái)，稱(chēng)之為邊。這樣利用一個(gè)圖形使各隊(duì)之間的比賽情況一目了然。的比賽情況一目了然。1.圖的定義圖的定義 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) ) 圖圖 10.1.1如果圖如果圖 10.1.1中的個(gè)中的個(gè)結(jié)點(diǎn)結(jié)點(diǎn)a， b， c， d分別分別表示個(gè)人，當(dāng)某兩表示個(gè)人，當(dāng)某兩個(gè)人互相認(rèn)識(shí)時(shí)，個(gè)人互相認(rèn)識(shí)時(shí)， 則則將其對(duì)應(yīng)點(diǎn)之間用邊將其對(duì)應(yīng)點(diǎn)之間用邊連接起來(lái)。連接起來(lái)。 這時(shí)的圖這時(shí)的圖又反映了這個(gè)人之又反映了這個(gè)人之間的認(rèn)識(shí)關(guān)系。間的認(rèn)識(shí)關(guān)系。 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph

5、 Theory ) ) 定義定義10.1.1一個(gè)圖一個(gè)圖G是一個(gè)序偶是一個(gè)序偶V(G), E(G)， 記記為為GV(G), E(G)。 其中其中V(G)是非空結(jié)點(diǎn)集合，是非空結(jié)點(diǎn)集合， E(G)是邊集合，是邊集合， 對(duì)對(duì)E(G)中的每條邊，中的每條邊， 有有V(G)中的中的結(jié)點(diǎn)的有序偶或無(wú)序偶與之對(duì)應(yīng)。結(jié)點(diǎn)的有序偶或無(wú)序偶與之對(duì)應(yīng)。 若邊若邊e所對(duì)應(yīng)的結(jié)點(diǎn)對(duì)是有序偶所對(duì)應(yīng)的結(jié)點(diǎn)對(duì)是有序偶a,b,則稱(chēng)則稱(chēng)e是有向邊。是有向邊。a叫邊叫邊e的始點(diǎn)的始點(diǎn),b叫邊叫邊e的終點(diǎn)的終點(diǎn),統(tǒng)稱(chēng)為統(tǒng)稱(chēng)為e的的端點(diǎn)。若邊端點(diǎn)。若邊e所對(duì)應(yīng)的結(jié)點(diǎn)對(duì)是無(wú)序偶所對(duì)應(yīng)的結(jié)點(diǎn)對(duì)是無(wú)序偶(a,b) ,則稱(chēng)則稱(chēng)e是是無(wú)向邊。

6、這時(shí)統(tǒng)稱(chēng)無(wú)向邊。這時(shí)統(tǒng)稱(chēng)e與兩個(gè)結(jié)點(diǎn)與兩個(gè)結(jié)點(diǎn)a和和b互相關(guān)聯(lián)。互相關(guān)聯(lián)。 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) )【例【例10.1.2】 設(shè)設(shè)G=V(G),E(G),其中其中 V(G)=a,b,c,d,E(G)=e1,e2,e3,e4,e5,e6,e7,e1=(a,b), e2=(a,c),e3=(b,d),e4=(b,c),e5=(d,c),e6=(a,d),e7=(b,b)。則圖則圖G可用圖可用圖10.1.2(a)或或(b)表示。表示。我們將結(jié)點(diǎn)我們將結(jié)點(diǎn)a、b的無(wú)序結(jié)點(diǎn)對(duì)記為的無(wú)序結(jié)點(diǎn)對(duì)記為(a，b），）， 有序有序結(jié)點(diǎn)對(duì)記為結(jié)點(diǎn)

7、對(duì)記為a，b。 一個(gè)圖一個(gè)圖G可用一個(gè)圖形來(lái)表示且表示是不唯一的。可用一個(gè)圖形來(lái)表示且表示是不唯一的。 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) )圖圖 10.1.2 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) )圖 10.1.2 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) )2. 圖圖G的結(jié)點(diǎn)與邊之間的關(guān)系的結(jié)點(diǎn)與邊之間的關(guān)系鄰接點(diǎn)鄰接點(diǎn): 同一條邊的兩個(gè)端點(diǎn)。同一條邊的兩個(gè)端點(diǎn)。孤立點(diǎn)孤立點(diǎn): 沒(méi)有邊與之關(guān)聯(lián)的結(jié)點(diǎn)。沒(méi)有邊與之關(guān)聯(lián)的結(jié)點(diǎn)。鄰

8、接邊鄰接邊: 關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的兩條邊。關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的兩條邊。孤立邊孤立邊: 不與任何邊相鄰接的邊。不與任何邊相鄰接的邊。自回路（環(huán)）：關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的一條邊（自回路（環(huán)）：關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的一條邊（v，v）或）或v，v）。）。平行邊平行邊(多重邊多重邊):關(guān)聯(lián)同一對(duì)結(jié)點(diǎn)的多條邊。關(guān)聯(lián)同一對(duì)結(jié)點(diǎn)的多條邊。 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) ) 如例如例10.1.1中的圖，結(jié)點(diǎn)集中的圖，結(jié)點(diǎn)集Va，b，c，d， 邊集邊集 Ee1， e2， e3， e4， e5， 其中其中 e1（a，b），），e2（a, c），），e3（a，d），）， e

9、4（b, c），）， e5（c, d）。）。 d與與a、 d與與c是鄰接的，是鄰接的， 但但d與與b不不鄰接，鄰接， 邊邊e3與與e5是鄰接的。是鄰接的。 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) ) 【例【例10.1.3】設(shè)圖設(shè)圖GV ,E 如圖如圖10.1.3所示。所示。 這里這里Vv1，v2，v3， Ee1，e2，e3，e4，e5， 其中其中e1 =(v1, v2) ，e2=(v1，v3) ， e3 =(v3, v3), e4 =(v2, v3), e5=(v2，v3)。 在這個(gè)圖中，在這個(gè)圖中，e3是關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的一條邊是關(guān)聯(lián)同一個(gè)

10、結(jié)點(diǎn)的一條邊,即即自回路；邊自回路；邊e4和和e5都與結(jié)點(diǎn)都與結(jié)點(diǎn)v2、 v3關(guān)聯(lián)，即它們關(guān)聯(lián)，即它們是平行邊。是平行邊。 10.1 圖的基本概念圖的基本概念 圖圖 10 .1. 3第第1010章章 圖論圖論(Graph Theory ) ) 3. 圖圖G的分類(lèi)的分類(lèi)按按G的結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)分為的結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)分為(n,m)圖圖,即即n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), m條邊的圖條邊的圖; 特別地特別地, (n,0)稱(chēng)為稱(chēng)為零圖零圖, (1,0) 圖稱(chēng)為圖稱(chēng)為平凡圖平凡圖 。(2) 按按G中關(guān)聯(lián)于同一對(duì)結(jié)點(diǎn)的邊數(shù)分為中關(guān)聯(lián)于同一對(duì)結(jié)點(diǎn)的邊數(shù)分為多重圖和簡(jiǎn)多重圖和簡(jiǎn)單圖單圖; 多重圖多重圖:含有平行邊的圖（如圖含有

11、平行邊的圖（如圖 10 .1. 3） ； 線線 圖圖: 非多重圖稱(chēng)為線圖；非多重圖稱(chēng)為線圖； (1) 簡(jiǎn)單圖簡(jiǎn)單圖:不含平行邊和自環(huán)的圖。不含平行邊和自環(huán)的圖。 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) )G1、G2是多重圖是多重圖G3是線圖是線圖G4是簡(jiǎn)單圖是簡(jiǎn)單圖第第1010章章 圖論圖論(Graph Theory ) ) (3)按按G的邊有序、無(wú)序分為的邊有序、無(wú)序分為有向圖、無(wú)向圖和混合圖有向圖、無(wú)向圖和混合圖; 有向圖：有向圖：每條邊都是有向邊的圖稱(chēng)為有向圖每條邊都是有向邊的圖稱(chēng)為有向圖 （圖（圖 10 .1.4 (b)； 無(wú)向圖：

12、無(wú)向圖：每條邊都是無(wú)向邊的圖稱(chēng)為無(wú)向圖；每條邊都是無(wú)向邊的圖稱(chēng)為無(wú)向圖； 混合圖：混合圖：既有無(wú)向邊既有無(wú)向邊, 又有有向邊的圖稱(chēng)為混合圖。又有有向邊的圖稱(chēng)為混合圖。 (4)按按G的邊旁有無(wú)數(shù)量特征分為的邊旁有無(wú)數(shù)量特征分為加權(quán)圖、無(wú)權(quán)圖加權(quán)圖、無(wú)權(quán)圖(如圖如圖 10.1.4); 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) )圖圖 10 .1. 4(5)按按G的任意兩個(gè)結(jié)點(diǎn)間是否有邊分為的任意兩個(gè)結(jié)點(diǎn)間是否有邊分為完全圖完全圖Kn (如圖如圖 10.1.5)和和不完全圖不完全圖(如圖如圖 10.1.6)。 10.1 圖的基本概念圖的基本概念 第

13、第1010章章 圖論圖論(Graph Theory ) ) 完全圖完全圖：任意兩個(gè)不同的結(jié)點(diǎn)都鄰接的簡(jiǎn)單圖稱(chēng)為：任意兩個(gè)不同的結(jié)點(diǎn)都鄰接的簡(jiǎn)單圖稱(chēng)為完全圖。完全圖。n 個(gè)結(jié)點(diǎn)的無(wú)向完全圖記為個(gè)結(jié)點(diǎn)的無(wú)向完全圖記為Kn。 圖圖10.1.5給出了給出了K3和和K4。從圖中可以看出。從圖中可以看出K3有有條邊，條邊，K4有條邊。有條邊。 容易證明容易證明Kn有有 條邊。條邊。(1)2n n 10.1 圖的基本概念圖的基本概念 圖圖 10 .1. 6圖圖 10.1.5 K3與與K4示意圖示意圖第第1010章章 圖論圖論(Graph Theory ) )例例213213有向完全圖有向完全圖無(wú)向完全圖無(wú)向

14、完全圖第第1010章章 圖論圖論(Graph Theory ) )給定任意一個(gè)含有給定任意一個(gè)含有n個(gè)結(jié)點(diǎn)的圖個(gè)結(jié)點(diǎn)的圖G,總可以把它補(bǔ)成一個(gè)總可以把它補(bǔ)成一個(gè)具有同樣結(jié)點(diǎn)的完全圖具有同樣結(jié)點(diǎn)的完全圖,方法是把那些缺少的邊添上。方法是把那些缺少的邊添上。 定義定義10.1.2 設(shè)設(shè)GV, E是一個(gè)具有是一個(gè)具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖。以圖。以V為結(jié)點(diǎn)集，以從完全圖為結(jié)點(diǎn)集，以從完全圖Kn中刪去中刪去G的所有邊后的所有邊后得到的圖（或由得到的圖（或由G中所有結(jié)點(diǎn)和所有能使中所有結(jié)點(diǎn)和所有能使G成為完全圖成為完全圖的添加邊組成的圖）稱(chēng)為的添加邊組成的圖）稱(chēng)為G的的補(bǔ)圖補(bǔ)圖，記為，記為 。 例

15、如，零圖和完全圖互為補(bǔ)圖。例如，零圖和完全圖互為補(bǔ)圖。G 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) )G相對(duì)于相對(duì)于Kn的補(bǔ)圖是下圖中的的補(bǔ)圖是下圖中的G第第1010章章 圖論圖論(Graph Theory ) )第第1010章章 圖論圖論(Graph Theory ) )互為補(bǔ)圖互為補(bǔ)圖互為補(bǔ)圖互為補(bǔ)圖互為補(bǔ)圖互為補(bǔ)圖第第1010章章 圖論圖論(Graph Theory ) ) 【例【例10.1.4】（拉姆齊問(wèn)題）試證在任何一個(gè)有個(gè)（拉姆齊問(wèn)題）試證在任何一個(gè)有個(gè)人的組里，人的組里， 存在個(gè)人互相認(rèn)識(shí)，存在個(gè)人互相認(rèn)識(shí)， 或者存在個(gè)人互或者

16、存在個(gè)人互相不認(rèn)識(shí)。相不認(rèn)識(shí)。 我們用個(gè)結(jié)點(diǎn)來(lái)代表人，我們用個(gè)結(jié)點(diǎn)來(lái)代表人， 并用鄰接性來(lái)代表認(rèn)并用鄰接性來(lái)代表認(rèn)識(shí)關(guān)系。識(shí)關(guān)系。 這樣一來(lái)，這樣一來(lái)， 該例就是要證明：該例就是要證明： 任意一個(gè)有任意一個(gè)有個(gè)結(jié)點(diǎn)的圖個(gè)結(jié)點(diǎn)的圖G中，中， 或者有個(gè)互相鄰接的點(diǎn)，或者有個(gè)互相鄰接的點(diǎn)， 或者或者有個(gè)互相不鄰接的點(diǎn)。有個(gè)互相不鄰接的點(diǎn)。 即，即， 對(duì)任何一個(gè)有個(gè)結(jié)點(diǎn)對(duì)任何一個(gè)有個(gè)結(jié)點(diǎn)的圖的圖G， G或或 中含有一個(gè)三角形（即中含有一個(gè)三角形（即K3）。）。 G 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) ) 證明證明: 設(shè)設(shè)GV ,E， |V|6，

17、 v是是G中一結(jié)點(diǎn)。中一結(jié)點(diǎn)。 因?yàn)橐驗(yàn)関 與與G的其余個(gè)結(jié)點(diǎn)或者在的其余個(gè)結(jié)點(diǎn)或者在 中鄰接，中鄰接， 或者在或者在G中鄰接。中鄰接。 故不失一般性可假定，故不失一般性可假定， 有個(gè)結(jié)點(diǎn)有個(gè)結(jié)點(diǎn)v1， v2， v3在在G中與中與v鄰接。鄰接。 如果這個(gè)結(jié)點(diǎn)中有兩個(gè)結(jié)點(diǎn)（如如果這個(gè)結(jié)點(diǎn)中有兩個(gè)結(jié)點(diǎn)（如v1， v2）鄰接，）鄰接， 則它們與則它們與v 就是就是G中一個(gè)三角形的個(gè)頂點(diǎn)。中一個(gè)三角形的個(gè)頂點(diǎn)。 如果這如果這3個(gè)結(jié)點(diǎn)中任意兩個(gè)在個(gè)結(jié)點(diǎn)中任意兩個(gè)在G中均不鄰接，中均不鄰接， 則則v1， v2， v3就就是是 中一個(gè)三角形的個(gè)頂點(diǎn)。中一個(gè)三角形的個(gè)頂點(diǎn)。 GG 10.1 圖的基本概念圖的基

18、本概念 第第1010章章 圖論圖論(Graph Theory ) ) 10.1.2 圖的結(jié)點(diǎn)的度數(shù)及其計(jì)算圖的結(jié)點(diǎn)的度數(shù)及其計(jì)算 我們常常需要關(guān)心圖中有多少條邊與某一結(jié)點(diǎn)我們常常需要關(guān)心圖中有多少條邊與某一結(jié)點(diǎn)關(guān)聯(lián)，這就引出了圖的一個(gè)重要概念關(guān)聯(lián)，這就引出了圖的一個(gè)重要概念結(jié)點(diǎn)的度數(shù)結(jié)點(diǎn)的度數(shù)。 10.1 圖的基本概念圖的基本概念 定義定義: 在有向圖中在有向圖中, 以以v為終點(diǎn)的邊數(shù)稱(chēng)為結(jié)點(diǎn)為終點(diǎn)的邊數(shù)稱(chēng)為結(jié)點(diǎn)v 的入的入度，度， 記為記為 ;以以v為始點(diǎn)的邊數(shù)稱(chēng)為結(jié)點(diǎn)為始點(diǎn)的邊數(shù)稱(chēng)為結(jié)點(diǎn)v 的出的出度，度， 記為記為 。結(jié)點(diǎn)。結(jié)點(diǎn)v的入度與出度之和稱(chēng)為結(jié)的入度與出度之和稱(chēng)為結(jié)點(diǎn)點(diǎn)v的度數(shù)，

19、記為的度數(shù)，記為 d(v)或或deg(v)。 ( )dv( )dv第第1010章章 圖論圖論(Graph Theory ) )定義定義: 在無(wú)向圖中，圖中結(jié)點(diǎn)在無(wú)向圖中，圖中結(jié)點(diǎn)v所關(guān)聯(lián)的邊數(shù)所關(guān)聯(lián)的邊數(shù)(有環(huán)時(shí)計(jì)算兩次有環(huán)時(shí)計(jì)算兩次)稱(chēng)為結(jié)點(diǎn)稱(chēng)為結(jié)點(diǎn)v 的度數(shù)，記為的度數(shù)，記為d(v)或或deg(v) 。| )(min)( | )(max)( VvvdGVvvdG最小度最大度第第1010章章 圖論圖論(Graph Theory ) )例例245136G1頂點(diǎn)頂點(diǎn)2入度：入度：1 出度：出度：3頂點(diǎn)頂點(diǎn)4入度：入度：1 出度：出度：0例例157324G26頂點(diǎn)頂點(diǎn)5的度：的度：3頂點(diǎn)頂點(diǎn)2的度

20、：的度：4第第1010章章 圖論圖論(Graph Theory ) ) 定理定理 10.1.1 無(wú)向圖無(wú)向圖GV ,E中結(jié)點(diǎn)度數(shù)的總和等中結(jié)點(diǎn)度數(shù)的總和等于邊數(shù)的兩倍，于邊數(shù)的兩倍， 即即證明證明: 因?yàn)槊織l邊都與兩個(gè)結(jié)點(diǎn)關(guān)聯(lián)，因?yàn)槊織l邊都與兩個(gè)結(jié)點(diǎn)關(guān)聯(lián)， 所以加上一條所以加上一條邊就使得各結(jié)點(diǎn)度數(shù)的和增加邊就使得各結(jié)點(diǎn)度數(shù)的和增加 2， 由此結(jié)論成立。由此結(jié)論成立。 定義定義：無(wú)向圖中，如果每個(gè)結(jié)點(diǎn)的度都是：無(wú)向圖中，如果每個(gè)結(jié)點(diǎn)的度都是k,則稱(chēng)為則稱(chēng)為k-度正則圖。度正則圖。d( )2VE 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) )推論

21、推論: 無(wú)向圖無(wú)向圖G中度數(shù)為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)。中度數(shù)為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)。證明證明: 設(shè)設(shè)V1和和V2分別是分別是G中奇數(shù)度數(shù)和偶數(shù)度數(shù)的結(jié)中奇數(shù)度數(shù)和偶數(shù)度數(shù)的結(jié)點(diǎn)集。點(diǎn)集。 由定理由定理10.1.1知知 由于由于 是偶數(shù)之和，是偶數(shù)之和， 必為偶數(shù)，必為偶數(shù)， 而而2|E|也為偶數(shù)，也為偶數(shù)， 故故 是偶數(shù)。是偶數(shù)。 由此由此|V1|必為偶數(shù)。必為偶數(shù)。1deg( )VEvvVvVv2)deg()deg(212)deg(Vvv 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) ) 定理定理 10.1.2 在任何有向圖在任何有向圖GV ,E

22、中，中， 有有( )( )v Vv VdvdvE圖圖10.1.4第第1010章章 圖論圖論(Graph Theory ) ) 10.1.3 子圖和圖的同構(gòu)子圖和圖的同構(gòu) 1.子圖子圖 在研究和描述圖的性質(zhì)時(shí)，子圖的概念占有在研究和描述圖的性質(zhì)時(shí)，子圖的概念占有重要地位。重要地位。 定義定義10.1.5 設(shè)有圖設(shè)有圖G=V , E和圖和圖 G= V, E 。 1) 若若VV， EE， 則稱(chēng)則稱(chēng)G是是G的的子圖子圖。 2) 若若G是是G的子圖，且的子圖，且EE，則稱(chēng)，則稱(chēng)G是是G 的的真子圖真子圖。 第第1010章章 圖論圖論(Graph Theory ) )356例例245136圖與子圖圖與子圖

23、第第1010章章 圖論圖論(Graph Theory ) ) 3) 若若V=V， EE，則稱(chēng)，則稱(chēng)G是是G的的生成子圖生成子圖。圖圖10.1.7給出了圖給出了圖G以及它的真子圖以及它的真子圖G1和生成子圖和生成子圖G2。 圖圖10.1.7 圖圖G以及其真子圖以及其真子圖G 1和生成子圖和生成子圖G2 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) )例例 畫(huà)出畫(huà)出K4的所有非同構(gòu)的生成子圖。的所有非同構(gòu)的生成子圖。第第1010章章 圖論圖論(Graph Theory ) )2221112222222222222 , , GV EGV Euvu vE

24、GVGVG VGEGEEEGV結(jié)點(diǎn)定義： 設(shè)圖是圖的子圖。若對(duì)任意結(jié)點(diǎn) 和 ，如果，則由唯一地確定，并稱(chēng)是，記為或。如果無(wú)孤立結(jié)點(diǎn)，且集合的誘導(dǎo)子圖邊集的誘導(dǎo)子圖由所唯一確定，則稱(chēng)是，記為或。第第1010章章 圖論圖論(Graph Theory ) ) 2. 圖的同構(gòu)圖的同構(gòu) 10.1 圖的基本概念圖的基本概念 試觀察下面各圖有何異同？試觀察下面各圖有何異同？第第1010章章 圖論圖論(Graph Theory ) ) 圖圖 10.1.8 同構(gòu)的圖同構(gòu)的圖 圖圖 10.1.9 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Graph Theory ) ) 定義定義10.1.6

25、 設(shè)有圖設(shè)有圖 G=V , E和圖和圖G= V, E。 如果存在雙射如果存在雙射：VV，使得，使得 e=(u, v) E iff e=(u),(v)E， 且且 (u， v)與與(u),(v)有相同的重?cái)?shù)，則稱(chēng)有相同的重?cái)?shù)，則稱(chēng)G與與G 同構(gòu)。記作同構(gòu)。記作G G。 注：由同構(gòu)的定義可知，不僅結(jié)點(diǎn)之間要具有一注：由同構(gòu)的定義可知，不僅結(jié)點(diǎn)之間要具有一一對(duì)應(yīng)關(guān)系，而且要求這種對(duì)應(yīng)關(guān)系保持結(jié)點(diǎn)間一對(duì)應(yīng)關(guān)系，而且要求這種對(duì)應(yīng)關(guān)系保持結(jié)點(diǎn)間的鄰接關(guān)系。對(duì)于有向圖的同構(gòu)還要求保持邊的的鄰接關(guān)系。對(duì)于有向圖的同構(gòu)還要求保持邊的方向。方向。 10.1 圖的基本概念圖的基本概念 第第1010章章 圖論圖論(Gr

26、aph Theory ) ) 【例【例10.1.5】考察圖考察圖10.1.9中的兩個(gè)圖中的兩個(gè)圖GV , E和和 G= V, E 。 顯然，定義顯然，定義：VV, (vi)v i , 可以驗(yàn)證可以驗(yàn)證是是滿足定義滿足定義10.1.6的雙射，所以的雙射，所以G G。 10.1 圖的基本概念圖的基本概念 圖圖 10.1.9第第1010章章 圖論圖論(Graph Theory ) ) 一般說(shuō)來(lái)，證明兩個(gè)圖是同構(gòu)的并非是一般說(shuō)來(lái)，證明兩個(gè)圖是同構(gòu)的并非是輕而易舉的事情，往往需要花些氣力。輕而易舉的事情，往往需要花些氣力。請(qǐng)讀者證明下圖中兩個(gè)圖是同構(gòu)的。請(qǐng)讀者證明下圖中兩個(gè)圖是同構(gòu)的。第第1010章章

27、圖論圖論(Graph Theory ) )第第1010章章 圖論圖論(Graph Theory ) ) 根據(jù)圖的同構(gòu)定義，可以給出圖同構(gòu)的必要條件根據(jù)圖的同構(gòu)定義，可以給出圖同構(gòu)的必要條件如下：如下：(1) 結(jié)點(diǎn)數(shù)目相等；結(jié)點(diǎn)數(shù)目相等；(2) 邊數(shù)相等；邊數(shù)相等；(3) 度數(shù)相同的結(jié)點(diǎn)數(shù)目相等。度數(shù)相同的結(jié)點(diǎn)數(shù)目相等。但這僅僅是必要條件而不是充分條件。但這僅僅是必要條件而不是充分條件。第第1010章章 圖論圖論(Graph Theory ) )下圖中的下圖中的(a)和和(b)滿足上述三個(gè)條件，然而并不同滿足上述三個(gè)條件，然而并不同構(gòu)。構(gòu)。因?yàn)樵谝驗(yàn)樵?a)中度數(shù)為中度數(shù)為3的結(jié)點(diǎn)的結(jié)點(diǎn)x與兩個(gè)

28、度數(shù)為與兩個(gè)度數(shù)為1的結(jié)點(diǎn)的結(jié)點(diǎn)鄰接，而鄰接，而(b)中度數(shù)為中度數(shù)為3的結(jié)點(diǎn)的結(jié)點(diǎn)y僅與一個(gè)度數(shù)為僅與一個(gè)度數(shù)為1的的結(jié)點(diǎn)鄰接。結(jié)點(diǎn)鄰接。尋找一種簡(jiǎn)單有效的方法來(lái)判定圖的同構(gòu)，至今尋找一種簡(jiǎn)單有效的方法來(lái)判定圖的同構(gòu)，至今仍是圖論中懸而未決的重要課題。仍是圖論中懸而未決的重要課題。第第1010章章 圖論圖論(Graph Theory ) )第第1010章章 圖論圖論(Graph Theory ) ) 對(duì)于同構(gòu)，對(duì)于同構(gòu)，形象地說(shuō)，若圖的結(jié)點(diǎn)可以任意形象地說(shuō)，若圖的結(jié)點(diǎn)可以任意挪動(dòng)位置，而邊是完全彈性的，只要在不拉斷挪動(dòng)位置，而邊是完全彈性的，只要在不拉斷的條件下，這個(gè)圖可以變形為另一個(gè)圖，那

29、么的條件下，這個(gè)圖可以變形為另一個(gè)圖，那么這兩個(gè)圖是同構(gòu)的。故同構(gòu)的兩個(gè)圖從外形上這兩個(gè)圖是同構(gòu)的。故同構(gòu)的兩個(gè)圖從外形上看可能不一樣，但它們的看可能不一樣，但它們的拓?fù)浣Y(jié)構(gòu)拓?fù)浣Y(jié)構(gòu)是一樣的。是一樣的。 第第1010章章 圖論圖論(Graph Theory ) )10.2 路與圖的連通性路與圖的連通性(Walks & The Connectivity of Graphs) 10.2.1 路與回路路與回路(Walks and Circuits) 10.2.2 圖的連通性圖的連通性(The Connectivity of Graphs) 第第1010章章 圖論圖論(Graph Theory

30、 ) )10.2.1 路與回路路與回路(Wlaks and Circuits) 定義定義 10.2.1 給定圖給定圖GV ,E, 設(shè)設(shè)v0, v1, , vkV， e1，e2，ekE，其中，其中ei是關(guān)聯(lián)于結(jié)點(diǎn)是關(guān)聯(lián)于結(jié)點(diǎn)vi-1和和vi的邊，的邊， 稱(chēng)交替序列稱(chēng)交替序列v0e1v1e2ekvk為為連接連接v0到到vk的路的路， v0和和vk分分別稱(chēng)為路的起點(diǎn)與終點(diǎn)。路中邊的數(shù)目別稱(chēng)為路的起點(diǎn)與終點(diǎn)。路中邊的數(shù)目k稱(chēng)作路的長(zhǎng)度。稱(chēng)作路的長(zhǎng)度。 當(dāng)當(dāng)v0=vk時(shí)時(shí),這條路稱(chēng)為回路。這條路稱(chēng)為回路。 在在簡(jiǎn)單圖簡(jiǎn)單圖中一條路中一條路v0e1v1e2ekvk由它的結(jié)點(diǎn)序列由它的結(jié)點(diǎn)序列v0v1vk確

31、定確定,所以簡(jiǎn)單圖的路所以簡(jiǎn)單圖的路,可表示為可表示為v0v1vk 。如圖。如圖10.1.1表示的簡(jiǎn)單圖中，表示的簡(jiǎn)單圖中， 路路ae1be4ce5d可寫(xiě)成可寫(xiě)成abcd。 第第1010章章 圖論圖論(Graph Theory ) ) 定義定義 10.2.2 設(shè)設(shè)=v0e1v1e2ekvk是圖是圖G中連接中連接v0到到vk的的路。路。 1)若若e1， e2， ， ek都不相同，都不相同， 則稱(chēng)路則稱(chēng)路為簡(jiǎn)單路為簡(jiǎn)單路或跡；或跡； 2)若若v0， v1， ， vk都不相同，則稱(chēng)路都不相同，則稱(chēng)路為基本路為基本路或通路；或通路； 3) 圈中若出現(xiàn)的每條邊恰好一次，稱(chēng)簡(jiǎn)單圈。若圈中若出現(xiàn)的每條邊恰好

32、一次，稱(chēng)簡(jiǎn)單圈。若出現(xiàn)的每個(gè)結(jié)點(diǎn)恰好一次，稱(chēng)基本圈。出現(xiàn)的每個(gè)結(jié)點(diǎn)恰好一次，稱(chēng)基本圈。 10.2.1 路與回路路與回路(Wlaks and Circuits)第第1010章章 圖論圖論(Graph Theory ) )結(jié)點(diǎn)重復(fù)情況結(jié)點(diǎn)重復(fù)情況邊重復(fù)情況邊重復(fù)情況路路 允許允許 允許允許簡(jiǎn)單路簡(jiǎn)單路 允許允許不允許不允許 基本路基本路 不允許不允許 不允許不允許 回路回路允許允許允許允許簡(jiǎn)單圈簡(jiǎn)單圈允許允許不允許不允許基本圈基本圈不允許不允許不允許不允許10.2.1 路與回路路與回路(Wlaks and Circuits)第第1010章章 圖論圖論(Graph Theory ) )注意：不同的教

33、材定義不同！注意：不同的教材定義不同！途徑途徑(walk)：圖：圖G中一個(gè)點(diǎn)邊交替出現(xiàn)的序列。中一個(gè)點(diǎn)邊交替出現(xiàn)的序列。跡跡(trail)：邊不重的途徑。：邊不重的途徑。路路(path): 頂點(diǎn)不重復(fù)的跡。頂點(diǎn)不重復(fù)的跡。閉途徑（閉途徑（closed walk）：起點(diǎn)和終點(diǎn)相同的途徑。）：起點(diǎn)和終點(diǎn)相同的途徑。閉跡閉跡(closed trail)：起點(diǎn)和終點(diǎn)相同的跡，也稱(chēng)為回：起點(diǎn)和終點(diǎn)相同的跡，也稱(chēng)為回路（路（circuit）。）。圈圈(cycle): 起點(diǎn)和終點(diǎn)相同的路。起點(diǎn)和終點(diǎn)相同的路。10.2.1 路與回路路與回路(Wlaks and Circuits)第第1010章章 圖論圖論(G

34、raph Theory ) )例例157324G26例例245136G1路徑：路徑：1，2，3，5，6，3路徑長(zhǎng)度：路徑長(zhǎng)度：5簡(jiǎn)單路徑：簡(jiǎn)單路徑：1，2，3，5回路：回路：1，2，3，5，6，3，1簡(jiǎn)單回路：簡(jiǎn)單回路：3，5，6，3路徑：路徑：1，2，5，7，6，5，2，3路徑長(zhǎng)度：路徑長(zhǎng)度：7簡(jiǎn)單路徑：簡(jiǎn)單路徑：1，2，5，7，6回路：回路：1，2，5，7，6，5，2，1簡(jiǎn)單回路：簡(jiǎn)單回路：1，2，3，1第第1010章章 圖論圖論(Graph Theory ) ) 例如在圖例如在圖 10.2.1中，中， 有連接有連接v5到到v3的路的路v5e8v4e5v2e6v5e7v3， 這也是一條簡(jiǎn)單

35、路；路這也是一條簡(jiǎn)單路；路 v1e1v2 e3v3是一條基本路；是一條基本路； 路路v1e1v2e3v3e4v2e1v1是一是一 條回路，條回路， 但不是基本圈；但不是基本圈； 路路v1e1v2e3v3e2v1是一條是一條 回路，回路， 也是圈。也是圈。 圖圖 10.2.1 10.2.1 路與回路路與回路(Wlaks and Circuits)第第1010章章 圖論圖論(Graph Theory ) ) 定義定義 10.2.3 在圖在圖G中，中， 若結(jié)點(diǎn)若結(jié)點(diǎn)vi到到vj有路連接有路連接（這時(shí)稱(chēng)（這時(shí)稱(chēng)vi和和vj是可達(dá)的），是可達(dá)的）， 其中長(zhǎng)度最短的其中長(zhǎng)度最短的路的長(zhǎng)度稱(chēng)為路的長(zhǎng)度稱(chēng)為v

36、i到到vj 的距離，的距離， 用符號(hào)用符號(hào)d(vi,vj)表表示。若從示。若從vi到到vj不存在路徑不存在路徑,則則d(vi,vj)=。 例如在圖例如在圖10.2.1中，中， （v1， v4）。）。 10.2.1 路與回路路與回路(Wlaks and Circuits)第第1010章章 圖論圖論(Graph Theory ) ) 注意注意:在有向圖中在有向圖中,d(vi,vj)不一定等于不一定等于d(vj,vi), 但一般地滿足以下性質(zhì)但一般地滿足以下性質(zhì): (1) d(vi,vj)0; (2) d(vi,vi)=0; (3) d(vi,vj)+d(vj,vk)d(vi,vk)。 圖圖 10.

37、2.1 10.2.1 路與回路路與回路(Wlaks and Circuits)第第1010章章 圖論圖論(Graph Theory ) ) 定理定理 10.2.1 設(shè)設(shè)G是具有是具有n個(gè)結(jié)點(diǎn)的圖，個(gè)結(jié)點(diǎn)的圖， 如果從結(jié)點(diǎn)如果從結(jié)點(diǎn)v1到另一結(jié)點(diǎn)到另一結(jié)點(diǎn)v2存在一條路，則存在一條路，則從結(jié)點(diǎn)從結(jié)點(diǎn)v1到到v2必存在一條長(zhǎng)度不大于必存在一條長(zhǎng)度不大于n1的的基本路（通路）?；韭罚ㄍ罚?。 10.2.1 路與回路路與回路(Wlaks and Circuits)第第1010章章 圖論圖論(Graph Theory ) ) 證明證明:假定從假定從v1到到v2存在一條路徑存在一條路徑,(v1,vi,v

38、2)是所是所經(jīng)的結(jié)點(diǎn)經(jīng)的結(jié)點(diǎn),如果其中有相同的結(jié)點(diǎn)如果其中有相同的結(jié)點(diǎn)vk,例例 (v1,vi,vk,vk,v2),則刪去從則刪去從vk到到vk的這些邊的這些邊,它它仍是從仍是從v1到到v2的路徑的路徑,如此反復(fù)地進(jìn)行直至如此反復(fù)地進(jìn)行直至(v1,vi,v2)中沒(méi)有重復(fù)結(jié)點(diǎn)為止。此時(shí)中沒(méi)有重復(fù)結(jié)點(diǎn)為止。此時(shí),所得的就是通路。通路的所得的就是通路。通路的長(zhǎng)度比所經(jīng)結(jié)點(diǎn)數(shù)少長(zhǎng)度比所經(jīng)結(jié)點(diǎn)數(shù)少1,圖中共圖中共n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),故通路長(zhǎng)度不故通路長(zhǎng)度不超過(guò)超過(guò)n-1。 推論推論 設(shè)圖設(shè)圖GV ,E ， |V|n， 則則G中任一基本中任一基本圈長(zhǎng)度不大于圈長(zhǎng)度不大于n。10.2.1 路與回路路與回路(Wl

39、aks and Circuits)第第1010章章 圖論圖論(Graph Theory ) ) 1. 無(wú)向圖的連通性無(wú)向圖的連通性 定義定義 10.2.4 在無(wú)向圖如果一個(gè)圖的任何兩個(gè)結(jié)點(diǎn)在無(wú)向圖如果一個(gè)圖的任何兩個(gè)結(jié)點(diǎn)之間都有一條路，那么我們稱(chēng)這個(gè)圖是連通的，否之間都有一條路，那么我們稱(chēng)這個(gè)圖是連通的，否則是不連通的。則是不連通的。 定義定義 10.2.5 圖圖G的一個(gè)連通的子圖的一個(gè)連通的子圖G（稱(chēng)為（稱(chēng)為 連通連通子圖）若不包含在子圖）若不包含在G的任何更大的連通子圖中，的任何更大的連通子圖中， 它它就被稱(chēng)作就被稱(chēng)作G的連通分支。我們把圖的連通分支。我們把圖G的連通分支個(gè)的連通分支個(gè)數(shù)記

40、作數(shù)記作（G）。）。10.2.2 圖的連通性圖的連通性(The Connectivity of Graphs)第第1010章章 圖論圖論(Graph Theory ) )圖圖 10.2.3 圖圖G與與G 在圖在圖10.2.3中，中， G是不連通的，是不連通的， （G），）， 而而G是是連通的，連通的， （G）。）。 任何一個(gè)圖都可劃分為若干個(gè)連通分支。任何一個(gè)圖都可劃分為若干個(gè)連通分支。 顯然，顯然， 僅當(dāng)圖僅當(dāng)圖G的連通分支數(shù)的連通分支數(shù) （G）時(shí)，）時(shí)， 圖圖G是連通的。是連通的。10.2.2 圖的連通性圖的連通性第第1010章章 圖論圖論(Graph Theory ) ) 在圖的研究中，

41、常常需要考慮刪去與增加結(jié)點(diǎn)、在圖的研究中，常常需要考慮刪去與增加結(jié)點(diǎn)、結(jié)點(diǎn)集、邊和邊集（或弧集）的問(wèn)題。所謂從結(jié)點(diǎn)集、邊和邊集（或弧集）的問(wèn)題。所謂從圖圖G=中刪去結(jié)點(diǎn)集中刪去結(jié)點(diǎn)集S，是指作，是指作V-S以及從以及從E中刪去與中刪去與S中的全部結(jié)點(diǎn)相聯(lián)結(jié)的邊而得到的中的全部結(jié)點(diǎn)相聯(lián)結(jié)的邊而得到的子圖，記作子圖，記作G-S；特別當(dāng)；特別當(dāng)S=v時(shí)，簡(jiǎn)記為時(shí)，簡(jiǎn)記為G-v；所謂從圖所謂從圖G=中刪去邊集（或弧集）中刪去邊集（或弧集）T，是指作是指作E-T，且，且T中的全部邊所關(guān)聯(lián)的結(jié)點(diǎn)仍在中的全部邊所關(guān)聯(lián)的結(jié)點(diǎn)仍在V中而得到的子圖，記為中而得到的子圖，記為G-T；特別當(dāng)；特別當(dāng)T=e 時(shí)，時(shí)，簡(jiǎn)

42、記作簡(jiǎn)記作G-e。第第1010章章 圖論圖論(Graph Theory ) ) 所謂圖所謂圖G=增加結(jié)點(diǎn)集增加結(jié)點(diǎn)集S，是指作，是指作VS以以及向及向E中并入中并入S中、中、S與與V中所成的邊而得到的中所成的邊而得到的圖，記作圖，記作G+S；特別當(dāng)；特別當(dāng)S=v 時(shí)，簡(jiǎn)記為時(shí)，簡(jiǎn)記為G+v；圖圖G=增加邊集（或弧集）增加邊集（或弧集）T是指作是指作ET所得到的圖，記作所得到的圖，記作G+T，這里，這里T中全部邊（或中全部邊（或?。┑年P(guān)聯(lián)結(jié)點(diǎn)屬于?。┑年P(guān)聯(lián)結(jié)點(diǎn)屬于V。第第1010章章 圖論圖論(Graph Theory ) ) 定義定義: 給定連通無(wú)向圖給定連通無(wú)向圖G=，S V。若。若(G-S

43、)(G)，但，但 T S有有 (G-T)= (G)，則稱(chēng)，則稱(chēng)S是是G的一個(gè)分離結(jié)點(diǎn)集。若圖的一個(gè)分離結(jié)點(diǎn)集。若圖G的分離結(jié)點(diǎn)集的分離結(jié)點(diǎn)集S=v ，則稱(chēng)，則稱(chēng)v是是G的的割點(diǎn)割點(diǎn)。 類(lèi)似地可定義圖類(lèi)似地可定義圖G的分離邊集的分離邊集T；若圖；若圖G的分離的分離邊集邊集T=e ，則稱(chēng)，則稱(chēng)e是是G的的割邊或橋割邊或橋。第第1010章章 圖論圖論(Graph Theory ) ) 對(duì)于連通的非平凡圖對(duì)于連通的非平凡圖G，稱(chēng)，稱(chēng) (G)= |S|S是是G的分的分離結(jié)點(diǎn)集離結(jié)點(diǎn)集 為圖為圖G的的結(jié)點(diǎn)連通度，它表明產(chǎn)生不結(jié)點(diǎn)連通度，它表明產(chǎn)生不連通圖而需要?jiǎng)h去結(jié)點(diǎn)的最少數(shù)目連通圖而需要?jiǎng)h去結(jié)點(diǎn)的最少數(shù)

44、目。于是，對(duì)。于是，對(duì)于分離圖于分離圖G， (G)=0；對(duì)于存在割點(diǎn)的連通圖；對(duì)于存在割點(diǎn)的連通圖G， (G)=1。VSmin第第1010章章 圖論圖論(Graph Theory ) ) 類(lèi)似地定義邊連通度類(lèi)似地定義邊連通度 (G)= |T|T是是G的分離邊的分離邊集集 ，它，它表明產(chǎn)生不連通圖而需要?jiǎng)h去邊的最少表明產(chǎn)生不連通圖而需要?jiǎng)h去邊的最少數(shù)目數(shù)目?？梢?jiàn)，對(duì)于分離圖?？梢?jiàn)，對(duì)于分離圖G， (G)=0；對(duì)于平凡；對(duì)于平凡圖圖G， (G)=0；對(duì)于圖；對(duì)于圖K1， (K1)=0；對(duì)于存在割；對(duì)于存在割邊的連通圖邊的連通圖G， (G)=1；對(duì)于完全圖；對(duì)于完全圖Kn， (Kn)=n-1。ETm

45、in第第1010章章 圖論圖論(Graph Theory ) ) 下面是由惠特尼下面是由惠特尼(H.Whitney)于于1932年得到的關(guān)年得到的關(guān)于結(jié)點(diǎn)連通度、邊連通度和最小度的不等式聯(lián)于結(jié)點(diǎn)連通度、邊連通度和最小度的不等式聯(lián)系的定理：系的定理：定理定理: 對(duì)于任何一個(gè)無(wú)向圖對(duì)于任何一個(gè)無(wú)向圖G，有，有 (G) (G)(G)。定理定理: 一個(gè)連通無(wú)向圖一個(gè)連通無(wú)向圖G中的結(jié)點(diǎn)中的結(jié)點(diǎn)v是割點(diǎn)是割點(diǎn)存在兩存在兩個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)u和和w，使得聯(lián)結(jié)，使得聯(lián)結(jié)u和和w的每條鏈都經(jīng)過(guò)的每條鏈都經(jīng)過(guò)v。第第1010章章 圖論圖論(Graph Theory ) )定理定理: 一個(gè)連通無(wú)向圖一個(gè)連通無(wú)向圖G中的

46、邊中的邊e是割邊是割邊 存在兩個(gè)存在兩個(gè)結(jié)點(diǎn)結(jié)點(diǎn)u和和w，使得聯(lián)結(jié)，使得聯(lián)結(jié)u與與w的每條鏈都經(jīng)過(guò)的每條鏈都經(jīng)過(guò)e。下面再給出一個(gè)判定一條邊是割邊的充要條件。下面再給出一個(gè)判定一條邊是割邊的充要條件。定理定理: 連通無(wú)向圖連通無(wú)向圖G中的一條邊中的一條邊e是割邊是割邊e不包含不包含在圖的任何基本圈中。在圖的任何基本圈中。第第1010章章 圖論圖論(Graph Theory ) ) 2. 有向圖的連通性有向圖的連通性 定義定義10.2.6 在有向圖中在有向圖中,若從結(jié)點(diǎn)若從結(jié)點(diǎn)u到到v有一有一條路，則稱(chēng)條路，則稱(chēng)u可達(dá)可達(dá)v。 定義定義10.2.7 設(shè)有有向圖設(shè)有有向圖G， 1)若若G的任意兩個(gè)

47、結(jié)點(diǎn)中的任意兩個(gè)結(jié)點(diǎn)中,至少?gòu)囊粋€(gè)結(jié)點(diǎn)可至少?gòu)囊粋€(gè)結(jié)點(diǎn)可達(dá)另一個(gè)結(jié)點(diǎn)達(dá)另一個(gè)結(jié)點(diǎn),則稱(chēng)圖則稱(chēng)圖G是單向連通的是單向連通的; 10.2.2 圖的連通性圖的連通性第第1010章章 圖論圖論(Graph Theory ) ) 2)如果如果G的任意兩個(gè)結(jié)點(diǎn)都是相互可達(dá)的的任意兩個(gè)結(jié)點(diǎn)都是相互可達(dá)的,則稱(chēng)圖則稱(chēng)圖G是強(qiáng)連通的是強(qiáng)連通的; 3)如果略去邊的方向后，如果略去邊的方向后， G成為連通的無(wú)向圖，則成為連通的無(wú)向圖，則稱(chēng)圖稱(chēng)圖G是弱連通的。是弱連通的。 從定義可知：從定義可知： 若圖若圖G是單向連通的，是單向連通的， 則必是弱連通的；若圖則必是弱連通的；若圖G是強(qiáng)連通的，是強(qiáng)連通的， 則則必是單向

48、連通的，必是單向連通的， 且也是弱連通的。且也是弱連通的。 但反但反之不真。之不真。 第第1010章章 圖論圖論(Graph Theory ) ) 定理定理 10.2.2一個(gè)有向圖一個(gè)有向圖G是強(qiáng)連通的，是強(qiáng)連通的， 當(dāng)當(dāng)且僅當(dāng)且僅當(dāng)G中有一個(gè)（有向）回路，中有一個(gè)（有向）回路， 它至少它至少包含每個(gè)結(jié)點(diǎn)一次。包含每個(gè)結(jié)點(diǎn)一次。 第第1010章章 圖論圖論(Graph Theory ) )證明證明: 必要性：如果有向圖必要性：如果有向圖G是強(qiáng)連通的，則任意是強(qiáng)連通的，則任意兩個(gè)結(jié)點(diǎn)都是相互可達(dá)的。故必可作一回路經(jīng)過(guò)兩個(gè)結(jié)點(diǎn)都是相互可達(dá)的。故必可作一回路經(jīng)過(guò)圖中所有各結(jié)點(diǎn)。否則必有一回路不包含某

49、一結(jié)圖中所有各結(jié)點(diǎn)。否則必有一回路不包含某一結(jié)點(diǎn)點(diǎn)v。這樣，這樣，v與回路上各結(jié)點(diǎn)就不能相互可達(dá)，與回路上各結(jié)點(diǎn)就不能相互可達(dá)， 這與這與G是強(qiáng)連通矛盾。是強(qiáng)連通矛盾。 充分性：如果充分性：如果G中有一個(gè)回路，它至少包含中有一個(gè)回路，它至少包含每個(gè)結(jié)點(diǎn)一次，則每個(gè)結(jié)點(diǎn)一次，則G中任意兩個(gè)結(jié)點(diǎn)是相互可達(dá)的，中任意兩個(gè)結(jié)點(diǎn)是相互可達(dá)的， 故故G是強(qiáng)連通的。是強(qiáng)連通的。 10.2.2 圖的連通性圖的連通性第第1010章章 圖論圖論(Graph Theory ) ) 定義定義 10.2.8 在有向圖在有向圖G=V,E中中,G是是G的子的子圖圖,若若G是強(qiáng)連通的是強(qiáng)連通的(單向連通的單向連通的,弱連通的

50、弱連通的),沒(méi)沒(méi)有包含有包含G的更大子圖的更大子圖G是強(qiáng)連通的是強(qiáng)連通的(單向連通單向連通的的,弱連通的弱連通的),則稱(chēng)則稱(chēng)G是是G的強(qiáng)分圖的強(qiáng)分圖(單向分圖單向分圖,弱弱分圖分圖)。 10.2.2 圖的連通性圖的連通性第第1010章章 圖論圖論(Graph Theory ) )連通圖連通圖例例245136強(qiáng)連通圖強(qiáng)連通圖356例例非連通圖非連通圖連通分圖連通分圖例例245136第第1010章章 圖論圖論(Graph Theory ) )圖圖 10.2.5 10.2.2 圖的連通性圖的連通性(The Connectivity of Graphs)第第1010章章 圖論圖論(Graph Theo

51、ry ) )在圖在圖10.2.5中中,強(qiáng)分圖集合是強(qiáng)分圖集合是: 1,2,3,e1,e2,e3,4,5,6,7,8,e7,e8單向分圖集合是單向分圖集合是: 1,2,3,4,5,e1,e2,e3,e4,e5,6,5,e6, 7,8,e7,e8 弱分圖集合是弱分圖集合是: 1,2,3,4,5,6,e1,e2,e3,e4,e5,e6, 7,8,e7,e810.2.2 圖的連通性圖的連通性第第1010章章 圖論圖論(Graph Theory ) )下面給出簡(jiǎn)單有向圖的一個(gè)應(yīng)用下面給出簡(jiǎn)單有向圖的一個(gè)應(yīng)用資源分配圖。資源分配圖。 在多道程序的計(jì)算機(jī)系統(tǒng)中，可以同時(shí)執(zhí)行多個(gè)在多道程序的計(jì)算機(jī)系統(tǒng)中，可以

52、同時(shí)執(zhí)行多個(gè)程序。實(shí)際上，程序共享計(jì)算機(jī)系統(tǒng)中的資源，程序。實(shí)際上，程序共享計(jì)算機(jī)系統(tǒng)中的資源，如磁帶機(jī)、磁盤(pán)設(shè)備、如磁帶機(jī)、磁盤(pán)設(shè)備、CPU、主存貯器和編譯程、主存貯器和編譯程序等。操作系統(tǒng)對(duì)這些資源負(fù)責(zé)分配給各個(gè)程序。序等。操作系統(tǒng)對(duì)這些資源負(fù)責(zé)分配給各個(gè)程序。當(dāng)一個(gè)程序要求使用某種資源，它要發(fā)出請(qǐng)求，當(dāng)一個(gè)程序要求使用某種資源，它要發(fā)出請(qǐng)求，操作系統(tǒng)必須保證這一請(qǐng)求得到滿足。操作系統(tǒng)必須保證這一請(qǐng)求得到滿足。第第1010章章 圖論圖論(Graph Theory ) )對(duì)資源的請(qǐng)求可能發(fā)生沖突。如程序?qū)Y源的請(qǐng)求可能發(fā)生沖突。如程序A控制著資控制著資源源r1，請(qǐng)求資源，請(qǐng)求資源r2；但程序

53、；但程序B控制著資源控制著資源r2，請(qǐng)求，請(qǐng)求資源資源r1。這種情況稱(chēng)為處于死鎖狀態(tài)。然而沖突。這種情況稱(chēng)為處于死鎖狀態(tài)。然而沖突的請(qǐng)求必須解決，資源分配圖有助發(fā)現(xiàn)和糾正死的請(qǐng)求必須解決，資源分配圖有助發(fā)現(xiàn)和糾正死鎖。鎖。假設(shè)某一程序?qū)σ恍┵Y源的請(qǐng)求，在該程序運(yùn)行假設(shè)某一程序?qū)σ恍┵Y源的請(qǐng)求，在該程序運(yùn)行完之前必須都得到滿足。在請(qǐng)求的時(shí)間里，被請(qǐng)完之前必須都得到滿足。在請(qǐng)求的時(shí)間里，被請(qǐng)求的資源是不能利用的，程序控制著可利用的資求的資源是不能利用的，程序控制著可利用的資源，但對(duì)不可利用的資源則必須等待。源，但對(duì)不可利用的資源則必須等待。第第1010章章 圖論圖論(Graph Theory )

54、)令令Pt=p1，p2，pm 表示計(jì)算機(jī)系統(tǒng)在時(shí)刻表示計(jì)算機(jī)系統(tǒng)在時(shí)刻t的的程序集合，程序集合，Qt Pt是運(yùn)行的程序集合，或者說(shuō)在時(shí)是運(yùn)行的程序集合，或者說(shuō)在時(shí)刻刻t至少分配一部分所請(qǐng)求的資源的程序集合。至少分配一部分所請(qǐng)求的資源的程序集合。Rt=r1，r2，rn 是系統(tǒng)在時(shí)刻是系統(tǒng)在時(shí)刻t的資源集合。的資源集合。資源分配圖資源分配圖Gt=是有向圖，它表示了時(shí)刻是有向圖，它表示了時(shí)刻t系統(tǒng)中資源分配狀態(tài)。把每個(gè)資源系統(tǒng)中資源分配狀態(tài)。把每個(gè)資源ri看作圖中一個(gè)看作圖中一個(gè)結(jié)點(diǎn)，其中結(jié)點(diǎn)，其中i=1，2，n。表示有向邊，表示有向邊，E當(dāng)且僅當(dāng)程序當(dāng)且僅當(dāng)程序pkQt已分配到資源已分配到資源ri

55、且且等待資源等待資源rj。第第1010章章 圖論圖論(Graph Theory ) )例如，令例如，令Rt=r1,r2,r3,r4 ，Qt=p1,p2,p3,p4 。資源分。資源分配狀態(tài)是：配狀態(tài)是：p1占用資源占用資源r4且請(qǐng)求資源且請(qǐng)求資源r1；p2占用資源占用資源r1且請(qǐng)求資源且請(qǐng)求資源r2和和r3；p3占用資源占用資源r2且請(qǐng)求資源且請(qǐng)求資源r3；p4占用資源占用資源r3且請(qǐng)求資源且請(qǐng)求資源r1和和r4。第第1010章章 圖論圖論(Graph Theory ) )于是，可得到資源分配圖于是，可得到資源分配圖Gt=，如圖，如圖10.2.7所示。所示。能夠證明，在時(shí)刻能夠證明，在時(shí)刻t計(jì)算

56、機(jī)系統(tǒng)處于死鎖狀態(tài)計(jì)算機(jī)系統(tǒng)處于死鎖狀態(tài)資源分配圖資源分配圖Gt中包含強(qiáng)分圖。于是，對(duì)于圖中包含強(qiáng)分圖。于是，對(duì)于圖10.2.7，Gt是強(qiáng)連通的，即處于死鎖狀態(tài)。是強(qiáng)連通的，即處于死鎖狀態(tài)。第第1010章章 圖論圖論(Graph Theory ) )圖圖 10.2.7第第1010章章 圖論圖論(Graph Theory ) )10.3 圖的矩陣表示圖的矩陣表示(Matrix Notation of Graph) 10.3.1 鄰接矩陣鄰接矩陣 (Adjacency Matrices) 10.3.2 可達(dá)性矩陣可達(dá)性矩陣 (Reachability Matrices )第第1010章章 圖論圖論

57、(Graph Theory ) )10.3.1鄰接矩陣鄰接矩陣 (Adjacency Matrices) 上面我們介紹了圖的一種表示方法，上面我們介紹了圖的一種表示方法， 即即用圖形表示圖。用圖形表示圖。 它的優(yōu)點(diǎn)是形象直觀，它的優(yōu)點(diǎn)是形象直觀， 但是但是這種表示在結(jié)點(diǎn)與邊的數(shù)目很多時(shí)是不方便的。這種表示在結(jié)點(diǎn)與邊的數(shù)目很多時(shí)是不方便的。 下面我們提供另一種用矩陣表示圖的方法。下面我們提供另一種用矩陣表示圖的方法。 利利用這種方法，用這種方法， 我們能把圖用矩陣存儲(chǔ)在計(jì)算機(jī)我們能把圖用矩陣存儲(chǔ)在計(jì)算機(jī)中，中， 利用矩陣的運(yùn)算還可以了解到它的一些有利用矩陣的運(yùn)算還可以了解到它的一些有關(guān)性質(zhì)。關(guān)性

58、質(zhì)。第第1010章章 圖論圖論(Graph Theory ) ) 定義定義 10.3.1 設(shè)設(shè)GV ,E是有是有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖， 則則n階方陣（階方陣（aij）稱(chēng)為）稱(chēng)為G的鄰接矩陣。的鄰接矩陣。 其中其中1( ,)0ijijEa 否則否則 如圖如圖10.3.1所示的圖所示的圖G， 其鄰接矩陣其鄰接矩陣A為為10.3 圖的矩陣表示圖的矩陣表示(Matrix Notation of Graph) 第第1010章章 圖論圖論(Graph Theory ) )0111110100110101010110010A 顯然無(wú)向圖的鄰接矩陣必是對(duì)稱(chēng)的。顯然無(wú)向圖的鄰接矩陣必是對(duì)稱(chēng)的。 下面

59、的定理說(shuō)明，下面的定理說(shuō)明， 在鄰接矩陣在鄰接矩陣A的冪的冪A2， A3， 等矩陣中，等矩陣中， 每個(gè)元素有特定的含義。每個(gè)元素有特定的含義。 圖圖10.3.1 G 10.3 圖的矩陣表示圖的矩陣表示(Matrix Notation of Graph) 第第1010章章 圖論圖論(Graph Theory ) )圖圖10.3.1 圖圖G 10.3 圖的矩陣表示圖的矩陣表示(Matrix Notation of Graph) 第第1010章章 圖論圖論(Graph Theory ) ) 定理定理 10.3.1 設(shè)設(shè)G是具有是具有n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)v1, v2, ,vn 的的圖，圖， 其鄰接矩陣為其鄰

60、接矩陣為A， 則則Ak（k1， 2， ）的（）的（i， j）項(xiàng)元素項(xiàng)元素a(k)ij是從是從vi到到vj的長(zhǎng)度等于的長(zhǎng)度等于k的路的總數(shù)。的路的總數(shù)。 證明證明: 施歸納于施歸納于k。 當(dāng)當(dāng)k1時(shí)，時(shí)， A1A， 由由A的定義，的定義， 定理顯然成立。定理顯然成立。 若若kl時(shí)定理成立，時(shí)定理成立， 則當(dāng)則當(dāng)kl1時(shí)，時(shí)， A l+1Al A， 所以所以 rjnrlirlijaaa1)()1(10.3 圖的矩陣表示圖的矩陣表示(Matrix Notation of Graph) 第第1010章章 圖論圖論(Graph Theory ) ) 根據(jù)鄰接矩陣定義根據(jù)鄰接矩陣定義arj是聯(lián)結(jié)是聯(lián)結(jié)vr和和vj的長(zhǎng)度為的長(zhǎng)度