離散課件北極熊校園第9

1、2022-4-62022-4-6第四篇第四篇 圖論圖論 圖論是一門很有實(shí)用價值的學(xué)科，它在圖論是一門很有實(shí)用價值的學(xué)科，它在自然科自然科學(xué)、社會科學(xué)學(xué)、社會科學(xué)等各領(lǐng)域均有很多等各領(lǐng)域均有很多應(yīng)用應(yīng)用。自上世紀(jì)中。自上世紀(jì)中葉以來，它受計(jì)算機(jī)科學(xué)蓬勃發(fā)展的刺激，發(fā)展極葉以來，它受計(jì)算機(jī)科學(xué)蓬勃發(fā)展的刺激，發(fā)展極其迅速，應(yīng)用范圍不斷拓廣，已滲透到諸如其迅速，應(yīng)用范圍不斷拓廣，已滲透到諸如語言學(xué)語言學(xué)、邏輯學(xué)邏輯學(xué)、物理學(xué)物理學(xué)、化學(xué)化學(xué)、電訊工程電訊工程、計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué)以以及及數(shù)學(xué)的其它分支數(shù)學(xué)的其它分支中。特別在計(jì)算機(jī)科學(xué)中，如中。特別在計(jì)算機(jī)科學(xué)中，如形形式語言式語言、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)

2、、分布式系統(tǒng)分布式系統(tǒng)、操作系統(tǒng)操作系統(tǒng)等方面等方面均扮演著重要的角色。均扮演著重要的角色。 2022-4-62022-4-6第四篇第四篇 圖論圖論第第9 9章章 圖圖2022-4-62022-4-69.2 9.2 圖的基本概念圖的基本概念 9.2.1 9.2.1 圖的定義圖的定義例例9.2.19.2.1（1 1）考慮一張航線地圖，圖中用點(diǎn)表示城考慮一張航線地圖，圖中用點(diǎn)表示城市，當(dāng)兩個城市間有直達(dá)航班時，就用一條線將相市，當(dāng)兩個城市間有直達(dá)航班時，就用一條線將相應(yīng)的點(diǎn)連接起來。這種航線地圖的一部分如下圖所應(yīng)的點(diǎn)連接起來。這種航線地圖的一部分如下圖所示；示；長春長春北京北京成都成都武漢武漢上海

3、上海2022-4-62022-4-6基本思想基本思想 對于這種圖形，我們感興趣的只是對于這種圖形，我們感興趣的只是有多少個點(diǎn)有多少個點(diǎn)和和哪些結(jié)點(diǎn)之間有線連接哪些結(jié)點(diǎn)之間有線連接，至于連線的長短曲直和，至于連線的長短曲直和結(jié)點(diǎn)的位置卻無關(guān)緊要，只要求每一條線都起始于結(jié)點(diǎn)的位置卻無關(guān)緊要，只要求每一條線都起始于一個點(diǎn)，而終止于另一個點(diǎn)。一個點(diǎn)，而終止于另一個點(diǎn)。 2022-4-62022-4-6定義定義9.2.19.2.1 一個一個圖圖(Graph)(Graph)是一個是一個序偶序偶，記為，記為G = G = （1 1）V = vV = v1 1, v, v2 2, , , v, vn n 是是

4、節(jié)點(diǎn)集節(jié)點(diǎn)集, ,是是有限非空有限非空集合集合，v vi i稱為稱為結(jié)點(diǎn)結(jié)點(diǎn)(Nodal Point)(Nodal Point) 。（2 2）E E是是有限集合有限集合，稱為，稱為邊集邊集(Frontier Set)(Frontier Set)。E E中的每條中的每條邊邊都有都有V V中的結(jié)點(diǎn)對與之對應(yīng)。中的結(jié)點(diǎn)對與之對應(yīng)。 無向邊無向邊e e與與無序結(jié)點(diǎn)對無序結(jié)點(diǎn)對(u,v)(u,v)相對應(yīng)，記為相對應(yīng)，記為e = e = (u, v) = (v, u)(u, v) = (v, u)，u u、v v是兩個是兩個端點(diǎn)端點(diǎn)(End point)(End point)。 有向邊有向邊e e與與有序

5、結(jié)點(diǎn)有序結(jié)點(diǎn)對對相對應(yīng)，記為相對應(yīng)，記為e = e = ，這時稱，這時稱u u為為始點(diǎn)始點(diǎn)，v v為為終點(diǎn)終點(diǎn)。 2022-4-62022-4-69.2.2 9.2.2 圖的表示圖的表示 對于一個圖對于一個圖G G，如果將其記為，如果將其記為G = G = ，并，并寫出寫出V V和和E E的集合表示，這稱為的集合表示，這稱為圖的集合表示圖的集合表示。 而為了描述簡便起見，在一般情況下，往往只而為了描述簡便起見，在一般情況下，往往只畫出它的圖形：用小圓圈表示畫出它的圖形：用小圓圈表示V V中的結(jié)點(diǎn)，用由中的結(jié)點(diǎn)，用由u u指指向向v v的有向線段或曲線表示有向邊的有向線段或曲線表示有向邊，無向線

6、，無向線段或曲線表示無向邊段或曲線表示無向邊(u, v)(u, v)，這稱為，這稱為圖的圖形表示圖的圖形表示。 2022-4-62022-4-6例例9.2.3 9.2.3 設(shè)圖設(shè)圖G = G = 的圖形如下圖所示，試寫出的圖形如下圖所示，試寫出G G的集的集合表示。合表示。 1 12 23 34 45 5分析分析 將所有將所有小圓圈小圓圈的記號構(gòu)成的記號構(gòu)成結(jié)點(diǎn)集合結(jié)點(diǎn)集合，將連接結(jié)，將連接結(jié)點(diǎn)對的點(diǎn)對的直線或曲線直線或曲線用用圓括號圓括號括起該結(jié)點(diǎn)對表示括起該結(jié)點(diǎn)對表示無向邊無向邊，將連接結(jié)點(diǎn)對的將連接結(jié)點(diǎn)對的有向直線或曲線有向直線或曲線用用尖括號尖括號括起該結(jié)點(diǎn)括起該結(jié)點(diǎn)對表示對表示有向邊

7、有向邊，這里箭頭指向的結(jié)點(diǎn)放在后面。，這里箭頭指向的結(jié)點(diǎn)放在后面。 解解 圖圖G G的集合表示為的集合表示為G = = 1, 2, 3, 4, G = = 1, 2, 3, 4, 55，(1, 4)(1, 4)，(1, 5)(1, 5)，(2, 3)(2, 3)，3, 5，。 2022-4-62022-4-6圖的矩陣表示圖的矩陣表示定義定義9.2.29.2.2：設(shè)圖：設(shè)圖G = G = ，其中，其中V = vV = v1 1, , v v2 2, , , v, vn n ，并假定結(jié)點(diǎn)已經(jīng)有了從，并假定結(jié)點(diǎn)已經(jīng)有了從v v1 1到到v vn n的的次序次序，則則n n階方陣階方陣A AG G =

