離散數(shù)學(xué)-7-3-圖的矩陣表示

1、離 散 數(shù) 學(xué)Discrete Mathematics,山東科技大學(xué)信息科學(xué)與工程學(xué)院,圖的定義點(diǎn)的度數(shù)特殊的圖圖同構(gòu),7-1 圖的基本概念,三、特殊的圖1、多重圖定義7-1.4：含有平行邊的圖稱(chēng)為多重圖。,2、簡(jiǎn)單圖：不含平行邊和環(huán)的圖稱(chēng)為簡(jiǎn)單圖。,3、完全圖定義7-1.5：簡(jiǎn)單圖G=中，若每一對(duì)結(jié)點(diǎn)間均有邊相連，則稱(chēng)該圖為完全圖。有n個(gè)結(jié)點(diǎn)的無(wú)向完全圖記為Kn。,無(wú)向完全圖：每一條邊都是無(wú)向邊

2、 不含有平行邊和環(huán) 每一對(duì)結(jié)點(diǎn)間都有邊相連,如果在Kn中，對(duì)每一條邊任意確定一個(gè)方向，則稱(chēng)該圖為n個(gè)結(jié)點(diǎn)的有向完全圖。顯然它的邊數(shù)為n(n-1)/2。,定理7-1.4 在任何圖中, n個(gè)結(jié)點(diǎn)的無(wú)向完全圖Kn的邊數(shù)為n(n-1)/2。,? 證明： n個(gè)結(jié)點(diǎn)中任取兩個(gè)結(jié)點(diǎn)的組合數(shù)為 Cn2 = n(n-1)/2故

3、的邊數(shù)為 |E| = n(n-1)/2 ?,5、相對(duì)于完全圖的補(bǔ)圖定義7-1.6：給定一個(gè)簡(jiǎn)單圖G，由G中所有結(jié)點(diǎn)和所有能使G成為完全圖的添加邊組成的圖，稱(chēng)為G的相對(duì)于完全圖的補(bǔ)圖，或簡(jiǎn)稱(chēng)為G的補(bǔ)圖，記為?G。即G=，?G=，其中E2={(u，v)?u，v?V，(u，v)?E1}。,6、子圖定義7-1.7：設(shè)圖G=，如果有圖G’=，且E

4、’?E，V’?V，則稱(chēng)G’為G的子圖。 當(dāng)V’=V時(shí)，則稱(chēng)G’為G的生成子圖。,例如，下圖， 圖(b)的G和圖(c)的G’ 都是圖(a)的K5的子圖。,7、相對(duì)于圖G的補(bǔ)圖定義7-1.8：設(shè)G’=是G=的子圖，若給定另一個(gè)圖G”=使得E”=E-E’，且V”中僅包含E”的邊所關(guān)聯(lián)的結(jié)點(diǎn)，則稱(chēng)G”是子圖G’相對(duì)于圖G的補(bǔ)圖。,例如，上圖(b)的G是圖(c)的G’ 相對(duì)于圖(a)的K5的補(bǔ)圖。,圖的定義點(diǎn)的度數(shù)特殊的圖圖

5、同構(gòu),7-1 圖的基本概念,四、同構(gòu)定義7-1.9：設(shè)圖G=及圖G’=，如果存在一一對(duì)應(yīng)的映射g：Vi?Vi’且e=(vi，vj)(或)是G的一條邊，當(dāng)且僅當(dāng)e’=(g(vi)，g(vj))(或)是G’的一條邊，則稱(chēng)G與G’同構(gòu)，記作G ≌ G’。,兩圖同構(gòu)的一些必要條件：1.結(jié)點(diǎn)數(shù)目相同；2.邊數(shù)相等；3.度數(shù)相同的結(jié)點(diǎn)數(shù)目相等。,以上幾個(gè)條件不是兩個(gè)圖同構(gòu)的充分條件。見(jiàn)279頁(yè)圖7-1.10同構(gòu)必須是結(jié)點(diǎn)和邊分別存

6、在一一對(duì)應(yīng)。,練習(xí)279頁(yè)（3）,對(duì)應(yīng)結(jié)點(diǎn)度數(shù)不同，所以?xún)蓤D不同構(gòu)。,作業(yè),279頁(yè):(5)（6）,7-2 路與回路,在現(xiàn)實(shí)世界中，常常要考慮這樣的問(wèn)題：如何從一個(gè)圖中的給定結(jié)點(diǎn)出發(fā)，沿著一些邊連續(xù)移動(dòng)而達(dá)到另一指定結(jié)點(diǎn)，這種依次由點(diǎn)和邊組成的序列，就形成了路的概念。,學(xué)習(xí)本節(jié)要熟悉如下術(shù)語(yǔ)(22個(gè))：,路、,路的長(zhǎng)度、,跡、,回路、,通路、,圈、,連通、,連通分支、,點(diǎn)割集、,連通圖、,割點(diǎn)、,點(diǎn)連通度、,邊割集、,邊連通度、,割邊

7、、,可達(dá)、,單側(cè)連通、,強(qiáng)連通、,強(qiáng)分圖、,弱連通、,弱分圖、,單側(cè)分圖,掌握5個(gè)定理，一個(gè)推論。,路無(wú)向圖的連通性有向圖的連通性,7-2 路與回路,一、路,定義7-2.1 給定圖G=,設(shè) v0,v1,…,vn?V， e1,…,en?E, 其中ei是關(guān)聯(lián)于結(jié)點(diǎn)vi-1,vi的邊，交替序列v0e1v1e2…envn稱(chēng)為結(jié)點(diǎn)v0到vn的路（擬路徑Pseudo path） 。 v0和vn分別稱(chēng)為路的起點(diǎn)和終點(diǎn)，邊的數(shù)目n稱(chēng)作路的長(zhǎng)度

8、。當(dāng)v0=vn時(shí)，這條路稱(chēng)作回路（閉路徑closed walk） 。若一條路中所有的邊e1, …, en均不相同,稱(chēng)作跡（路徑walk） 。若一條路中所有的結(jié)點(diǎn)v0, v1,…, vn均不相同,稱(chēng)作通路(Path) 。閉的通路,即除v0=vn之外，其余結(jié)點(diǎn)均不相同的路，稱(chēng)作圈（回路circuit） 。,例如路：v1e2v3e3v2e3v3e4v2e6v5e7v3跡：v5e8v4e5v2e6v5e7v3e4v2通