8、 (a = (aijij) )nxnnxn稱為稱為G G的的鄰接矩陣鄰接矩陣(Adjacency Matrix)(Adjacency Matrix)，其中，其中n n, ,1,2,3,1,2,3,j ji,i,否則否則0，0，E Ev v, ,v vE或E或) )v v, ,若(v若(v1，1，a aj ji ij ji iijij 2022-4-62022-4-6例例9.2.49.2.4試寫出下圖所示圖試寫出下圖所示圖G G的鄰接矩陣。的鄰接矩陣。 v v1 1v v2 2v v5 5v v4 4v v3 3v v6 6分析分析 首先將圖中的首先將圖中的6 6個結(jié)點(diǎn)排序，個結(jié)點(diǎn)排序，若第若第

9、i i行前的結(jié)點(diǎn)到第行前的結(jié)點(diǎn)到第j j列前的結(jié)點(diǎn)列前的結(jié)點(diǎn)有邊相連，則在鄰接矩陣的第有邊相連，則在鄰接矩陣的第i i行第行第j j列元素為列元素為1 1，否則為，否則為0 0。 011101101001110100101110000101110010AG解解 若結(jié)點(diǎn)排序?yàn)槿艚Y(jié)點(diǎn)排序?yàn)関 v1 1v v2 2v v3 3v v4 4v v5 5v v6 6，則，則其鄰接矩陣其鄰接矩陣2022-4-62022-4-6說明說明 圖圖G = G = 的鄰接矩陣依賴于的鄰接矩陣依賴于V V中元素的次序。中元素的次序。 G G的任何一個鄰接矩陣可以從的任何一個鄰接矩陣可以從G G的另一鄰接矩陣的另一鄰接

10、矩陣中通過交換某些行和相應(yīng)的列而得到，中通過交換某些行和相應(yīng)的列而得到， 只選只選V V中元素的任一種次序所得出的鄰接矩陣，中元素的任一種次序所得出的鄰接矩陣，作為圖作為圖G G的鄰接矩陣。的鄰接矩陣。 2022-4-62022-4-69.2.3 9.2.3 圖的操作圖的操作 定義定義9.2.39.2.3 設(shè)圖設(shè)圖G = G = 。1.1. 設(shè)設(shè)eEeE，用，用G-eG-e表示從表示從G G中去掉邊中去掉邊e e得到的圖，稱得到的圖，稱為為刪除邊刪除邊e e。又設(shè)。又設(shè)E EE E，用，用G-EG-E 表示從表示從G G中刪除中刪除E E 中所有邊得到的圖，稱為中所有邊得到的圖，稱為刪除刪除E

11、 E 。2.2. 設(shè)設(shè)vVvV，用，用G-vG-v表示從表示從G G中去掉結(jié)點(diǎn)中去掉結(jié)點(diǎn)v v及及v v關(guān)聯(lián)的關(guān)聯(lián)的所有邊得到的圖，稱為所有邊得到的圖，稱為刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)v v。又設(shè)。又設(shè)V VV V，用用G-VG-V 表示從表示從G G中刪除中刪除V V 中所有結(jié)點(diǎn)及關(guān)聯(lián)的所中所有結(jié)點(diǎn)及關(guān)聯(lián)的所有邊得到的圖，稱為有邊得到的圖，稱為刪除刪除V V 。2022-4-62022-4-6定義定義9.2.39.2.3（續(xù)）（續(xù)）3.3. 設(shè)設(shè)e = (u, v)Ee = (u, v)E，用，用GeGe表示從表示從G G中刪除中刪除e e，將，將e e的兩個端點(diǎn)的兩個端點(diǎn)u, vu, v用一個新的結(jié)點(diǎn)

12、用一個新的結(jié)點(diǎn)w w代替，使代替，使w w關(guān)關(guān)聯(lián)除聯(lián)除e e外的外的u u和和v v關(guān)聯(lián)的一切邊，稱為關(guān)聯(lián)的一切邊，稱為邊邊e e的收縮的收縮。一個圖一個圖G G可以收縮為圖可以收縮為圖H H，是指，是指H H可以從可以從G G經(jīng)過若經(jīng)過若干次邊的收縮而得到。干次邊的收縮而得到。4.4. 設(shè)設(shè)u, vV(u, vu, vV(u, v可能相鄰，也可能不相鄰可能相鄰，也可能不相鄰) )，用，用G(u, v)G(u, v)表示在表示在u, vu, v之間加一條邊之間加一條邊(u, v)(u, v)，稱，稱為為加新邊加新邊。2022-4-62022-4-69.2.4 9.2.4 鄰接點(diǎn)與鄰接邊鄰接點(diǎn)與

13、鄰接邊 定義定義9.2.49.2.4 在圖在圖G = G = 中，若兩個結(jié)點(diǎn)中，若兩個結(jié)點(diǎn)v vi i和和v vj j是邊是邊e e的的端點(diǎn)端點(diǎn)，則稱，則稱v vi i與與v vj j互為互為鄰接點(diǎn)鄰接點(diǎn)(Adjacent (Adjacent Point)Point)，否則，否則v vi i與與v vj j稱為稱為不鄰接的不鄰接的； 具有具有公共結(jié)公共結(jié)點(diǎn)點(diǎn)的兩條邊稱為的兩條邊稱為鄰接邊鄰接邊(Adjacent Edge)(Adjacent Edge)； 兩個兩個端端點(diǎn)相同點(diǎn)相同的邊稱為的邊稱為環(huán)環(huán)(Ring)(Ring)或或自回路自回路(Self-Loop)(Self-Loop)； 圖圖中中

14、不與任何結(jié)點(diǎn)相鄰接不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱為的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)；孤立結(jié)點(diǎn)； 僅由僅由孤立結(jié)點(diǎn)組成的圖稱為孤立結(jié)點(diǎn)組成的圖稱為零圖零圖(Null Graph)(Null Graph)； 僅含僅含一個結(jié)點(diǎn)的零圖稱為一個結(jié)點(diǎn)的零圖稱為平凡圖平凡圖(Trivial Graph)(Trivial Graph)； 含有含有n n個結(jié)點(diǎn)，個結(jié)點(diǎn)，m m條邊的圖，稱為條邊的圖，稱為(n, m)(n, m)圖圖。2022-4-62022-4-6例例9.2.59.2.5試寫出下圖所示圖試寫出下圖所示圖G G的所有結(jié)點(diǎn)的鄰接點(diǎn)、所有邊的所有結(jié)點(diǎn)的鄰接點(diǎn)、所有邊的鄰接邊，并指出所有的孤立結(jié)點(diǎn)和環(huán)。的鄰接邊，并指出所

15、有的孤立結(jié)點(diǎn)和環(huán)。 v v3 3e e1 1e e2 2e e3 3e e5 5v v2 2v v1 1v v5 5e e4 4v v4 4e e6 6e e7 7v v6 62022-4-62022-4-6例例9.2.5 9.2.5 解解結(jié)結(jié)點(diǎn)點(diǎn)鄰接點(diǎn)鄰接點(diǎn)是否孤是否孤立結(jié)點(diǎn)立結(jié)點(diǎn)邊邊鄰接邊鄰接邊是否環(huán)是否環(huán)e e1 1e e1 1,e,e2 2,e,e3 3,e,e4 4,e,e5 5,e,e6 6否否v v1 1v v1 1,v,v2 2,v,v3 3,v,v4 4否否e e2 2e e1 1,e,e2 2,e,e3 3,e,e6 6否否v v2 2v v1 1,v,v3 3否否e e3

16、 3e e1 1,e,e2 2,e,e3 3,e,e6 6是是v v3 3v v1 1,v,v2 2否否e e4 4e e1 1,e,e4 4,e,e5 5,e,e6 6否否v v4 4v v1 1否否e e5 5e e1 1,e,e4 4,e,e5 5,e,e6 6否否v v5 5是是e e6 6e e1 1,e,e2 2,e,e3 3,e,e4 4,e,e5 5,e,e6 6否否v v6 6v v6 6否否e e7 7e e7 7是是圖圖G G既不是平凡圖，也不是零圖，而是一個既不是平凡圖，也不是零圖，而是一個(6, 7)(6, 7)圖。圖。v v3 3e e1 1e e2 2e e3 3

17、e e5 5v v2 2v v1 1v v5 5e e4 4v v4 4e e6 6e e7 7v v6 62022-4-62022-4-69.2.5 9.2.5 圖的分類圖的分類 1. 1. 按邊有無方向分類按邊有無方向分類每條邊都是每條邊都是無向邊無向邊的圖稱為的圖稱為無向圖無向圖(Undirected (Undirected Graph)Graph)；每條邊都是每條邊都是有向邊有向邊的圖稱為的圖稱為有向圖有向圖(Directed (Directed Graph)Graph)；有些邊是有些邊是無向邊無向邊，而另一些邊是，而另一些邊是有向邊有向邊的圖稱為的圖稱為混混合圖合圖(Mixed Gr

18、aph)(Mixed Graph)。 第第6 6章的關(guān)系圖都是有向圖，這時鄰接矩陣就是章的關(guān)系圖都是有向圖，這時鄰接矩陣就是關(guān)系矩陣。關(guān)系矩陣。2022-4-62022-4-6例例9.2.69.2.6試判斷下圖所示的三個圖是無向圖、有向圖，還是試判斷下圖所示的三個圖是無向圖、有向圖，還是混合圖？混合圖？v v3 3G G1 1v v2 2v v1 1v v3 3G G2 2v v2 2v v1 1v v3 3G G3 3v v2 2v v1 1解解 G G1 1為無向圖，為無向圖，G G2 2為有向圖，為有向圖，G G3 3為混合圖。為混合圖。2022-4-62022-4-6說明說明 我們僅討

19、論無向圖和有向圖，至于混合圖，我我們僅討論無向圖和有向圖，至于混合圖，我們可將其中的無向邊看成方向相反的兩條有向邊，們可將其中的無向邊看成方向相反的兩條有向邊，從而轉(zhuǎn)化為有向圖來研究。例如可將圖從而轉(zhuǎn)化為有向圖來研究。例如可將圖G G3 3轉(zhuǎn)化為下轉(zhuǎn)化為下圖。圖。 v v3 3G G3 3v v2 2v v1 12022-4-62022-4-62. 2. 按有無平行邊分類按有無平行邊分類 定義定義9.2.69.2.6 在有向圖中，兩結(jié)點(diǎn)間在有向圖中，兩結(jié)點(diǎn)間( (包括結(jié)點(diǎn)自身包括結(jié)點(diǎn)自身間間) )若有若有同始點(diǎn)和同終點(diǎn)同始點(diǎn)和同終點(diǎn)的幾條邊，則這幾條邊稱的幾條邊，則這幾條邊稱為為平行邊平行邊；

20、在無向圖中，兩結(jié)點(diǎn)間；在無向圖中，兩結(jié)點(diǎn)間( (包括結(jié)點(diǎn)自身包括結(jié)點(diǎn)自身間間) )若有幾條邊，則這幾條邊稱為若有幾條邊，則這幾條邊稱為平行邊平行邊。兩結(jié)點(diǎn)兩結(jié)點(diǎn)a a、b b間相互間相互平行的邊的條數(shù)平行的邊的條數(shù)稱為邊稱為邊(a, b)(a, b)或或的的重?cái)?shù)重?cái)?shù)。含有平行邊的圖稱為含有平行邊的圖稱為多重圖多重圖；非多重圖稱為；非多重圖稱為線圖線圖；無環(huán)的線圖稱為無環(huán)的線圖稱為簡單圖簡單圖。 2022-4-62022-4-6例例9.2.79.2.7試判斷下圖所示的試判斷下圖所示的4 4個圖是多重圖、線圖，還是簡個圖是多重圖、線圖，還是簡單圖？并指出多重圖中所有平行邊的重?cái)?shù)。單圖？并指出多重圖

21、中所有平行邊的重?cái)?shù)。 v v3 3G G1 1v v2 2v v1 1v v4 4a aG G2 2b bc c1 1G G3 32 23 3G G4 4分析分析 多重圖和線圖，僅僅看有無平行邊；簡單圖是一種特殊多重圖和線圖，僅僅看有無平行邊；簡單圖是一種特殊的線圖，僅僅無環(huán)而已。兩個端點(diǎn)都相同的無向邊是平行邊，的線圖，僅僅無環(huán)而已。兩個端點(diǎn)都相同的無向邊是平行邊，但兩個端點(diǎn)都相同的有向邊不一定是平行邊，例如但兩個端點(diǎn)都相同的有向邊不一定是平行邊，例如G G2 2中的中的和和就不是平行邊，因此就不是平行邊，因此的重?cái)?shù)是的重?cái)?shù)是3 3，而不是，而不是4 4。 解解 G G1 1、G G2 2是多

22、重圖，是多重圖，G G3 3是線圖，是線圖，G G4 4是簡單圖。是簡單圖。G G1 1中平中平行邊行邊(v(v1 1, v, v1 1) )的重?cái)?shù)為的重?cái)?shù)為2 2，(v(v1 1, v, v3 3) )的重?cái)?shù)為的重?cái)?shù)為2 2，(v(v2 2, v, v4 4) )的重?cái)?shù)為的重?cái)?shù)為3 3；G G2 2中平行邊中平行邊的重?cái)?shù)為的重?cái)?shù)為3 3，的的重?cái)?shù)為重?cái)?shù)為2 2。2022-4-62022-4-63. 3. 按邊或結(jié)點(diǎn)是否含權(quán)分類按邊或結(jié)點(diǎn)是否含權(quán)分類 定義定義9.2.79.2.7 賦權(quán)圖賦權(quán)圖(Weight Graph)G(Weight Graph)G是一個是一個三重三重組組或或四重組四重組，

23、其中，其中V V是結(jié)是結(jié)點(diǎn)集合，點(diǎn)集合，E E是邊的集合，是邊的集合，f f是從是從V V到非負(fù)實(shí)數(shù)集合的到非負(fù)實(shí)數(shù)集合的函數(shù)函數(shù)，g g是從是從E E到非負(fù)實(shí)數(shù)集合的到非負(fù)實(shí)數(shù)集合的函數(shù)函數(shù)。2022-4-62022-4-6例例9.2.89.2.8下圖所示的圖哪個是賦權(quán)圖，哪個是無權(quán)圖？是賦下圖所示的圖哪個是賦權(quán)圖，哪個是無權(quán)圖？是賦權(quán)圖的請寫出相應(yīng)的函數(shù)。權(quán)圖的請寫出相應(yīng)的函數(shù)。 v v4 4v v1 1v v2 2v v3 3G G3 3v v3 3G G1 1v v2 2v v1 1v v4 45 56 67 76 68 88 810106 69 9c c7 7a ab bd d505