9、路：v4e8v5e6v2e1v1e2v3圈：v2e1v1e2v3e7v5e6v2,在簡(jiǎn)單圖中一條路v0e1v1e2…envn，由它的結(jié)點(diǎn)序列v0，v1，…，vn確定，所以簡(jiǎn)單圖的路，可由其結(jié)點(diǎn)序列表示。在有向圖中，結(jié)點(diǎn)數(shù)大于1的一條路亦可由邊序列e1e2…en表示。,定理7-2.1 在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk存在一條路，則從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk必存在一條不多于n-1條邊的路。,? 證明思路：多于n-1條邊的路

10、中必有重復(fù)出現(xiàn)的結(jié)點(diǎn)，反復(fù)刪去夾在兩個(gè)重復(fù)結(jié)點(diǎn)之間的邊之后，剩余的邊數(shù)不會(huì)超過(guò)n-1條邊。 ?,推論 在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk存在一條路，則從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk必存在一條邊數(shù)小于n的通路。,定理7-2.1的證明 如果從結(jié)點(diǎn)vj到vk存在一條路，該路上的結(jié)點(diǎn)序列是vj…vi…vk，如果在這條中有l(wèi)條邊，則序列中必有 l+1個(gè)結(jié)點(diǎn)，若l

11、>n-1，則必有結(jié)點(diǎn)vs，它在序列中不止出現(xiàn)一次，即必有結(jié)點(diǎn)序列vj…vs…vs…vk，在路中去掉從vs到vs的這些邊，仍是vj到vk的一條路，但此路比原來(lái)的路邊數(shù)要少，如此重復(fù)進(jìn)行下去，必可得到一條從vj到vk的不多于n-1條邊的路。,如在圖7-2.1中有5個(gè)結(jié)點(diǎn)。 v1到v3的一條路為：v1e2v3e3v2e3v3e4v2e6v5e7v3此路中有6條邊，去掉e3有路v1e2v3e4v2e6v5e7v3有4條邊。v1到v

12、3最短的路為v1e2v3,路無(wú)向圖的連通性有向圖的連通性,7-2 路與回路,二、無(wú)向圖的連通性：1、連通,定義7-2.2 在無(wú)向圖G中，如果從結(jié)點(diǎn)u和結(jié)點(diǎn)v之間若存在一條路，則稱(chēng)結(jié)點(diǎn)u和結(jié)點(diǎn)v是連通的（connected） 。,結(jié)點(diǎn)之間的連通性是結(jié)點(diǎn)集V上的等價(jià)關(guān)系，對(duì)應(yīng)該等價(jià)關(guān)系，必可將作出一個(gè)劃分，把V分成非空子集V1, V2, …, Vm,使得兩個(gè)結(jié)點(diǎn)vj和vk是連通的，當(dāng)且僅當(dāng)它們屬于同一個(gè)Vi 。把子圖G(V1) ,

13、G(V2) , …, G(Vm)稱(chēng)為圖G的連通分支（connected components）,圖G的連通分支數(shù)記為W(G) 。,,,,,,,,,,,,,,,2、連通圖 定義7-2.3：若圖G只有一個(gè)連通分支，則稱(chēng)G是連通圖。 顯然在連通圖中，任意兩個(gè)結(jié)點(diǎn)之間必是連通的。,,,,,,,,,,,對(duì)于連通圖，常常由于刪除了圖中的點(diǎn)或邊，而影響了圖的連通性。刪除結(jié)點(diǎn)：所謂在圖中刪除結(jié)點(diǎn)v，即是把v以及與v關(guān)聯(lián)的邊

14、都刪除。刪除邊：所謂在圖中刪除某條邊，即是把該邊刪除。,二、無(wú)向圖的連通性1、連通,定義7-2.2 在無(wú)向圖G中，如果從結(jié)點(diǎn)u和結(jié)點(diǎn)v之間若存在一條路，則稱(chēng)結(jié)點(diǎn)u和結(jié)點(diǎn)v是連通的。,2、連通圖 若圖G只有一個(gè)連通分支，則稱(chēng)G是連通圖。,對(duì)于連通圖，常常由于刪除了圖中的點(diǎn)或邊，而影響了圖的連通性。刪除結(jié)點(diǎn)：所謂在圖中刪除結(jié)點(diǎn)v，即是把v以及與v關(guān)聯(lián)的邊都刪除。刪除邊：所謂在圖中刪除某條邊，即是把該邊刪除。,3、割點(diǎn)定

15、義7-2.4 設(shè)無(wú)向圖G =是連通圖,若有結(jié)點(diǎn)集V1?V,使圖G中刪除了V1的所有結(jié)點(diǎn)后,所得到的子圖是不連通圖,而刪除了V1的任何真子集后,所得到的子圖仍是連通圖,則稱(chēng)V1是G的一個(gè)點(diǎn)割集(cut-set of nodes) 。若某一個(gè)點(diǎn)構(gòu)成一個(gè)點(diǎn)割集，則稱(chēng)該點(diǎn)為割點(diǎn)。,點(diǎn)連通度：是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的點(diǎn)的最少數(shù)目，也稱(chēng)為連通度，記為k(G) 。即k(G)=min{|V1|| V1是G的點(diǎn)割集} 稱(chēng)為圖G的點(diǎn)連通度(1

16、)若G是平凡圖，則V1=?，k(G)=0(2)k(Kn)=n-1(3)若圖存在割點(diǎn)，則k(G)=1(4)規(guī)定非連通圖的連通度k(G)=0,4、割邊 定義7-2.5 設(shè)無(wú)向圖G =是連通圖,若有邊集E1?E，使圖 G中刪除了E1的所有邊后，所得到的子圖是不連通圖，而刪除了E1的任何真子集后，所得到的子圖仍是連通圖，則稱(chēng)E1是G的一個(gè)邊割集(cut-set of edges) 。若某一條邊就構(gòu)成一個(gè)邊割集，則稱(chēng)該邊為

17、割邊或橋。 割邊e使圖G滿(mǎn)足W(G-e)>W(G) 。,邊連通度(edge-connectivity) ? (G)定義：非平凡圖的邊連通度為 ? (G)=min{ |E1| | E1是G的邊割集}邊連通度? (G)是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的邊的最少數(shù)目。(1)若G是平凡圖則E1=?，??(G)=0(2)若G存在割邊，則?(G)=1， (3)規(guī)定非連通圖的邊連通度為?(G)=0,5、