24、0404070703535G G2 24545G1G1、G2G2是賦權(quán)圖，是賦權(quán)圖，G3G3不是賦權(quán)圖。記圖不是賦權(quán)圖。記圖G1=G1=和和G2=G2=，其，其中：中：g1()=5g1()=5，g1()=6g1()=6. .2022-4-62022-4-69.2.6 9.2.6 子圖與補(bǔ)圖子圖與補(bǔ)圖 定義定義9.2.89.2.8 設(shè)有圖設(shè)有圖G = G = 和圖和圖G G1 1 = V = 。1.1. 若若V V1 1 V V，E E1 1 E E，則稱，則稱G G1 1是是G G的的子圖子圖(Subgraph)(Subgraph)，記為，記為G G1 1 G G。2.2. 若若G G1 1

25、G G，且，且G G1 1G(G(即即V V1 1 V V或或E E1 1 E) E)，則稱，則稱G G1 1是是G G的的真子真子圖圖(Proper Subgraph)(Proper Subgraph)，記為，記為G G1 1 G G。3.3. 若若V V1 1 = V = V，E E1 1 E E，則稱，則稱G G1 1是是G G的的生成子圖生成子圖(Spanning (Spanning Subgraph)Subgraph)。4.4. 設(shè)設(shè)V V2 2 V V且且V V2 2 ，以，以V V2 2為結(jié)點(diǎn)集，為結(jié)點(diǎn)集，以兩個端點(diǎn)均在以兩個端點(diǎn)均在V V2 2中中的邊的全體為邊集的的邊的全體為

26、邊集的G G的子圖的子圖，稱為，稱為V V2 2導(dǎo)出的導(dǎo)出的G G的子圖，的子圖，簡稱簡稱V V2 2的的導(dǎo)出子圖導(dǎo)出子圖(Induced Subgraph)(Induced Subgraph)。 2022-4-62022-4-6例例9.2.99.2.9判斷下圖中，圖判斷下圖中，圖G G1 1、G G2 2和和G G3 3是否是圖是否是圖G G的子圖、真子的子圖、真子圖、生成子圖、導(dǎo)出子圖？圖、生成子圖、導(dǎo)出子圖？v v1 1v v2 2v v3 3v v4 4v v5 5G Gv v1 1v v2 2v v3 3v v4 4G G1 1v v1 1v v2 2v v3 3v v4 4v v5

27、 5G G2 2v v1 1v v2 2v v3 3v v4 4G G3 3解解 G G1 1、G G2 2和和G G3 3都是圖都是圖G G的子圖、真子圖；的子圖、真子圖；G G2 2是圖是圖G G的生成子圖；的生成子圖；G G1 1是圖是圖G G的的vv1 1, v, v2 2, v, v3 3, v, v4 4 的導(dǎo)出子的導(dǎo)出子圖。圖。2022-4-62022-4-6定義定義9.2.99.2.9 設(shè)設(shè)G = G = 為一個具有為一個具有n n個結(jié)點(diǎn)的個結(jié)點(diǎn)的無向簡單無向簡單圖圖，如果，如果G G中中任意兩個結(jié)點(diǎn)間都有邊相連任意兩個結(jié)點(diǎn)間都有邊相連，則稱，則稱G G為為無向完全圖無向完全圖

28、，簡稱，簡稱G G為為完全圖完全圖，記為，記為K Kn n。 設(shè)設(shè)G = G = 為一個具有為一個具有n n個結(jié)點(diǎn)的個結(jié)點(diǎn)的有向簡單有向簡單圖圖，如果，如果G G中中任意兩個結(jié)點(diǎn)間都有兩條方向相反的任意兩個結(jié)點(diǎn)間都有兩條方向相反的有向邊相連有向邊相連，則稱，則稱G G為為有向完全圖有向完全圖，在不發(fā)生誤解，在不發(fā)生誤解的情況下，也記為的情況下，也記為K Kn n。 對于完全圖來說，其對于完全圖來說，其鄰接矩陣鄰接矩陣除主對角元為除主對角元為0 0外，其它元素均為外，其它元素均為1 1。 2022-4-62022-4-6例例K K3 3K K4 4K K3 3K K5 5無向完全圖無向完全圖K

29、Kn n的邊數(shù)為的邊數(shù)為有向完全圖有向完全圖K Kn n的邊數(shù)為的邊數(shù)為1)1)n(nn(n2 21 1C(n,2)C(n,2) 1)1)n(nn(nP(n,2)P(n,2) 2022-4-62022-4-6定義定義9.2.109.2.10設(shè)設(shè)G = G = 為簡單圖，為簡單圖，G G = V, E = 為完全圖，為完全圖，則稱則稱G G1 1 = V, E = -E為為G G的的補(bǔ)圖補(bǔ)圖，記為，記為 。注注 在定義在定義9.2.109.2.10中，當(dāng)中，當(dāng)G G為有向圖時，則為有向圖時，則G G為有為有向完全圖；當(dāng)向完全圖；當(dāng)G G為無向圖時，則為無向圖時，則G G為無向完全圖。為無向完全圖

30、。G G的補(bǔ)圖也可理解為從結(jié)點(diǎn)集的補(bǔ)圖也可理解為從結(jié)點(diǎn)集V V的完全圖中刪除的完全圖中刪除G G中中的邊剩下的圖，即的邊剩下的圖，即G G與其補(bǔ)圖的結(jié)點(diǎn)集是相同的，與其補(bǔ)圖的結(jié)點(diǎn)集是相同的，邊集是相對于完全圖的邊集為全集的補(bǔ)集。邊集是相對于完全圖的邊集為全集的補(bǔ)集。顯然，若顯然，若G G1 1= = ，則，則G= G= ，即它們互為補(bǔ)圖。，即它們互為補(bǔ)圖。K Kn n的補(bǔ)圖為的補(bǔ)圖為n n個結(jié)點(diǎn)的零圖。個結(jié)點(diǎn)的零圖。 G GG G1 1G G2022-4-62022-4-6例例9.2.109.2.10求下圖中圖求下圖中圖(a)(a)、(b)(b)、(c)(c)的補(bǔ)圖。的補(bǔ)圖。(a)(a)(b)

31、(b)(c)(c)分析分析 互為補(bǔ)圖的兩個圖的結(jié)點(diǎn)集相同，邊集是相互為補(bǔ)圖的兩個圖的結(jié)點(diǎn)集相同，邊集是相對于完全圖的邊集為全集的補(bǔ)集。具體做的時候，對于完全圖的邊集為全集的補(bǔ)集。具體做的時候，可先補(bǔ)充一些邊使其變?yōu)橥耆珗D，然后再刪除原來可先補(bǔ)充一些邊使其變?yōu)橥耆珗D，然后再刪除原來圖中的邊得到。圖中的邊得到。 解解 上圖中圖上圖中圖(a)(a)、(b)(b)、(c)(c)的補(bǔ)圖分別為圖下中的補(bǔ)圖分別為圖下中圖圖(a)(a)、(b)(b)、(c)(c)。 (a)(a)(b)(b)(c)(c)注意，注意，孤孤立結(jié)點(diǎn)一立結(jié)點(diǎn)一定不要漏定不要漏了，否則了，否則結(jié)點(diǎn)集就結(jié)點(diǎn)集就不同。不同。2022-4-6

32、2022-4-6利用鄰接矩陣描述補(bǔ)圖利用鄰接矩陣描述補(bǔ)圖 若設(shè)簡單圖若設(shè)簡單圖G G的鄰接矩陣的鄰接矩陣A = (aA = (aijij) )n nn n，則它的，則它的補(bǔ)圖補(bǔ)圖 的鄰接矩陣的鄰接矩陣 有：有：G Gn n, ,1 1, ,2 2, ,3 3, ,j ji i, ,j ji i0 0，j ji i，a a1 1a ai ij ji ij jn nn ni ij j) )a a( (A A2022-4-62022-4-6例例9.2.119.2.11證明：在任意證明：在任意6 6個人的集會上，總會有個人的集會上，總會有3 3個人相互認(rèn)個人相互認(rèn)識或者有識或者有3 3個人互相不認(rèn)識（

33、假設(shè)認(rèn)識是相互的）。個人互相不認(rèn)識（假設(shè)認(rèn)識是相互的）。 分析分析 把把6 6個人作為結(jié)點(diǎn)，相互認(rèn)識的人之間連邊，個人作為結(jié)點(diǎn)，相互認(rèn)識的人之間連邊，這個問題就轉(zhuǎn)化圖的問題?？梢岳脠D及其補(bǔ)圖來這個問題就轉(zhuǎn)化圖的問題?？梢岳脠D及其補(bǔ)圖來解這個問題。解這個問題。2022-4-62022-4-6證明證明 把參加集會的人作為結(jié)點(diǎn)，相互認(rèn)識的人之間連把參加集會的人作為結(jié)點(diǎn)，相互認(rèn)識的人之間連邊，得到圖邊，得到圖G G，設(shè)為，設(shè)為G G的補(bǔ)圖，這樣問題就轉(zhuǎn)化為證明的補(bǔ)圖，這樣問題就轉(zhuǎn)化為證明G G或中至少有一個完全子圖或中至少有一個完全子圖K K3 3。 考慮完全圖考慮完全圖K K6 6，結(jié)點(diǎn)，結(jié)點(diǎn)v

34、 v1 1與其余與其余5 5個結(jié)點(diǎn)各有一條邊個結(jié)點(diǎn)各有一條邊相連，這相連，這5 5條邊一定有條邊一定有3 3條在條在G G或或 中，不妨設(shè)有中，不妨設(shè)有3 3條邊條邊在在G G中，設(shè)這中，設(shè)這3 3條邊為條邊為(v(v1 1, v, v2 2) )、(v(v1 1, v, v3 3) )、(v(v1 1, v, v4 4) )。 考慮結(jié)點(diǎn)考慮結(jié)點(diǎn)v v2 2, v, v3 3, v, v4 4。若。若v v2 2, v, v3 3, v, v4 4在在G G中無邊相連，中無邊相連，則則v v2 2, v, v3 3, v, v4 4相互不認(rèn)識；若相互不認(rèn)識；若v v2 2, v, v3 3,

35、v, v4 4在在G G中至少有一中至少有一條邊相連，例如條邊相連，例如(v(v2 2, v, v3 3) )，則，則v v1 1, v, v2 2, v, v3 3就相互認(rèn)識。就相互認(rèn)識。因此，總有因此，總有3 3個人相互認(rèn)識或者有個人相互認(rèn)識或者有3 3個人互不認(rèn)識。個人互不認(rèn)識。G G2022-4-62022-4-69.2.7 9.2.7 結(jié)點(diǎn)的度數(shù)與握手定理結(jié)點(diǎn)的度數(shù)與握手定理定義定義9.2.119.2.11 （1 1）圖）圖G = G = 中以結(jié)點(diǎn)中以結(jié)點(diǎn)v vV V為為端點(diǎn)的邊數(shù)端點(diǎn)的邊數(shù)( (有環(huán)時計(jì)算兩次有環(huán)時計(jì)算兩次) )稱為結(jié)點(diǎn)稱為結(jié)點(diǎn)v v的的度數(shù)度數(shù)(Degree)(D

36、egree)，簡稱，簡稱度度，記為，記為deg(v)deg(v)。（2 2）有向圖）有向圖G = G = 中以結(jié)點(diǎn)中以結(jié)點(diǎn)v v為為始點(diǎn)的邊數(shù)始點(diǎn)的邊數(shù)稱稱為為v v的的出度出度(Out-Degree)(Out-Degree)，記為，記為degdeg+ +(v)(v)；以結(jié)點(diǎn)；以結(jié)點(diǎn)v v為為終點(diǎn)的邊數(shù)終點(diǎn)的邊數(shù)稱為稱為v v的的入度入度(In-Degree)(In-Degree)，記為，記為degdeg- -(v)(v)。顯然，。顯然，deg(v) = degdeg(v) = deg+ +(v)+deg(v)+deg- -(v)(v)。（3 3）對于圖）對于圖G = G = ，度數(shù)為度數(shù)為1

37、 1的結(jié)點(diǎn)稱為的結(jié)點(diǎn)稱為懸掛懸掛結(jié)點(diǎn)結(jié)點(diǎn)，以懸掛結(jié)點(diǎn)為端點(diǎn)的邊稱為，以懸掛結(jié)點(diǎn)為端點(diǎn)的邊稱為懸掛邊懸掛邊。 2022-4-62022-4-6利用鄰接矩陣描述利用鄰接矩陣描述 設(shè)圖設(shè)圖G = G = ，V = vV = v1 1, v, v2 2, , , v, vn n 的鄰接矩的鄰接矩陣為陣為nnnnn2n2n1n12n2n222221211n1n12121111a a.a aa a.a a.a aa aa a.a aa aA A若若G G是無向圖，則是無向圖，則A A中第中第i i行元素是由結(jié)點(diǎn)行元素是由結(jié)點(diǎn)v vi i所關(guān)聯(lián)的所關(guān)聯(lián)的邊所決定，其中為邊所決定，其中為1 1的元素?cái)?shù)目等于的

38、元素?cái)?shù)目等于v vi i的度數(shù)，即，的度數(shù)，即，i ii in n1 1k ki ik ki ia aa a) )d de eg g( (v vi ii in n1 1k kk ki ii ia aa a) )d de eg g( (v v2022-4-62022-4-6利用鄰接矩陣描述利用鄰接矩陣描述若若G G是有向圖，則是有向圖，則A A中第中第i i行元素是由結(jié)點(diǎn)行元素是由結(jié)點(diǎn)v vi i為始點(diǎn)為始點(diǎn)的邊所決定，其中為的邊所決定，其中為1 1的元素?cái)?shù)目等于的元素?cái)?shù)目等于v vi i的出度，的出度，即即A A中第中第i i列元素是由結(jié)點(diǎn)列元素是由結(jié)點(diǎn)v vi i為終點(diǎn)的邊所決定，其中為終點(diǎn)