18、定理7-2.2 對(duì)于任一圖G,有k(G)≤?(G)≤δ(G) 。,在7-2.2節(jié)定義了圖的最小度： δ(G)=min(deg(v)，v?V) 下面的定理給出了點(diǎn)連通度k(G) 、邊連通度?(G)和圖的最小度?(G)之間的關(guān)系。,,,,,,,,,,,,,,,k(G)=?,?(G)=?,?(G)=?,s,,a,b,c,,,,,d,,,,,,,證明： 若G不連通，則k(G)=?(G)=0，故上式成立

19、。 若G連通，可分兩步證明上式也成立： 1)先證明?(G)≤?(G)： 如果G是平凡圖，則?(G)=0≤?(G)， 若G是非平凡圖，則因每一結(jié)點(diǎn)的所有關(guān)聯(lián)邊必含一個(gè)邊割集，(因?(G)=min{deg(v)|v?V}，設(shè)u?V使的deg(u)=δ(G)，與u相關(guān)聯(lián)的?條邊必包含一個(gè)邊割集，至少這?條邊刪除使圖不連通。)故?(G)≤?(G)。,5、定理7-2.2 對(duì)于

20、任何一個(gè)圖G,有k(G)≤?(G)≤δ(G) 。,2)再證k(G)≤?(G)：(a)設(shè)?(G)=1，即G有一割邊，顯然這時(shí)k(G)=1，上式成立。(b)設(shè)?(G)≥2，則必可刪去某?(G)條邊，使G不連通，而刪去其中?(G)-1條邊，它仍是連通的，且有一條橋e=(u，v)。對(duì)?(G)-1條邊中的每一條邊都選取一個(gè)不同于u、v的端點(diǎn)，把這些端點(diǎn)刪去則必至少刪去?(G)-1條邊。若這樣產(chǎn)生的圖是不連通的，則k(G)≤?(G)-

21、1<?(G)；若這樣產(chǎn)生的圖是連通的，則e仍是橋，此時(shí)再刪去u或v就必產(chǎn)生一個(gè)不連通圖，故k(G)≤?(G)。由1)和2)得k(G)≤?(G)≤?(G)。,6.定理7-2.3 一個(gè)連通無(wú)向圖G的結(jié)點(diǎn)v是割點(diǎn)的充分必要條件是存在兩個(gè)結(jié)點(diǎn)u和w,使得結(jié)點(diǎn)u和w的每一條路都通過(guò)v 。,? 證明思路： 1) 先證:v是割點(diǎn)?存在結(jié)點(diǎn)u和w的每條路都通過(guò)v 若v是連通圖G=割點(diǎn)，設(shè)刪去v得到的子圖G’, 則G’至少包

22、含兩個(gè)連通分支G1=和G2= 。任取u?V1，w?V2，因?yàn)镚是連通的，故在G中必有一條連結(jié)u和w的路C，但u和w在G’中屬于兩個(gè)不同的連通分支，故u和w必不連通，因此C必須通過(guò)v，故u和w之間的任意一條路都通過(guò)v 。 2)再證:存在結(jié)點(diǎn)u和w的每條路都通過(guò)v ?v是割點(diǎn) 若連通圖G中的某兩個(gè)結(jié)點(diǎn)u和w的每一條路都通過(guò)v，則刪去v得到子圖G’，在G’中這兩個(gè)結(jié)點(diǎn)u和w必然不連通，故v是圖G的割點(diǎn)。 ?,三、有向圖

23、的連通性：1、可達(dá)：在無(wú)向圖G中，從結(jié)點(diǎn)u到v若存在一條路，則稱(chēng)結(jié)點(diǎn)u到結(jié)點(diǎn)v是可達(dá)的。,有向圖的可達(dá)性：對(duì)于任何一個(gè)有向圖G=, 從結(jié)點(diǎn)u和到結(jié)點(diǎn)v有一條路,稱(chēng)為從u可達(dá)v。有向圖上的可達(dá)性(accesible),是結(jié)點(diǎn)集上的二元關(guān)系，它是自反的和傳遞的，但是一般來(lái)說(shuō)不是對(duì)稱(chēng)的。故可達(dá)性不是等價(jià)關(guān)系。,如果u可達(dá)v，它們之間可能不止一條路，在所有這些路中，最短路的長(zhǎng)度稱(chēng)為u和v之間的距離（或短程線(xiàn)），記作d，它滿(mǎn)足下列性質(zhì)：d

24、≥0d =0d + d ≥ d,把D=max d, u,v∈V稱(chēng)作圖的直徑。,如果從u到v是不可達(dá)的，則通常寫(xiě)成 d =∞ 注意：當(dāng)u可達(dá)v，且v也可達(dá)u時(shí)， d 不一定等于d,2、定義7-2.6 在簡(jiǎn)單有向圖G中，任何一對(duì)結(jié)點(diǎn)間，至少有一個(gè) 結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的，則稱(chēng)這個(gè)圖是單側(cè)連通的 。 如果對(duì)于圖G中的任何一對(duì)結(jié)點(diǎn)兩者之間是相互可達(dá)的，則稱(chēng)這個(gè)圖是強(qiáng)連通的。 如果在圖G中略去邊的方向，將它看成無(wú)向圖后，圖是

25、連通的，則稱(chēng)該圖為弱連通的。,顯然，強(qiáng)連通圖→單側(cè)連通圖→弱連通圖。而逆推均不成立。,證明：充分性：如G中有一條有向回路，經(jīng)過(guò)每一點(diǎn)至少一次，則G中任意兩點(diǎn)u、v∈V，u和v都是相互可達(dá)的，則G是強(qiáng)連通圖。,3、定理7-2.4：一個(gè)有向圖是強(qiáng)連通的充分必要條件是G有一個(gè)回路，它至少包含每個(gè)結(jié)點(diǎn)一次。,必要性：任取u，v∈V，圖G是強(qiáng)連通圖，則u→v有有向路，v→u也有有向路，則u→v→u構(gòu)成了一個(gè)有向回路，如果該有向回路沒(méi)有包含w，而u

26、→w，w→u均有有向路，則u→v→u→w→u又是一個(gè)有向回路，一直下去可以將圖中所有的點(diǎn)均包含進(jìn)去。,4、定義7-2.7：在簡(jiǎn)單有向圖中，具有強(qiáng)連通性質(zhì)的最大子圖，稱(chēng)為強(qiáng)分圖；具有單側(cè)連通性質(zhì)的最大子圖，稱(chēng)為單側(cè)分圖；具有弱連通性質(zhì)的最大子圖，稱(chēng)為弱分圖。,,,定理7-2.5 在有向圖G=中，它的每一個(gè)結(jié)點(diǎn)位于且只位于一個(gè)強(qiáng)分圖中。,?證明思路： 1)先證:每一個(gè)結(jié)點(diǎn)必位于一個(gè)強(qiáng)分圖中。 2)再證:每一個(gè)結(jié)點(diǎn)只位于