39、的邊所決定，其中為為1 1的元素?cái)?shù)目等于的元素?cái)?shù)目等于v vi i的入度，即。的入度，即。n n1 1k kikiki ia a) )(v(vdegdegn n1 1k kkikii ia a) )(v(vdegdeg2022-4-62022-4-6例例9.2.129.2.12求右圖中所有結(jié)點(diǎn)的度數(shù)、出度和求右圖中所有結(jié)點(diǎn)的度數(shù)、出度和入度，指出懸掛結(jié)點(diǎn)和為懸掛邊。入度，指出懸掛結(jié)點(diǎn)和為懸掛邊。v v1 1v v2 2v v3 3v v4 4v v5 5分析分析 求結(jié)點(diǎn)的度數(shù)非常簡單，只需要數(shù)一下以該求結(jié)點(diǎn)的度數(shù)非常簡單，只需要數(shù)一下以該結(jié)點(diǎn)為端點(diǎn)的邊數(shù)，出度只需要數(shù)一下以其為始點(diǎn)結(jié)點(diǎn)為端點(diǎn)的

40、邊數(shù)，出度只需要數(shù)一下以其為始點(diǎn)的邊數(shù)，入度只需要數(shù)一下以其為終點(diǎn)的邊數(shù)，無的邊數(shù)，入度只需要數(shù)一下以其為終點(diǎn)的邊數(shù)，無向環(huán)算向環(huán)算2 2度，又向環(huán)出度和入度各算度，又向環(huán)出度和入度各算1 1度。只有度數(shù)度。只有度數(shù)為為1 1的才是懸掛結(jié)點(diǎn)，以懸掛結(jié)點(diǎn)為端點(diǎn)的邊才是懸的才是懸掛結(jié)點(diǎn)，以懸掛結(jié)點(diǎn)為端點(diǎn)的邊才是懸掛邊。掛邊。解解 deg(vdeg(v1 1) = 1) = 1，degdeg+ +(v(v1 1) = 0) = 0，degdeg- -(v(v1 1) = 1) = 1deg(vdeg(v2 2) = 4) = 4，degdeg+ +(v(v2 2) = 3) = 3，degdeg-

41、-(v(v2 2) = 1) = 1deg(vdeg(v3 3) = 3) = 3，degdeg+ +(v(v3 3) = 1) = 1，degdeg- -(v(v3 3) = 2) = 2deg(vdeg(v4 4) = 4) = 4，degdeg+ +(v(v4 4) = 2) = 2，degdeg- -(v(v4 4) = 2) = 2deg(vdeg(v5 5) = deg) = deg+(+(v v5 5) = deg) = deg- -(v(v5 5) = 0) = 0v v1 1為懸掛結(jié)點(diǎn)，為懸掛結(jié)點(diǎn)，v 為懸掛邊。為懸掛邊。 2022-4-62022-4-6定理定理9.2.1(

42、9.2.1(握手定理握手定理) )圖中結(jié)點(diǎn)度數(shù)的總和等于邊數(shù)的二倍圖中結(jié)點(diǎn)度數(shù)的總和等于邊數(shù)的二倍，即設(shè)圖，即設(shè)圖G = G = ，則有，則有 E E2 2deg(v)deg(v)V Vv v分析分析 由定義由定義9.2.119.2.11，結(jié)點(diǎn)，結(jié)點(diǎn)v v的度數(shù)等于以的度數(shù)等于以v v為端點(diǎn)為端點(diǎn)的邊數(shù)，而的邊數(shù)，而1 1條邊有條邊有2 2個端點(diǎn)個端點(diǎn)( (環(huán)的環(huán)的2 2個端點(diǎn)相同個端點(diǎn)相同) )，因此因此1 1條邊貢獻(xiàn)條邊貢獻(xiàn)2 2度。度。證明證明 因?yàn)槊織l邊都有兩個端點(diǎn)因?yàn)槊織l邊都有兩個端點(diǎn)( (環(huán)的兩個端點(diǎn)相環(huán)的兩個端點(diǎn)相同同) )，所以加上一條邊就使得各結(jié)點(diǎn)的度數(shù)之和增，所以加上一條邊

43、就使得各結(jié)點(diǎn)的度數(shù)之和增加加2 2，因此結(jié)論成立。，因此結(jié)論成立。 這個結(jié)果是圖論的第一個定理，它是由這個結(jié)果是圖論的第一個定理，它是由歐拉歐拉于于17361736年年最先給出的。歐拉曾對此定理給出了這樣一最先給出的。歐拉曾對此定理給出了這樣一個形象論斷：個形象論斷：如果許多人在見面時握了手，兩只手如果許多人在見面時握了手，兩只手握在一起，被握過手的總次數(shù)為偶數(shù)握在一起，被握過手的總次數(shù)為偶數(shù)。故此定理稱。故此定理稱為為圖論的基本定理圖論的基本定理或或握手定理握手定理。2022-4-62022-4-6推論推論9.2.19.2.1 圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)個數(shù)為偶數(shù)。圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)個數(shù)為偶數(shù)。

44、分析分析 考慮考慮2|E|2|E|為偶數(shù)，奇數(shù)個奇數(shù)之和為奇數(shù)，為偶數(shù)，奇數(shù)個奇數(shù)之和為奇數(shù)，偶數(shù)個奇數(shù)之和為偶數(shù)。偶數(shù)個奇數(shù)之和為偶數(shù)。 今后常稱今后常稱度數(shù)為奇數(shù)的結(jié)點(diǎn)度數(shù)為奇數(shù)的結(jié)點(diǎn)為為奇度數(shù)結(jié)點(diǎn)奇度數(shù)結(jié)點(diǎn)(Odd (Odd Degree Point)Degree Point)，度數(shù)為偶數(shù)的結(jié)點(diǎn)度數(shù)為偶數(shù)的結(jié)點(diǎn)為為偶度數(shù)結(jié)點(diǎn)偶度數(shù)結(jié)點(diǎn)(Even Degree Point)(Even Degree Point)。 2022-4-62022-4-6定理定理9.2.29.2.2有向圖中各結(jié)點(diǎn)的出度之和等于各結(jié)點(diǎn)的入度之和，有向圖中各結(jié)點(diǎn)的出度之和等于各結(jié)點(diǎn)的入度之和，等于邊數(shù)，即設(shè)有向圖等于邊