27、一個(gè)強(qiáng)分圖中。 ?,作業(yè),286－287： (2)(5)(8),7-3 圖的矩陣表示,圖G=的圖形表示方法：使用圖形表示法很容易把圖的結(jié)構(gòu)展現(xiàn)出來(lái)，而且這種表示直觀明了。但這只在結(jié)點(diǎn)和邊(或弧)的數(shù)目相當(dāng)小的情況下才是可行的。顯然這限制了圖的利用。圖的另一種表示法—圖的矩陣表示法：克服了圖形表示法的不足可以充分利用現(xiàn)代工具電子計(jì)算機(jī)，以達(dá)到研究圖的目的。,一、鄰接矩陣,0 1 0 0A(G

28、1)= 0 0 1 1 1 1 0 1 1 0 0 0,0 1 1 1 1 1 0 1 0 0A(G)= 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0,無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)矩陣，有向圖的鄰接矩陣不一定是對(duì)稱(chēng)的。,0 0

29、 1 1 1 0 0 0A(G1)= 1 1 0 1 0 1 0 0,圖G2的鄰接矩陣是將圖G1的鄰接矩陣第一、二行對(duì)調(diào)，第一、二列對(duì)調(diào)得到的。,0 1 0 0A(G1)= 0 0 1 1 1 1 0 1 1 0 0 0,對(duì)于給定圖G，顯然不會(huì)因結(jié)點(diǎn)編序不同而使其結(jié)構(gòu)

30、發(fā)生任何變化，即圖的結(jié)點(diǎn)所有不同的編序?qū)嶋H上仍表示同一個(gè)圖。換句話(huà)說(shuō)，這些結(jié)點(diǎn)的不同編序的圖都是同構(gòu)的，并且它們的鄰接矩陣都是相似的。于是圖G與H同構(gòu)?存在置換矩陣P，使A(H)=P-1A(G)P今后將略去這種由于V中結(jié)點(diǎn)編序而引起鄰接矩陣的任意性，而取該圖的任一個(gè)鄰接矩陣作為該圖的矩陣表示。,若鄰接矩陣的元素全為零，則其對(duì)應(yīng)的圖是零圖；若(無(wú)向圖)鄰接矩陣的元素除主對(duì)角線(xiàn)元素外全為1，則其對(duì)應(yīng)的圖是簡(jiǎn)單完全圖。(有向圖)鄰

31、接矩陣的元素除主對(duì)角線(xiàn)元素外全為1，則其對(duì)應(yīng)的圖是強(qiáng)連通圖。,鄰接矩陣可展示相應(yīng)圖的一些性質(zhì)：,當(dāng)給定的簡(jiǎn)單圖是無(wú)向圖時(shí)，鄰接矩陣是對(duì)稱(chēng)矩陣；若給定任何對(duì)稱(chēng)矩陣A，顯然可以唯一地作出以A為其鄰接矩陣的簡(jiǎn)單圖G。所有n個(gè)結(jié)點(diǎn)的不同編序的簡(jiǎn)單圖的集合與所有n階對(duì)稱(chēng)矩陣的集合可建立一一對(duì)應(yīng)。,鄰接矩陣可展示相應(yīng)圖的一些性質(zhì)：,當(dāng)給定的圖是簡(jiǎn)單有向圖時(shí)，其鄰接矩陣并非一定是對(duì)稱(chēng)矩陣，但所有n個(gè)結(jié)點(diǎn)的不同編序的簡(jiǎn)單圖的集合，與所有n階鄰接矩陣

32、的集合亦可建立一一對(duì)應(yīng)。不僅如此，通過(guò)對(duì)矩陣元素的一些計(jì)算還可以得到對(duì)應(yīng)圖的某些數(shù)量的特征。,鄰接矩陣可展示相應(yīng)圖的一些性質(zhì)：,在給定簡(jiǎn)單有向圖的鄰接矩陣中，第i行元素是由結(jié)點(diǎn)vi出發(fā)的弧所確定，故第i行中值為1的元素?cái)?shù)目等于結(jié)點(diǎn)vi的出度。同理，第j列中值為1的元素?cái)?shù)目等于結(jié)點(diǎn)vj的入度。即d+(vi)=和d-(vj)= 。,利用鄰接矩陣計(jì)算結(jié)點(diǎn)的入度和出度,例 290頁(yè)例1,定理7-3.1 設(shè)A(G)是

33、圖G=的鄰接矩陣，則(A(G))l中的i行j列元素aij (l)等于G中聯(lián)結(jié)vi與vj的長(zhǎng)度為l的路徑條數(shù)。,? 證明思路：對(duì)l用數(shù)學(xué)歸納法證明。 1) 當(dāng)l=2時(shí):aij (2)等于G中聯(lián)結(jié)vi與vj的長(zhǎng)度為2的路徑條數(shù)。 2)設(shè)命題對(duì)l成立，即：aij (l)等于G中聯(lián)結(jié)vi與vj的長(zhǎng)度為l的路徑條數(shù)。 3)現(xiàn)證l+1時(shí)也成立。即(A(G))l+1=(A(G)). (A(G))l

34、 n aij (l+1) = ? aik × akj (l) k=1 對(duì)k求和即得結(jié)論。 ?,P300 (1)求出圖7-3.9中有向圖的鄰接矩陣A，找出從v1到v4長(zhǎng)度為2和4的路，用計(jì)算A2，A3，A4來(lái)驗(yàn)證這結(jié)論。,解,從v1到v4長(zhǎng)度為2的路為v1 v2 v4從v1到v4長(zhǎng)度為4的路有：v1 v2 v4 v2 v4 v1 v2 v3

35、 v2 v4 v1 v4 v2 4 v3 v4,,,,,,,,,,,,v2,v3,v1,v4,在一些實(shí)際問(wèn)題中，有時(shí)要判定圖中結(jié)點(diǎn)vi到結(jié)點(diǎn)vj是否可達(dá)，或者說(shuō)vi到vj是否存在路。如果利用圖G的鄰接矩陣A，則可計(jì)算A2，A3，···，An，···。當(dāng)發(fā)現(xiàn)其中某個(gè)Al的aij(l)≥1，就表明vi可達(dá)vj或vi到vj存在一條路。但這種計(jì)算繁瑣量大，又不知計(jì)算Al到