45、數(shù)，即設(shè)有向圖G = G = ，則有，則有 E E( (v v) )d de eg g( (v v) )d de eg gV Vv vV Vv v分析分析 利用握手定理，考慮一條邊貢獻(xiàn)一個出度和利用握手定理，考慮一條邊貢獻(xiàn)一個出度和一個入度即可。一個入度即可。2022-4-62022-4-6定義定義9.2.129.2.12設(shè)設(shè)V = vV = v1 1, v, v2 2, , , v, vn n 為圖為圖G G的結(jié)點(diǎn)集，稱的結(jié)點(diǎn)集，稱(deg(v(deg(v1 1), deg(v), deg(v2 2), ), , deg(v, deg(vn n)為為G G的的度數(shù)序列度數(shù)序列(Degree

46、Sequence)(Degree Sequence)。 v v1 1v v2 2v v3 3v v4 4v v5 5上圖的度數(shù)序列為上圖的度數(shù)序列為(1, 4, 3, 4, 0)(1, 4, 3, 4, 0)。2022-4-62022-4-6例例9.2.149.2.14（1 1）(3, 5, 1, 4)(3, 5, 1, 4)，(1, 2, 3, 4, 5)(1, 2, 3, 4, 5)能成為圖能成為圖的度數(shù)序列嗎？為什么？的度數(shù)序列嗎？為什么？解解 （1 1）由于這兩個序列中，奇數(shù)的個數(shù)均為）由于這兩個序列中，奇數(shù)的個數(shù)均為奇數(shù)，由推論奇數(shù)，由推論9.2.19.2.1知，它們都不能成為圖的度

47、知，它們都不能成為圖的度數(shù)序列。數(shù)序列。分析分析 這是一個利用握手定理及其推論的例子。度這是一個利用握手定理及其推論的例子。度數(shù)序列中的每個元素都是一個結(jié)點(diǎn)的度數(shù)，利用推數(shù)序列中的每個元素都是一個結(jié)點(diǎn)的度數(shù)，利用推論論9.2.19.2.1，一定有偶數(shù)各奇數(shù)。，一定有偶數(shù)各奇數(shù)。2022-4-62022-4-69.2.8 9.2.8 圖的同構(gòu)圖的同構(gòu) 圖是表達(dá)事物之間關(guān)系的工具，因此，圖的最圖是表達(dá)事物之間關(guān)系的工具，因此，圖的最本質(zhì)的內(nèi)容是結(jié)點(diǎn)和邊的關(guān)聯(lián)關(guān)系。而在實(shí)際畫圖本質(zhì)的內(nèi)容是結(jié)點(diǎn)和邊的關(guān)聯(lián)關(guān)系。而在實(shí)際畫圖時，由于結(jié)點(diǎn)的位置不同，邊的長短曲直不同，同時，由于結(jié)點(diǎn)的位置不同，邊的長短曲直

48、不同，同一事物間的關(guān)系可能畫出不同形狀的圖來。例如下一事物間的關(guān)系可能畫出不同形狀的圖來。例如下圖中的兩個圖圖中的兩個圖G G1 1和和G G2 2實(shí)際上是同一個圖實(shí)際上是同一個圖K K4 4。 G G1 11 12 23 34 4G G2 21 12 23 34 42022-4-62022-4-6定義定義9.2.139.2.13設(shè)兩個圖設(shè)兩個圖G = G = 和和G G= V= ，如果存，如果存在在雙射雙射函數(shù)函數(shù)g g：VVVV，使得對于任意，使得對于任意e=(ve=(vi i,v,vj j),), v)E)E當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)e e = (g(v = (g(vi i), g(v), g(v

49、j j) ) EE，并且，并且e e與與e e的的重?cái)?shù)相同重?cái)?shù)相同，則稱，則稱G G與與G G同構(gòu)同構(gòu)，記為記為GGGG。 對于同構(gòu)，形象地說，若圖的結(jié)點(diǎn)可以任意挪對于同構(gòu)，形象地說，若圖的結(jié)點(diǎn)可以任意挪動位置，而邊是完全彈性的，只要在不拉斷的條件動位置，而邊是完全彈性的，只要在不拉斷的條件下，一個圖可以變形為另一個圖，那么這兩個圖是下，一個圖可以變形為另一個圖，那么這兩個圖是同構(gòu)的。同構(gòu)的。2022-4-62022-4-6兩個圖同構(gòu)的兩個圖同構(gòu)的必要條件必要條件（1 1）結(jié)點(diǎn)數(shù)目相同；）結(jié)點(diǎn)數(shù)目相同； （2 2）邊數(shù)相同；）邊數(shù)相同； （3 3）度數(shù)相同的結(jié)點(diǎn)數(shù)相同。）度數(shù)相同的結(jié)點(diǎn)數(shù)相同。

50、2022-4-62022-4-6例例9.2.149.2.14試證明下圖中，試證明下圖中，GGGG。8 8G G1 12 25 56 6G Gb b3 34 47 7a ac ce eg gd df fh h證明證明 構(gòu)造結(jié)點(diǎn)之間的雙射函數(shù)構(gòu)造結(jié)點(diǎn)之間的雙射函數(shù)f f如下：如下：f(1)=af(1)=a，f(2)=bf(2)=b，f(3)=cf(3)=c，f(4)=df(4)=d，f(5)=ef(5)=e，f(6)=ff(6)=f，f(7)=gf(7)=g，f(8)=hf(8)=h容易驗(yàn)證，容易驗(yàn)證，f f滿足定義滿足定義9.2.139.2.13，所以，所以GGGG。 分析分析 證明兩個圖同構(gòu)，

51、關(guān)鍵是找到滿足要求的結(jié)證明兩個圖同構(gòu)，關(guān)鍵是找到滿足要求的結(jié)點(diǎn)集之間的雙射函數(shù)?，F(xiàn)在還沒有好的辦法，只有點(diǎn)集之間的雙射函數(shù)?，F(xiàn)在還沒有好的辦法，只有憑經(jīng)驗(yàn)去試。憑經(jīng)驗(yàn)去試。2022-4-62022-4-6圖的應(yīng)用：通訊網(wǎng)絡(luò)圖的應(yīng)用：通訊網(wǎng)絡(luò)通訊網(wǎng)絡(luò)中最重要的整體問題之一是網(wǎng)絡(luò)的結(jié)構(gòu)形通訊網(wǎng)絡(luò)中最重要的整體問題之一是網(wǎng)絡(luò)的結(jié)構(gòu)形式。通訊網(wǎng)絡(luò)是一個強(qiáng)連通的有向圖，根據(jù)用途和式。通訊網(wǎng)絡(luò)是一個強(qiáng)連通的有向圖，根據(jù)用途和各種性能指標(biāo)有著不同的結(jié)構(gòu)形式，下圖給出了一各種性能指標(biāo)有著不同的結(jié)構(gòu)形式，下圖給出了一些典型的結(jié)構(gòu)。些典型的結(jié)構(gòu)。 (a)(a)(b)(b)(c)(c)(d)(d)(e)(e)在實(shí)際

52、應(yīng)用中，根據(jù)需要還可將上述幾種典型結(jié)構(gòu)在實(shí)際應(yīng)用中，根據(jù)需要還可將上述幾種典型結(jié)構(gòu)組合使用。組合使用。 環(huán)（環(huán)（RingRing）型網(wǎng)絡(luò)型網(wǎng)絡(luò)樹（樹（TreeTree）型網(wǎng)絡(luò)型網(wǎng)絡(luò)星（星（StarStar）型網(wǎng)絡(luò)型網(wǎng)絡(luò)分布式（分布式（DistributivityDistributivity）網(wǎng)絡(luò)網(wǎng)絡(luò)立方體（立方體（CubeCube）型網(wǎng)絡(luò)型網(wǎng)絡(luò)2022-4-62022-4-69.3 9.3 通路、回路與連通性通路、回路與連通性 右圖是中國鐵路交右圖是中國鐵路交通圖的一部分，如果一通圖的一部分，如果一個旅客要從成都乘火車個旅客要從成都乘火車到北京，那么他一定會到北京，那么他一定會經(jīng)過其它車站；而