36、何時(shí)為止。,根據(jù)定理7-2.1的推論可知，如果有向圖G有n個(gè)結(jié)點(diǎn)， vi到vj有一條路，則必然有一條長(zhǎng)度不大于n的通路，因此，只需考慮aij(l)就可以了，其中1≤l≤n。即只要計(jì)算Bn=A+A2+A3+···+An。 如果關(guān)心的是結(jié)點(diǎn)間可達(dá)性或結(jié)點(diǎn)間是否有路，至于結(jié)點(diǎn)間的路存在多少條及長(zhǎng)度是多少無(wú)關(guān)緊要，那么便可用可達(dá)矩陣來(lái)表示結(jié)點(diǎn)間可達(dá)性。,定理7-2.1 在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果

37、從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk存在一條路，則從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk必存在一條不多于n-1條邊的路。,二、可達(dá)矩陣,可達(dá)性矩陣的求法有兩種： 1) 計(jì)算矩陣 Bn=A+A2+A3+…+An 令矩陣 Bn中不為零的元素等于1，為零的元素不變，得到P。見(jiàn)例題1。 2) 令P =A∨A(2) ∨ A(3) ∨ … ∨ A(n) 其中A(i)(i=1,2,…,n)為布爾矩陣。見(jiàn)例題2。,P124:War

38、shall算法求取關(guān)系R的傳遞閉包R＋,I = 1，2，3，……，n第i步：如果 A[ j，i]=1，則將第i行加到第j行。,Warshall算法求取可達(dá)矩陣P,三、關(guān)聯(lián)矩陣1、無(wú)向圖的關(guān)聯(lián)矩陣,舉例,,,,,,,,,,,v1,v2,v3,v4,e1,e2,e3,e4,e5,e6,,v5,無(wú)向圖的關(guān)聯(lián)矩陣反映出來(lái)圖的性質(zhì):每一條邊關(guān)聯(lián)兩個(gè)結(jié)點(diǎn),故每一列中只有兩個(gè)1。每一行中元素之和等于該行對(duì)應(yīng)的結(jié)點(diǎn)的度數(shù)。一行中元素全為0，

39、其對(duì)應(yīng)結(jié)點(diǎn)為孤立點(diǎn)。兩個(gè)平行邊其對(duì)應(yīng)的兩列相同。同一個(gè)圖當(dāng)結(jié)點(diǎn)或邊的編號(hào)不同時(shí)，其對(duì)應(yīng)的矩陣只有行序列序的差別。,關(guān)聯(lián)矩陣的運(yùn)算:無(wú)向圖G的兩行相加定義為：第i行第j行的對(duì)應(yīng)元素模2相加；相當(dāng)于刪除結(jié)點(diǎn)vi與結(jié)點(diǎn)vj之間的關(guān)聯(lián)邊，合并結(jié)點(diǎn)vi和vj 。合并后得到的新結(jié)點(diǎn)記為vi,j 。,2、有向圖的關(guān)聯(lián)矩陣,舉例,,,,,,,,,,,v1,v2,v3,v4,e1,e2,e3,e4,e5,e6,,v5,有向圖的關(guān)聯(lián)矩陣的特點(diǎn)：

40、 (1)每一列中有一個(gè)1和一個(gè)-1，對(duì)應(yīng)一邊一個(gè)始點(diǎn)、一個(gè)終點(diǎn)，元素和為零。 (2)每一行元素的絕對(duì)值之和為對(duì)應(yīng)點(diǎn)的度數(shù)。-1的個(gè)數(shù)等于入度，1的個(gè)數(shù)等于出度。,關(guān)聯(lián)矩陣的運(yùn)算:,有向圖G的兩行相加定義為：第i行第j行的對(duì)應(yīng)元素算術(shù)相加；相當(dāng)于刪除結(jié)點(diǎn)vi與結(jié)點(diǎn)vj之間的關(guān)聯(lián)邊，合并結(jié)點(diǎn)vi和vj 。合并后得到的新結(jié)點(diǎn)記為vi,j 。,3、關(guān)聯(lián)矩陣的秩,定理7-3.2 如果一個(gè)連通圖G=,有r個(gè)結(jié)點(diǎn),則其完全關(guān)聯(lián)矩陣M(G)的秩

41、為r-1,即rank M (G)=r-1 。,? 證明思路： 只對(duì)無(wú)向圖證明 利用線(xiàn)性代數(shù)中矩陣的初等（行、列）變換不改變矩陣的秩的結(jié)論和方法。 ?,定理7-3.2的推論 如果一個(gè)連通圖G=,有r個(gè)結(jié)點(diǎn),w個(gè)最大連通子圖,則圖G的完全關(guān)聯(lián)矩陣M(G)的秩為r- w,即rank M (G)=r-w 。,小結(jié),圖的矩陣鄰接矩陣：點(diǎn)與點(diǎn)之間的鄰接關(guān)系矩陣可達(dá)矩陣：點(diǎn)與點(diǎn)之間的可達(dá)關(guān)系矩陣關(guān)聯(lián)矩陣：點(diǎn)與邊之間的關(guān)聯(lián)關(guān)系

42、矩陣,作業(yè),P300：(2)(3)(4)的關(guān)聯(lián)矩陣,7-4 歐拉圖和漢密爾頓圖,要求：1、理解歐拉圖、漢密爾頓圖的定義。2、掌握歐拉圖的判定方法。3、會(huì)判斷一些圖不是漢密爾頓圖。4、熟悉一些歐拉圖和漢密爾頓圖。,一、歐拉圖1、哥尼斯堡七橋問(wèn)題,近代圖論的歷史可追溯到18世紀(jì)的七橋問(wèn)題—穿過(guò)哥尼斯堡城的七座橋，要求每座橋通過(guò)一次且僅通過(guò)一次。,七橋問(wèn)題等價(jià)于在圖中求一條回路，此回路經(jīng)過(guò)每條邊一次且僅有一次。歐拉在173

43、6年的論文中提出了一條簡(jiǎn)單的準(zhǔn)則，確定了哥尼斯堡七橋問(wèn)題是不能解的。,2、歐拉圖(Euler),如果無(wú)孤立結(jié)點(diǎn)圖G上有一條經(jīng)過(guò)G的所有邊一次且僅一次的路徑，則稱(chēng)該路徑為圖G的歐拉路徑（Euler walk）。如果圖G上有一條經(jīng)過(guò)G邊一次且僅一次的的回路，則稱(chēng)該回路為圖G的歐拉回路。具有歐拉回路的圖稱(chēng)為歐拉圖（Euler graph）。,定理7-4.1 無(wú)向圖G具有一條歐拉路，當(dāng)且僅當(dāng)G連通，并且有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)。,? 證明