53、旅客經(jīng)過其它車站；而旅客不可能從成都乘火車到不可能從成都乘火車到達(dá)臺北。這就是我們要達(dá)臺北。這就是我們要研究的連通性。研究的連通性。成都成都昆明昆明重慶重慶廣州廣州長沙長沙武漢武漢上海上海蘭州蘭州西安西安沈陽沈陽北京北京天津天津鄭州鄭州廈門廈門高雄高雄臺北臺北2022-4-62022-4-69.3.1 9.3.1 通路與回路通路與回路 通路與回路是圖論中兩個重要的基本概念。本通路與回路是圖論中兩個重要的基本概念。本小節(jié)所述定義一般來說既適合有向圖，也適合無向小節(jié)所述定義一般來說既適合有向圖，也適合無向圖，否則，將加以說明或分開定義。圖，否則，將加以說明或分開定義。 2022-4-62022-4

54、-6定義定義9.3.1 9.3.1 （續(xù)）（續(xù)）給定圖給定圖G=G=中中結(jié)點(diǎn)和邊結(jié)點(diǎn)和邊相繼交錯出現(xiàn)相繼交錯出現(xiàn)的序列的序列=v=v0 0e e1 1v v1 1e e2 2v v2 2e ek kv vk k。1.1.若若中邊中邊e ei i的兩端點(diǎn)是的兩端點(diǎn)是v vi-1i-1和和v vi i（G G是有向圖時要求是有向圖時要求v vi-1i-1與與v vi i分別是分別是e ei i的始點(diǎn)和終點(diǎn)），的始點(diǎn)和終點(diǎn)），i=1,2,i=1,2,k,k，則，則稱稱為為結(jié)點(diǎn)結(jié)點(diǎn)v v0 0到結(jié)點(diǎn)到結(jié)點(diǎn)v vk k的的通路通路(Entry)(Entry)。2.2.v v0 0和和v vk k分別稱為

55、此通路的分別稱為此通路的始點(diǎn)始點(diǎn)和和終點(diǎn)終點(diǎn)，統(tǒng)稱為通路，統(tǒng)稱為通路的的端點(diǎn)端點(diǎn)。3.3.通路中通路中邊的數(shù)目邊的數(shù)目k k稱為此通路的稱為此通路的長度長度(Length)(Length)。4.4.當(dāng)當(dāng)v v0 0=v=vn n時，此通路稱為時，此通路稱為回路回路(Circuit)(Circuit)。2022-4-62022-4-6定義定義9.3.1 9.3.1 若若通路通路中的中的所有邊互不相同所有邊互不相同，則稱此通路為，則稱此通路為簡單通簡單通路路或一條或一條跡跡；若；若回路回路中的中的所有邊互不相同所有邊互不相同，則稱，則稱此回路為此回路為簡單回路簡單回路. .。 若若通路通路中的中的

56、所有結(jié)點(diǎn)互不相同所有結(jié)點(diǎn)互不相同（從而所有邊互不相從而所有邊互不相同同），則稱此通路為），則稱此通路為基本通路基本通路； 若若回路回路中除中除v v0 0=v=vk k外的外的所有結(jié)點(diǎn)互不相同所有結(jié)點(diǎn)互不相同（從而所從而所有邊互不相同有邊互不相同），則稱此回路為），則稱此回路為基本回路基本回路(Basic (Basic Circuit)Circuit)或者或者初級回路初級回路、圈圈。2022-4-62022-4-6例例9.3.19.3.1判斷下圖判斷下圖G1G1中的回路中的回路v v3 3e e5 5v v4 4e e7 7v v1 1e e4 4v v3 3e e3 3v v2 2e e1

57、1v v1 1e e4 4v v3 3、v v3 3e e3 3v v2 2e e2 2v v2 2e e1 1v v1 1e e4 4v v3 3、v v3 3e e3 3v v2 2e e1 1v v1 1e e4 4v v3 3是否是簡單回路、是否是簡單回路、基本回路？圖基本回路？圖G G2 2 中的通路中的通路v v1 1e e1 1v v2 2e e6 6v v5 5e e7 7v v3 3e e2 2v v2 2e e6 6v v5 5e e8 8v v4 4、v v1 1e e5 5v v5 5e e7 7v v3 3e e2 2v v2 2e e6 6v v5 5e e8 8v

58、 v4 4、v v1 1e e1 1v v2 2e e6 6v v5 5e e7 7v v3 3e e3 3v v4 4是否是簡單通路、基本通路？并求其長度。是否是簡單通路、基本通路？并求其長度。 v v1 1v v4 4v v2 2v v3 3e e7 7e e6 6e e1 1e e4 4e e5 5e e3 3e e2 2G G1 1v v2 2v v5 5v v3 3v v4 4e e2 2e e3 3e e4 4e e5 5e e6 6e e7 7e e1 1G G2 2v v1 1e e8 82022-4-62022-4-6定理定理9.3.19.3.1設(shè)設(shè)G = G = 為線圖，為

59、線圖，V = vV = v1 1, v, v2 2, , , v, vn n ，A = A = (a(aijij) )nxnnxn為為G G的鄰接矩陣，的鄰接矩陣，A Am m=( )=( )nxnnxn。則。則 為從結(jié)點(diǎn)為從結(jié)點(diǎn)v vi i到結(jié)點(diǎn)到結(jié)點(diǎn)v vj j長度為長度為m m的通路數(shù)目；的通路數(shù)目； 為結(jié)點(diǎn)為結(jié)點(diǎn)v vi i到自身的長度為到自身的長度為k k的回路數(shù)目；的回路數(shù)目； 為為G G中長度為中長度為m m的通路（含回路）總數(shù)。的通路（含回路）總數(shù)。 (m)(m)ijija a n n1 1i in n1 1j j(m)(m)ijija a(m)(m)ijija a(m)(m)

60、iiiia a2022-4-62022-4-6例例9.3.29.3.2求下圖求下圖G G中從結(jié)點(diǎn)中從結(jié)點(diǎn)v v1 1到結(jié)點(diǎn)到結(jié)點(diǎn)v v3 3長度為長度為2 2和和3 3的通路數(shù)的通路數(shù)目及所有長度為目及所有長度為2 2和和3 3的通路數(shù)目。的通路數(shù)目。v v4 4v v2 2v v1 1v v3 3分析分析 利用利用定理定理9.3.39.3.3，求圖中長度為，求圖中長度為m m的通路數(shù)目，的通路數(shù)目，只需要先寫出圖的只需要先寫出圖的鄰接矩陣鄰接矩陣，然后計(jì)算鄰接矩陣的，然后計(jì)算鄰接矩陣的m m次方次方即可。即可。2022-4-62022-4-6例例9.3.2 9.3.2 解解在圖中，在圖中，G