44、思路：1) 先證必要性: G有歐拉路 ? G連通 且（有0個(gè) 或 2個(gè)奇數(shù)度結(jié)點(diǎn)） 設(shè)G的歐拉路是點(diǎn)邊序列v0e1v1e2… ekvk，其中結(jié)點(diǎn)可能重復(fù)，但邊不重復(fù)。因歐拉路經(jīng)過(guò)（所有邊?）所有結(jié)點(diǎn)，所以圖G是連通的。 對(duì)于任一非端點(diǎn)結(jié)點(diǎn)vi，在歐拉路中每當(dāng)vi出現(xiàn)一次，必關(guān)聯(lián)兩條邊，故vi雖可重復(fù)出現(xiàn)，但是deg(vi)必是偶數(shù)。對(duì)于端點(diǎn),若v0=vk ，則deg(v0)必是偶數(shù)，即G中無(wú)奇數(shù)度結(jié)點(diǎn) 。若

45、v0≠vk ，則deg(v0)必是奇數(shù)， deg(vk)必是奇數(shù),即G中有兩個(gè)奇數(shù)度結(jié)點(diǎn) 。必要性證完。,2)再證充分性:(證明過(guò)程給出了一種構(gòu)造方法) G連通且（有0個(gè) 或 2個(gè)奇數(shù)度結(jié)點(diǎn)）? G有歐拉路 (1)若有 2個(gè)奇數(shù)度結(jié)點(diǎn),則從其中一個(gè)結(jié)點(diǎn)開(kāi)始構(gòu)造一條跡,即從v0出發(fā)經(jīng)關(guān)聯(lián)邊e1進(jìn)入v1,若deg(v1)為偶數(shù),則必可由v1再經(jīng)關(guān)聯(lián)邊e2進(jìn)入v2,如此下去,每邊僅取一次,由于G是連通的,故必

46、可到達(dá)另一奇數(shù)度結(jié)點(diǎn)停下,得到一條跡L1:v0e1v1e2… ekvk。若G中沒(méi)有奇數(shù)度結(jié)點(diǎn),則從任一結(jié)點(diǎn)v0出發(fā),用上述方法必可回到結(jié)點(diǎn)v0,得到一條閉跡。 (2) 若L1通過(guò)了G的所有邊, L1就是一條歐拉路。 (3) 若G中去掉L1后得到子圖G’,則G’中每個(gè)結(jié)點(diǎn)度數(shù)都為偶數(shù),因?yàn)樵瓉?lái)的圖G是連通的,故L1與G’至少有一個(gè)結(jié)點(diǎn)vi重合,在G’中由vi出發(fā)重復(fù)(1)的方法,得到閉跡L2。

47、 (4)當(dāng)L1與L2組合,若恰是G,得歐拉路,否則重復(fù)(3),可得閉跡L3,依此類(lèi)推可得一條歐拉路。充分性證完 ?,由于有了歐拉路和歐拉回路的判別準(zhǔn)則，因此哥尼斯堡七橋問(wèn)題立即有了確切的否定答案，因?yàn)閺膱D中可以看到deg(A)＝5，deg(B)＝deg(C)＝deg(D)=3，故歐拉回路必不存在。,定理7-4.1的推論 無(wú)向圖G具有一條歐拉回路，當(dāng)且僅當(dāng)G連通且所有結(jié)點(diǎn)度數(shù)皆為偶數(shù)。,4、一筆畫(huà)問(wèn)題要判定一個(gè)圖G是否可一筆畫(huà)出

48、，有兩種情況：一是從圖G中某一結(jié)點(diǎn)出發(fā)，經(jīng)過(guò)圖G的每一邊一次僅一次到達(dá)另一結(jié)點(diǎn)。另一種就是從G的某個(gè)結(jié)點(diǎn)出發(fā)，經(jīng)過(guò)G的每一邊一次僅一次再回到該結(jié)點(diǎn)。,,,,,,,,,,,,v1,v2,v3,v4,v5,,,,,,,,,,,,,,,,,,,為歐拉路，有從v2到v3的一筆畫(huà)。為歐拉回路，可以從任一結(jié)點(diǎn)出發(fā)，一筆畫(huà)回到原出發(fā)點(diǎn)。,,,,,,,,,,,,,5.定義7-4.2：給定有向圖G，通過(guò)圖中每邊一次且僅一次的一條單向路（回路），稱(chēng)作

49、單向歐拉路（回路）。,可以將歐拉路和歐拉回路的概念推廣到有向圖中。,6.定理7-4.2 (1)有向圖G為具有一條單向歐拉回路，當(dāng)且僅當(dāng)G連通，并且每個(gè)結(jié)點(diǎn)的入度等于出度。(2)有向圖G有單向歐拉路，當(dāng)且僅當(dāng)G連通，并且恰有兩個(gè)結(jié)點(diǎn)的入度與出度不等，它們中一個(gè)的出度比入度多1，另一個(gè)入度比出度多1。 證明思路與定理7-4.1類(lèi)似,例1有向歐拉圖應(yīng)用示例：計(jì)算機(jī)鼓輪的設(shè)計(jì)。 鼓輪表面分成24=16等份，其

50、中每一部分分別用絕緣體或?qū)w組成，絕緣體部分給出信號(hào)0，導(dǎo)體部分給出信號(hào)1，在下圖中陰影部分表示導(dǎo)體，空白體部分表示絕緣體，根據(jù)鼓輪的位置，觸點(diǎn)將得到信息4個(gè)觸點(diǎn)a,b,c,d讀出1101(狀態(tài)圖中的邊e13),轉(zhuǎn)一角度后將讀出1010 (邊e10)。 問(wèn)鼓輪上16個(gè)部分怎樣安排導(dǎo)體及絕緣體才能使鼓輪每旋轉(zhuǎn)一個(gè)部分，四個(gè)觸點(diǎn)能得到一組不同的四位二進(jìn)制數(shù)信息。,,,,,,,,,,,,,,,,,,,,,,,,,,,,0,1,

51、1,1,1,1,1,1,1,0,0,0,0,0,0,0,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,1,1,1,0,a,b,c,d,,設(shè)有一個(gè)八個(gè)結(jié)點(diǎn)的有向圖，如下圖所示。其結(jié)點(diǎn)分別記為三位二進(jìn)制數(shù){000，001，……，111}，設(shè)ai?{0,1}，從結(jié)點(diǎn)a1 a2 a3可引出兩條有向邊，其終點(diǎn)分別是a2 a30以及a2 a31。該兩條邊分別記為a1 a2 a30和a1 a2 a31。按照

52、上述方法，對(duì)于八個(gè)結(jié)點(diǎn)的有向圖共有16條邊，在這種圖的任一條路中，其鄰接的邊必是a1 a2 a3a4和a2 a3a4a5的形式，即是第一條邊標(biāo)號(hào)的后三位數(shù)與第二條邊的頭三位數(shù)相同。 由于圖中16條邊被記為不同的二進(jìn)制數(shù)，可見(jiàn)前述鼓輪轉(zhuǎn)動(dòng)所得到16個(gè)不同位置觸點(diǎn)上的二進(jìn)制信息，即對(duì)應(yīng)于圖中的一條歐拉回路。,010,101,110,100,011,001,111,000,,,,,,,,,,,,,e10=1010,e13=1101,e

53、5=0101,e3=0011,e11=1011,,,e6=0110,e7=0111,e14=1110,e15=1111,e12=1100,e2=0010,e4=0100,e1=0001,e8=1000,e9=1001,e0=0000,a1 a2 a3 (=000) 0,,,a1 a2 a3 (=000) 1,a1 a2 a3 (=001) 1,,a1 a2 a3 (=100) 0,,a1 a2 a3 (=111) 0,,,a1 a2 a

54、3 (=111) 1,a1 a2 a3 (=110) 0,,a1 a2 a3 (=011) 1,,所求的歐拉回路為： e0e1e2e4e9e3e6e13e10e5e11e7e16e14e12e8(e0) （從圖示位置開(kāi)始） e13e10e5e11e7e16e14e12e8e0e1e2e4e9e3e6 (e13) 所求的二進(jìn)制序列為： 0000100110101111 (0)

55、1101011110000100 (1) （從圖示位置開(kāi)始）,上述結(jié)論可推廣到鼓輪具有n個(gè)觸點(diǎn)的情況。構(gòu)造2n-1 個(gè)結(jié)點(diǎn)的有向圖，每個(gè)結(jié)點(diǎn)標(biāo)記為n-1位二進(jìn)制數(shù),從結(jié)點(diǎn)a1a2a3...an-1出發(fā),有一條終點(diǎn)為a2a3...an-10的邊,該邊記為a1a2a3...an-10；還有一條終點(diǎn)標(biāo)記為a2a3...an-11的邊,該邊記為a1a2a3...an-11 。鄰接邊的標(biāo)記規(guī)則為：“第一條邊后n-1位與第二條邊前n-1位二進(jìn)制數(shù)相

56、同”。 哈密爾頓回路問(wèn)題見(jiàn)圖7-4.6。,二、漢密爾頓圖,與歐拉回路類(lèi)似的是漢密爾頓回路。它是1859年漢密爾頓首先提出的一個(gè)關(guān)于12面體的數(shù)學(xué)游戲：能否在圖7-4.6中找到一個(gè)回路，使它含有圖中所有結(jié)點(diǎn)一次且僅一次？若把每個(gè)結(jié)點(diǎn)看成一座城市，連接兩個(gè)結(jié)點(diǎn)的邊看成是交通線(xiàn)，那么這個(gè)問(wèn)題就變成能否找到一條旅行路線(xiàn)，使得沿著該旅行路線(xiàn)經(jīng)過(guò)每座城市恰好一次，再回到原來(lái)的出發(fā)地？他把這個(gè)問(wèn)題稱(chēng)為周游世界問(wèn)題。,定義7-4.3：給定圖

57、G，若存在一條路經(jīng)過(guò)圖中的每個(gè)結(jié)點(diǎn)恰好一次，這條路稱(chēng)作漢密爾頓路。若存在一條回路，經(jīng)過(guò)圖中的每個(gè)結(jié)點(diǎn)恰好一次，這條回路稱(chēng)作漢密爾頓回路。具有漢密爾頓回路的圖稱(chēng)作漢密爾頓圖。,二、漢密爾頓圖,圖7-4.6存在一條漢密爾頓回路，它是漢密爾頓圖,2、定理7-4.3 若圖G＝具有漢密爾頓回路，則對(duì)于結(jié)點(diǎn)集V的每個(gè)非空子集S均有W(G-S)≤|S|，其中W(G-S)是G-S的連通分支數(shù)。,證明 設(shè)C是G的一條漢密爾頓回路，對(duì)于V的

58、任何一個(gè)非空子集S，在C中刪去S中任一結(jié)點(diǎn)a1，則C-a1是連通的非回路， W(C- a1)=1， |S|≥1，這時(shí) W(C-S)≤|S|。 若再刪去S中另一結(jié)點(diǎn)a2，則W(C-a1-a2)≤2，而 |S|≥2，這時(shí) W(C-S)≤|S|。由歸納法可得：W(C-S)≤|S|。同時(shí)C-S是G-S的一個(gè)生成子圖，因而W(G-S)≤W(C-S)，所以W(G-S)≤|S|。,C經(jīng)過(guò)圖G的每個(gè)結(jié)點(diǎn)恰好一次， C與G的結(jié)點(diǎn)集合是同一個(gè)，因此 C-S

59、與G-S的結(jié)點(diǎn)集合是同一個(gè)，,定理7-4.3是必要條件，可以用來(lái)證明一個(gè)圖不是漢密爾頓圖。,如右圖，取S={v1,v4}，則G-S有3個(gè)連通分支，,不滿(mǎn)足W(G-S)≤|S|，故該圖不是漢密爾頓圖。,所以用此定理來(lái)證明某一特定圖不是漢密爾頓圖并不是總是有效的。例如，著名的彼得森(Petersen)圖，在圖中刪去任一個(gè)結(jié)點(diǎn)或任意兩個(gè)結(jié)點(diǎn)，不能使它不連通；刪去3個(gè)結(jié)點(diǎn)，最多只能得到有兩個(gè)連通分支的子圖；刪去4個(gè)結(jié)點(diǎn)，只能得到最多三個(gè)連通分支

60、的子圖；刪去5個(gè)或5個(gè)以上的結(jié)點(diǎn)，余下子圖的結(jié)點(diǎn)數(shù)都不大于6，故必不能有5個(gè)以上的連通分支數(shù)。所以該圖滿(mǎn)足W(G-S)≤|S|，但是可以證明它不是漢密爾頓圖。,說(shuō)明：此定理是必要條件而不是充分條件。有的圖滿(mǎn)足此必要條件，但也不是漢密爾頓圖。,3.定理7-4.4 設(shè)圖G具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,如果G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n-1,則G中存在一條漢密爾頓路。,? 證明思路：1) 先證G連通: 若G有兩個(gè)或多個(gè)互不連通的分支

61、,設(shè)一個(gè)分圖有n1個(gè)結(jié)點(diǎn),任取一個(gè)結(jié)點(diǎn)v1,另一分圖有n2個(gè)結(jié)點(diǎn),任取一個(gè)結(jié)點(diǎn)v2,因?yàn)閐eg(v1)≤n1-1, deg(v2)≤n2-1, deg(v1)+ deg(v2)≤n1+n2-2<n-1 ,與假設(shè)矛盾, G是連通的。,2) 先證(構(gòu)造)要求的漢密爾頓路存在: 不要求掌握！,2) 先證(構(gòu)造)要求的漢密爾頓路存在: 設(shè)G中有p-1條邊的路,p<n,它的結(jié)點(diǎn)序列為v1, v2,…, vp

62、。如果有v1或vp鄰接于不在這條路上的一個(gè)結(jié)點(diǎn),立刻擴(kuò)展該路,使它包含這個(gè)結(jié)點(diǎn),從而得到p條邊的路。否則v1和vp都只鄰接于這條路上的結(jié)點(diǎn),我們證明在這種情況下,存在一條回路包含結(jié)點(diǎn)v1, v2,…, vp。,若v1鄰接于vp,則v1, v2, …, vp即為所求。 若v1鄰接于結(jié)點(diǎn)集{vl,vm,…,…,vj,…,vt}中之一,這里2≤l,m,...,j,...,t≤p-1,如果vp是鄰接于vl-1,vm-1,…,…,v

63、j-1, …,vt-1中之一,譬如是vj-1,則v1v2…vj-1vpvp-1...vjv1 是所求回路（如圖7-4.9(a)所示）。 如果vp不鄰接于vl-1,vm-1,…,…,vj-1, …,vt-1中任一個(gè),則vp最多鄰接于p-k-1個(gè)結(jié)點(diǎn), deg(vp)≤p-k-1, deg(v1)=k,故deg(vp)+deg(v1)≤p-k-1+k<n-1,即v1與 vp 度數(shù)之和最多為n-2，得到矛盾。,至此，已經(jīng)構(gòu)造出

64、一條包含結(jié)點(diǎn)v1,v2,…,vp的回路,因?yàn)镚是連通的,所以在G中必有一個(gè)不屬于該回路的結(jié)點(diǎn)vx與回路中某一結(jié)點(diǎn)vk鄰接,如圖7-4.9(b)所示, 于是就得到一條包含p條邊的回路(vx,vk,vk+1,…,vj-1,vp,vp-1,…, vj,v1, v2 , …, vk-1),如圖7-4.9(c)所示,重復(fù)前述構(gòu)造方法，直到得到n-1條邊的路。 ?,,說(shuō)明：該定理的條件是充分條件但不是必要條件。例：見(jiàn)3

65、08頁(yè)圖7-4.10。n=6，每一對(duì)結(jié)點(diǎn)度數(shù)之和等于4，小于n-1，但在G中存在一條漢密爾頓路。,3.定理7-4.4 設(shè)圖G具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,如果G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n-1,則G中存在一條漢密爾頓路。,例 某地有5個(gè)風(fēng)景點(diǎn)，若每個(gè)景點(diǎn)均有兩條道路與其他景點(diǎn)相通，問(wèn)是否可經(jīng)過(guò)每個(gè)景點(diǎn)一次而游完這5處。,解 將景點(diǎn)作為結(jié)點(diǎn)，道路作為邊，則得到一個(gè)有5個(gè)結(jié)點(diǎn)的無(wú)向圖。 由題意，對(duì)每個(gè)結(jié)點(diǎn)vi(i=1,2

66、,3,4,5)有 deg(vi)=2。 則對(duì)任兩點(diǎn)和均有 deg(vi) + deg(vj)=2 + 2 =4 = 5 – 1 所以此圖有一條漢密爾頓回路。即經(jīng)過(guò)每個(gè)景點(diǎn)一次而游完這5個(gè)景點(diǎn)。,例：在七天內(nèi)安排七門(mén)課程的考試，使得同一位教師所任的兩門(mén)課程不排在接連的兩天中，試證明如果沒(méi)有教師擔(dān)任多于四門(mén)課程，則符合上述要求的考試安排總是可能的。,證明：設(shè)

67、G為具有七個(gè)結(jié)點(diǎn)的圖，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一門(mén)課程考試，如果這兩個(gè)結(jié)點(diǎn)對(duì)應(yīng)的課程考試是由不同教師擔(dān)任的，那么這兩個(gè)結(jié)點(diǎn)之間有一條邊，因?yàn)槊總€(gè)教師所任課程數(shù)不超過(guò)4，故每個(gè)結(jié)點(diǎn)的度數(shù)至少是3，任兩個(gè)結(jié)點(diǎn)的度數(shù)之和至少是6，故G總是包含一條漢密爾頓路，它對(duì)應(yīng)于一個(gè)七門(mén)考試課程的一個(gè)適當(dāng)?shù)陌才拧?4.定理7-4.5 設(shè)圖G具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,如果G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n,則G中存在一條漢密爾頓回路。證明：略,5、圖的閉包

68、 定義7-4.4：給定圖G=有n個(gè)結(jié)點(diǎn)，若將圖G中度數(shù)之和至少是n (≥n) 的非鄰接結(jié)點(diǎn)連接起來(lái)得圖G’，對(duì)圖G’重復(fù)上述步驟，直到不再有這樣的結(jié)點(diǎn)對(duì)存在為止，所得到的圖，稱(chēng)為是原圖G的閉包，記作C(G)。,在這個(gè)例子中C(G)是完全圖，一般情況下， C(G)也可能不是完全圖。,6、定理7-4.6：當(dāng)且僅當(dāng)一個(gè)簡(jiǎn)單圖的閉包是漢密爾頓圖時(shí)，這個(gè)簡(jiǎn)單圖是漢密爾頓圖。7、推論：n?3的有向(無(wú)向)完全圖Kn為漢密爾頓圖。,判