離散數(shù)學(xué)第7章

1、第四篇圖論,圖論是近年來發(fā)展迅速而又應(yīng)用廣泛的一門新興學(xué)科。它最早起源于一些數(shù)學(xué)游戲的難題研究，如1736年歐拉（L.Euler)所解決的哥尼斯堡七橋問題。以及在民間廣為流傳的一些游戲問題：例如　迷宮問題、棋盤上馬的行走路線問題等等。這些古老的問題當(dāng)時吸引了許多學(xué)者的注意，從而在這些問題研究的基礎(chǔ)上，又提出了著名的四色猜想和環(huán)游世界各國的問題。,例：用定理解決哥尼斯堡橋的問題,第四篇 圖論,圖論不斷發(fā)展，它在解決運籌學(xué)，網(wǎng)絡(luò)理論，

2、信息論，控制論，博奕論以及計算機科學(xué)等各個領(lǐng)域的問題時，顯示出越來越大的效果。 對于這樣一門應(yīng)用廣泛的學(xué)科，其包含的內(nèi)容是豐富的，本篇我們只準(zhǔn)備介紹基本的概念和定理，為今后有關(guān)學(xué)科及課程的學(xué)習(xí)和研究提供方便。,WWW,復(fù)雜網(wǎng)絡(luò)的事例——技術(shù)網(wǎng)絡(luò),復(fù)雜網(wǎng)絡(luò)的事例——社會網(wǎng)絡(luò),朋友關(guān)系網(wǎng),科學(xué)引文網(wǎng),復(fù)雜網(wǎng)絡(luò)的事例——交通運輸網(wǎng)絡(luò),復(fù)雜網(wǎng)絡(luò)的事例——生物網(wǎng)絡(luò),Santa Fe 研究所的科學(xué)家合作網(wǎng),復(fù)雜網(wǎng)絡(luò)的事例——科學(xué)家合作網(wǎng),經(jīng)濟

3、物理學(xué)科學(xué)家合作網(wǎng),復(fù)雜網(wǎng)絡(luò)的事例——科學(xué)家合作網(wǎng),復(fù)雜網(wǎng)絡(luò)的事例——中藥方劑網(wǎng)示意圖,點（藥材）， 邊（藥材之間相互作用）， 局域世界（方劑）,§1 圖的基本概念,定義: 圖（graph）G由一個三元組表示，其中： 非空集合V(G)={v1,v2,…,vr} 稱為圖G的結(jié)點集，其成員vi(i=1,2,…,r)稱為結(jié)點或頂點（nodes or vertices）；集合 E(G)={e1,e2,…,

4、es} 稱為圖G的邊集，其成員ej(j=1,2,…s)稱為邊(edges)。函數(shù)?G ：E(G)→(V(G),V(G)) ，稱為邊與頂點的關(guān)聯(lián)映射（associatve mapping）,§1 圖的基本概念,例：G=其中V(G)={a，b，c，d}，E(G)={e1，e2，e3，e4，e5，e6}，?G(e1)=(a，b)，?G(e2)=(a，c)，?G(e3)=(b，d)，?G(e4)=(b，c)，?G(e5)=(

5、d，c)，?G(e6)=(a，d),§1 圖的基本概念,討論定義： (1)V(G) ={V1，V2，…，Vn}為有限非空集合, Vi稱為結(jié)點,簡稱V是點集。 (2)E(G)={e1，…，em}為有限的邊集合,ei稱邊， 每個ei都有V中的結(jié)點對與之相對應(yīng),稱E為邊集。 即每條邊是連結(jié)V中的某兩個點的。,§1圖的基本概念,(3) 若Ｇ中每一條邊e與有序偶對或無序偶對(vi,vj)相關(guān)

6、聯(lián)，則可說邊e連接結(jié)點vi和vj(4) 可用e＝或e＝ (vi,vj)，以結(jié)點來表示圖的邊，這樣可把圖簡化成：Ｇ＝。 例：有圖如下，試寫成定義表達式Ｇ＝〈Ｖ，Ｅ〉，其中Ｖ＝{v1,v2,v3,v4,v5} Ｅ＝{x1,x2,x3,x4,x5,x6},§1圖的基本概念,例：對有向圖可表示為：Ｇ＝〈Ｖ、Ｅ〉，其中Ｖ＝｛a、b、c、d｝Ｅ＝｛,,,,,｝,§1圖的基本概念,下面定義一些專門名詞：(1)有向

7、邊：若邊ej與結(jié)點序偶關(guān)聯(lián)，那么稱該邊為有向邊。(2)無向邊：若邊ej與結(jié)點無序偶(vj,vk)關(guān)聯(lián)，那么稱該邊為無向邊。,§1圖的基本概念,(3)鄰接結(jié)點：由一條邊（有向或無向）連接起來的結(jié)點偶對。 (4)（ｎ，ｅ）圖：具有ｎ個結(jié)點（頂點），ｅ條邊的圖。,§1圖的基本概念,(5)有向圖：在Ｇ中每一條邊均為有向邊。(6)無向圖：每條邊均為無向邊的圖。(7)混合圖：有些邊是無向邊，有些邊是有向邊的圖稱為混合圖

8、。,§1圖的基本概念,§1圖的基本概念,(8)點和邊的關(guān)聯(lián)：如ei=(u，v)或ei=稱u，v與ei關(guān)聯(lián)。(9)點與點的相鄰：關(guān)聯(lián)于同一條邊的結(jié)點稱為鄰接點。(10)邊與邊的鄰接：關(guān)聯(lián)于同一結(jié)點的邊稱為鄰接邊。,§1圖的基本概念,(11)孤立結(jié)點：不與任何結(jié)點相鄰接的結(jié)點稱為孤立結(jié)點。(12)零圖：僅有孤立結(jié)點的圖。(13)平凡圖：僅有一個孤立結(jié)點的圖。(14)自回路(環(huán))：關(guān)聯(lián)于同一結(jié)點的邊稱為

9、自回路，或稱為環(huán)。,§1圖的基本概念,(15) 平行邊：在有向圖中，始點和終點均相同的邊稱為平行邊，無向圖中若兩點間有多條邊，稱這些邊為平行邊，兩點間平行邊的條數(shù)稱為邊的重數(shù)。,定義：在圖G=，v?V，與結(jié)點v關(guān)聯(lián)的邊數(shù)稱為該點的度數(shù)，記為deg(v)。 孤立結(jié)點的度數(shù)為0。 圖G最大度記為?(G)=max{deg(v)|v?V(G)}， 最小度數(shù)記為 ?(G)=min{deg(v)|v?V(G)},

10、7;1圖的基本概念,定義：在有向圖中，v?V，以v為始點的邊數(shù)稱為該結(jié)點的出度，記作deg+(v);以v為終點的邊數(shù)稱為該結(jié)點的入度，記作deg-(v)。顯然有? deg(v)=deg+(v)+deg-(v),如：G1是無向圖，deg(v1)=3，deg(v2)=1G2是有向圖，deg+(v1)= 2 ，deg-(v1)=3，deg(v1)=5，,定理：每個圖中，結(jié)點度數(shù)總和等于邊數(shù)的兩倍。即 ?deg(v)=2|E|

11、 v?V,定理：在任何圖中, 度數(shù)為奇數(shù)的結(jié)點必定是偶數(shù)個。,,定理：在任何有向圖中，所有結(jié)點的入度之和等于所有結(jié)點的出度之和。,,定義：含有平行邊的圖稱為多重圖。,,簡單圖：不含平行邊和環(huán)的圖稱為簡單圖。,定義：簡單圖G=中，若每一對結(jié)點間均有邊相連，則稱該圖為完全圖。有n個結(jié)點的無向完全圖記為Kn。,,定理：在任何圖中, n個結(jié)點的無向完全圖Kn的邊數(shù)為n(n-1)/2。,無向完全圖：每一條邊都是無向邊

12、 不含有平行邊和環(huán) 每一對結(jié)點間都有邊相連,,證明： n個結(jié)點中任取兩個結(jié)點的組合數(shù)為 Cn2 = n(n-1)/2故的邊數(shù)為 |E| = n(n-1)/2,,定義：給定一個簡單圖G，由G中所有結(jié)點和所有能使G成為完全圖的添加邊組成的圖，稱為G的相對于完全圖的補圖，或簡稱為G的補圖，記為

13、?G。即G=，?G=，其中E2={(u，v)?u，v?V，(u，v)?E1}。,,,定義：設(shè)圖G=，如果有圖G’=，且E’?E，V’?V，則稱G’為G的子圖。當(dāng)V’=V時，則稱G’為G的生成子圖。,,相對于圖G的補圖定義：設(shè)G’=是G=的子圖，若給定另一個圖G”=使得E”=E-E’，且V”中僅包含E”的邊所關(guān)聯(lián)的結(jié)點，則稱G”是子圖G’相對于圖G的補圖。,,定義：設(shè)圖G=及圖G’=，如果存在一一對應(yīng)的映射g：vi?vi’且e=(v

14、i，vj)(或)是G的一條邊，當(dāng)且僅當(dāng)e’=(g(vi)，g(vj))(或)是G’的一條邊，則稱G與G’同構(gòu)，記作G ≌ G’。,兩圖同構(gòu)的一些必要條件：1.結(jié)點數(shù)目相同；2.邊數(shù)相等；3.度數(shù)相同的結(jié)點數(shù)目相等。,§2 路與回路,定義: 給定圖G=,設(shè) v0,v1,…,vn?V， e1,…,en?E, 其中ei是關(guān)聯(lián)于結(jié)點vi-1,vi的邊，交替序列v0e1v1e2…envn稱為結(jié)點v0到vn的路（擬路徑Pseu

15、do path） 。 v0和vn分別稱為路的起點和終點， 邊的數(shù)目n稱作路的長度。 當(dāng)v0=vn時，這條路稱作回路（閉路徑closed walk） 。,,例如路：v1e2v3e3v2e3v3e4v2e6v5e7v3 v5e8v4e5v2e6v5e7v3e4v2 v4e8v5e6v2e1v1e2v3 v2e1v1e2v3e7v5e6

16、v2,§2 路與回路,若一條路中所有的邊e1, …, en均不相同稱作跡（路徑walk） 。 若一條路中所有的結(jié)點v0, v1,…, vn均不相同,稱作通路（Path） 。 閉的通路,即除v0=vn之外，其余結(jié)點均不相同的路，稱作圈（回路circuit） 。,,§2路與回路,定理： 在一個具有n個結(jié)點的圖中，如果從結(jié)點vj到結(jié)點vk存在一條路，則從結(jié)點vj到結(jié)點vk必存在一條不多于n-1

17、條邊的路。,§2路與回路,推論：在一個具有n個結(jié)點的圖中，如果從結(jié)點vj到結(jié)點vk存在一條路，則從結(jié)點vj到結(jié)點vk必存在一條邊數(shù)小于n的通路。,,§2路與回路,定義： 在無向圖G中，如果從結(jié)點u和結(jié)點v之間若存在一條路，則稱結(jié)點u和結(jié)點v是連通的（connected） 。,,§2路與回路,結(jié)點之間的連通性是結(jié)點集V上的等價關(guān)系。 把子圖G(V1) , G(V2) , …, G(Vm)稱為圖

18、G的連通分支（connected components）,圖G的連通分支數(shù)記為W(G) 。,,§2路與回路,定義：若圖G只有一個連通分支，則稱G是連通圖。 顯然在連通圖中，任意兩個結(jié)點之間必是連通的。,,§2路與回路,對于連通圖，常常由于刪除了圖中的點或邊，而影響了圖的連通性。 刪除結(jié)點：所謂在圖中刪除結(jié)點v，即是把v以及與v關(guān)聯(lián)的邊都刪除。 刪除邊：所謂在圖中刪除某條邊，即是

19、把該邊刪除。,,§2路與回路,,定義：設(shè)無向圖G =是連通圖,若有結(jié)點集V1?V,使圖G中刪除了V1的所有結(jié)點后,所得到的子圖是不連通圖,而刪除了V1的任何真子集后,所得到的子圖仍是連通圖,則稱V1是G的一個點割集(cut-set of nodes) 。若某一個點構(gòu)成一個點割集，則稱該點為割點。,§2 路與回路,點連通度：為了產(chǎn)生一個不連通圖需要刪去的點的最少數(shù)目，也稱為連通度,記為k(G) 。 即k(G)=

20、min{|V1|| 是G的點割集} 稱為圖G的點連通度(node-connectivity) 。,,§2 路與回路,(1)若G是平凡圖則k(G)=0(2)k(Kn)=n-1(3)若圖存在割點，則k(G)=1(4)規(guī)定非連通圖的連通度k(G)=0,,§2 路與回路,,點割集V1={v2},§2 路與回路,定義：設(shè)無向圖G =是連通圖,若有邊集E1?E，使圖 G中刪除了E1的所有邊后，所得到

21、的子圖是不連通圖，而刪除了E1的任何真子集后，所得到的子圖仍是連通圖，則稱E1是G的一個邊割集(cut-set of edges) 。若某一條邊就構(gòu)成一個邊割集，則稱該邊為割邊或橋。 割邊e使圖G滿足W(G-e)>W(G) 。,§2路與回路,邊連通度(edge-connectivity) ? (G)定義：非平凡圖的邊連通度為 ? (G)=min{ |E1| | E1是G的邊割集} 邊連通度? (G)

22、是為了產(chǎn)生一個不連通圖需要刪去的邊的最少數(shù)目。,§2路與回路,(1)若G是平凡圖則?(G)=0(2)若G存在割邊，則?(G)=1， (3)規(guī)定非連通圖的邊連通度為?(G)=0,§2路與回路,定理： 對于任何一個圖G,有k(G)≤?(G)≤δ(G) 。,δ(G)=min(deg(v)，v?V),§2路與回路,若G不連通，則k(G)=?(G)=0，故上式成立。 若G連通，可分兩步證明上式也成立

23、： 1)先證明?(G)≤?(G)： 如果G是平凡圖，則?(G)=0≤?(G)， 若G是非平凡圖，則因每一結(jié)點的所有關(guān)聯(lián)邊必含一個邊割集，(因?(G)=min{deg(v)|v?V}，設(shè)u?V使的deg(u)=δ(G)，與u相關(guān)聯(lián)的?條邊必包含一個邊割集，至少這?條邊刪除使圖不連通。)故?(G)≤?(G)。,§2路與回路,2)再證k(G)≤?(G)：(a)設(shè)?(G)=1，即

24、G有一割邊，顯然這時k(G)=l，上式成立。,§2 路與回路,(b)設(shè)?(G)≥2，則必可刪去某?(G)條邊，使G不連通，而刪去其中?(G)-1條邊，它仍是連通的，且有一條橋e=(u，v)。對?(G)-1條邊中的每一條邊都選取一個不同于u，v的端點，把這些端點刪去則必至少刪去?(G)-1條邊。若這樣產(chǎn)生的圖是不連通的，則k(G)≤?(G)-1<?(G)，若這樣產(chǎn)生的圖是連通的，則e仍是橋，此時再刪去u或v就必產(chǎn)生一個

25、不連通圖，故k(G)≤?(G)。由1)和2)得k(G)≤?(G)≤?(G)。,§2路與回路,定理：一個連通無向圖G的結(jié)點v是割點的充分必要條件是存在兩個結(jié)點u和w,使得結(jié)點u和w的每一條路都通過v 。,§2路與回路,1) 先證:v是割點?存在結(jié)點u和w的每條路都通過v 若v是連通圖G=割點，設(shè)刪去v得到的子圖G’ , 則G’至少包含兩個連通分支G1=和G2= 。任取u?V1，w?V2，因為G是連通的，故在G中必

26、有一條連結(jié)u和w的路C，但u和w在G’中屬于兩個不同的連通分支，故u和w必不連通，因此C必須通過v，故u和w之間的任意一條路都通過v 。,§2路與回路,2)再證:存在結(jié)點u和w的每條路都通過v ?v是割點 若連通圖G中的某兩個結(jié)點的每一條路都通過v，則刪去v得到子圖G’ ，在G’中這兩個結(jié)點必然不連通，故v是圖G的割點。,§2路與回路,在無向圖G中，從結(jié)點u到v若存在一條路，則稱結(jié)點u到結(jié)點v是可達的。,

27、67;2路與回路,對于任何一個有向圖G=, 從結(jié)點u和到結(jié)點v有一條路,稱為從u可達v。 可達性(accesible),是結(jié)點集上的二元關(guān)系，它是自反的和傳遞的，但是一般來說不是對稱的。故可達性不是等價關(guān)系。,§2 路與回路,如果u可達v，它們之間可能不止一條路，在所有這些路中，最短路的長度稱為u和v之間的距離（或短程線），記作d，它滿足下列性質(zhì)： d≥0 d =0

28、 d + d ≥ d,§2路與回路,如果從u到v是不可達的，則通常寫成 d =∞注意：當(dāng)u可達v，且v也可達u時， d 不一定等于d,§2路與回路,有關(guān)距離的概念對無向圖也適用，把 D=max d, u,v∈V稱作圖的直徑。,§2 路與回路,定義: 在簡單有向圖G中，任何一對結(jié)點間，至少有一個結(jié)點到另一個結(jié)點是可達的，則稱這個圖是單側(cè)連通的 。,§2 路與回路,

29、如果對于圖G中的任何一對結(jié)點兩者之間是相互可達的，則稱這個圖是強連通的。 如果在圖G中略去邊的方向，將它看成無向圖后，圖是連通的，則稱該圖為弱連通的。 顯然，強連通圖→單側(cè)連通圖→弱連通圖。而逆推均不成立。,§2 路與回路,§2 路與回路,定理：一個有向圖是強連通的充分必要條件是G有一個回路，它至少包含每個結(jié)點一次。,§2 路與回路,證明：充分性：如G中有一條有向回路，經(jīng)過每一點至

30、少一次，則G中任意兩點u，v∈V，u可以沿著該有向回路的一部分的而到達v，則G是強連通圖。,§2 路與回路,必要性：任取u，v∈V，圖G是強連通圖，則u→v有有向路，v→u也有有向路，則u→v→u構(gòu)成了一個有向回路，如果該有向回路沒有包含w，而u→w，w→u均有有向路，則u→v→u→w→u又是一個有向回路，一直下去可以將圖中所有的點均包含進去。,§2 路與回路,定義： 在簡單有向圖中，具有強連通性質(zhì)的最

31、大子圖，稱為強分圖； 具有單側(cè)連通性質(zhì)的最大子圖，稱為單側(cè)分圖； 具有弱連通性質(zhì)的最大子圖，稱為弱分圖。,§2 路與回路,§2 路與回路,定理:在有向圖G=中，它的每一個結(jié)點位于且只位于一個強分圖中。,§3圖的矩陣表示,圖的鄰接矩陣表示方法 定義：設(shè)Ｇ＝＜Ｖ，Ｅ＞是簡單有向圖，其中V={v1,v2,…vn}定義一個nxn的矩陣A，并把其中各元素aij表示成：,,則稱矩陣A為圖G的

32、鄰接矩陣。,§3圖的矩陣表示,例：設(shè)圖Ｇ＝＜Ｖ，Ｅ＞如下圖所示 討論定義：（1）圖G的鄰接矩陣中的元素為0和1，∴又稱為布爾矩陣；（2）圖G的鄰接矩陣中的元素的次序是無關(guān)緊要的，只要進行行和行、列和列的交換，則可得到相同的矩陣。,§3圖的矩陣表示,∴若有二個簡單有向圖，則可得到二個對應(yīng)的鄰接矩陣，若對某一矩陣進行行和行、列和列之間的交換后得到和另一矩陣相同的矩陣，則此二圖同構(gòu)。,,,（3）當(dāng)有向圖中的有向邊

33、表示關(guān)系時，鄰接矩陣就是關(guān)系矩陣；（4）零圖的鄰接矩陣稱為零矩陣，即矩陣中的所有元素均為0；（5）在圖的鄰接矩陣中， ①行中1的個數(shù)就是行中相應(yīng)結(jié)點的引出次數(shù) ②列中1的個數(shù)就是列中相應(yīng)結(jié)點的引入次數(shù),§3圖的矩陣表示,２．矩陣的計算：,,,§3圖的矩陣表示,主對角線上的數(shù)表示結(jié)點i（或j）的引出次數(shù)。,,,主對角線上的數(shù)表示結(jié)點i（或j）的引入次數(shù)。,§3圖的矩陣表示,,,,,

34、,,,表示i和j之間具有長度為2的路徑數(shù)， 表示i和j之間具有長度為3的路徑數(shù)， 表示i和j之間具有長度為4的路徑數(shù)，,§3圖的矩陣表示,bij表示從結(jié)點vi到vj有長度分別為1，2，3，4的不同路徑總數(shù)。 此時， bij?0，表示從vi到vj是可達的。,,§3圖的矩陣表示,定義：設(shè)Ｇ＝＜Ｖ，Ｅ＞是簡單有向圖，其中|V|=ｎ（ ），定義一個 矩陣P，它的元素為

35、：則P稱為圖G的可達性矩陣。 由 可計算出可達性矩陣，其方法是：若 中（i ,j）是非“0”元素，則對應(yīng) ，否則 。,,,,,,,,,§3圖的矩陣表示,定義：設(shè)無向圖Ｇ＝＜Ｖ，Ｅ＞， 其中 ，則稱B為無向圖G的完全關(guān)聯(lián)矩陣。,,,,,

36、令,,可達矩陣表明了圖中任意兩結(jié)點間是否至少存在一條路以及在結(jié)點處是否有回路。 從圖G的鄰接矩陣A可以得到可達矩陣P，即令Bn=A+A2+A3+…+An，再從Bn中非零元素改為1而零元素不變，這種變換后的矩陣即是可達矩陣P。,§3圖的矩陣表示,例：,討論定義：（1）完全關(guān)聯(lián)矩陣為布爾矩陣；（2）對應(yīng)B中行均為0的結(jié)點為孤立結(jié)點，只有一個“1”的行的結(jié)點一定為懸掛的邊，且一定不在任一循環(huán)中全部為1的行的結(jié)點

37、必定聯(lián)結(jié)圖中所有的結(jié)點。,3) 每一條邊關(guān)聯(lián)兩個結(jié)點,故每一列中只有兩個1。 4) 每一行中元素之和等于該行對應(yīng)的結(jié)點的度數(shù)。 5) 兩個平行邊其對應(yīng)的兩列相同。 6) 同一個圖當(dāng)結(jié)點或邊的編號不同時，其對應(yīng)的矩陣只有行序列序的差別。,有向圖的關(guān)聯(lián)矩陣,有向圖的關(guān)聯(lián)矩陣的特點： (1)每一列中有一個1和一個-1，對應(yīng)一邊一個始點、一個終點，元素和為零。 (2)每一行元素的絕對值之和為對應(yīng)點的度數(shù)。-1的個數(shù)等于入

38、度，1的個數(shù)等于出度。,,,有向圖G的兩行相加定義為：第i行第j列的對應(yīng)元素算術(shù)相加；相當(dāng)于刪除結(jié)點vi與結(jié)點vj之間的關(guān)聯(lián)邊，合并結(jié)點vi和vj 。合并后得到的新結(jié)點記為vi,j 。 無向圖G的兩行相加定義為：第i行第j列的對應(yīng)元素模2相加；相當(dāng)于刪除結(jié)點vi與結(jié)點vj之間的關(guān)聯(lián)邊，合并結(jié)點vi和vj 。合并后得到的新結(jié)點記為vi,j 。,3、關(guān)聯(lián)矩陣的秩,定理： 如果一個連通圖G=,有r個結(jié)點,則其完全關(guān)聯(lián)矩陣M(G

39、)的秩為r-1,即rank M (G)=r-1 。,推論：如果一個連通圖G=,有r個結(jié)點,w個最大連通子圖,則圖G的完全關(guān)聯(lián)矩陣M(G)的秩為r- w,即rank M (G)=r-w 。,,例：寫出如圖7-3.11所示的圖G的完全關(guān)聯(lián)矩陣，并驗證其秩如定理7-3.2所述。,完全關(guān)聯(lián)矩陣為:,此圖為連通圖，由定理其秩為5。,§4 歐拉圖和漢密爾頓圖,2.定理7-4.1 無向圖G具有一條歐拉路，當(dāng)且僅當(dāng)G連通，并且有零個或

40、兩個奇數(shù)度結(jié)點。,1.定義7-4.1 如果無孤立結(jié)點圖G上有一條經(jīng)過G的所有邊一次且僅一次的路徑，則稱該路徑為圖G的歐拉路徑（Euler walk）。如果圖G上有一條經(jīng)過G邊一次且僅一次的的回路，則稱該回路為圖G的歐拉回路，具有歐拉回路的圖稱為歐拉圖（Euler graph）。,由于有了歐拉路和歐拉回路的判別準(zhǔn)則，因此哥尼斯堡七橋問題立即有了確切的否定答案，因為從圖中可以看到deg(A)＝5，deg(B)＝deg(C)＝deg(D)

41、=3，故歐拉回路必不存在。,3.定理7-4.1的推論 無向圖G具有一條歐拉路，當(dāng)且僅當(dāng)G連通且所有結(jié)點度數(shù)皆為偶數(shù)。,例：用定理解決哥尼斯堡橋的問題,一筆畫問題 要判定一個圖G是否可一筆畫出，有兩種情況：一是從圖G中某一結(jié)點出發(fā)，經(jīng)過圖G的每一邊一次僅一次到達另一結(jié)點。另一種就是從G的某個結(jié)點出發(fā)，經(jīng)過G的每一邊一次僅一次再回到該結(jié)點。上述兩種情況分別可以由歐拉路和歐拉回路的判定條件予以解決。,定義7-4.2：給

42、定有向圖G，通過圖中每邊一次且僅一次的一條單向路（回路），稱作單向歐拉路（回路）。,可以將歐拉路和歐拉回路的概念推廣到有向圖中。,定理7-4.2 有向圖G為具有一條單向歐拉回路，當(dāng)且僅當(dāng)G連通，并且每個結(jié)點的入度等于出度。有向圖G有單向歐拉路，當(dāng)且僅當(dāng)G連通，并且恰有兩個結(jié)點的入度與出度不等，它們中一個的出度比入度多1，另一個入度比出度多1。,例1有向歐拉圖應(yīng)用示例：計算機鼓輪的設(shè)計。 鼓輪表面分成24=16等份，其

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

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

45、上述方法，對于八個結(jié)點的有向圖共有16條邊，在這種圖的任一條路中，其鄰接的邊必是a1 a2 a3a4和a2 a3a4a5的形式，即是第一條邊標(biāo)號的后三位數(shù)與第二條邊的頭三位數(shù)相同。 由于圖中16條邊被記為不同的二進制數(shù)，可見前述鼓輪轉(zhuǎn)動所得到16個不同位置觸點上的二進制信息，即對應(yīng)于圖中的一條歐拉回路。,設(shè)有一個八個結(jié)點的有向圖，如下圖所示。其結(jié)點分別記為三位二進制數(shù){000，001，……，111}，設(shè)ai?{0,1}，從結(jié)點

46、a1 a2 a3可引出兩條有向邊，其終點分別是a2 a30以及a2 a31。該兩條邊分別記為a1 a2 a30和a1 a2 a31。按照上述方法，對于八個結(jié)點的有向圖共有16條邊，在這種圖的任一條路中，其鄰接的邊必是a1 a2 a3a4和a2 a3a4a5的形式，即是第一條邊標(biāo)號的后三位數(shù)與第二條邊的頭三位數(shù)相同。 由于圖中16條邊被記為不同的二進制數(shù)，可見前述鼓輪轉(zhuǎn)動所得到16個不同位置觸點上的二進制信息，即對應(yīng)于圖中的一條

47、歐拉回路。,所求的歐拉回路為： e0e1e2e4e9e3e6e13e10e5e11e7e16e14e12e8(e0) （從圖示位置開始） e13e10e5e11e7e16e14e12e8e0e1e2e4e9e3e6 (e13) 所求的二進制序列為： 0000100110101111 (0) 1101011110000100 (1) （從圖示位置開始）,上述結(jié)論可推廣到鼓輪具有

48、n個觸點的情況。構(gòu)造2n-1 個結(jié)點的有向圖，每個結(jié)點標(biāo)記為n-1位二進制數(shù),從結(jié)點a1a2a3...an-1出發(fā),有一條終點為a2a3...an-10的邊,該邊記為a1a2a3...an-10；還有一條終點標(biāo)記為a2a3...an-11的邊,該邊記為a1a2a3...an-11 。鄰接邊的標(biāo)記規(guī)則為：“第一條邊后n-1位與第二條邊前n-1位二進制數(shù)相同”。,二、漢密爾頓圖,與歐拉回路類似的是漢密爾頓回路。它是1859年漢密爾頓首先提出

49、的一個關(guān)于12面體的數(shù)學(xué)游戲：能否在圖7-4.6中找到一個回路，使它含有圖中所有結(jié)點一次且僅一次？若把每個結(jié)點看成一座城市，連接兩個結(jié)點的邊看成是交通線，那么這個問題就變成能否找到一條旅行路線，使得沿著該旅行路線經(jīng)過每座城市恰好一次，再回到原來的出發(fā)地？他把這個問題稱為周游世界問題。,定義7-4.3：給定圖G，若存在一條路經(jīng)過圖中的每個結(jié)點恰好一次，這條路稱作漢密爾頓路。若存在一條回路，經(jīng)過圖中的每個結(jié)點恰好一次，這條回路稱作漢密爾頓回

50、路。 具有漢密爾頓回路的圖稱作漢密爾頓圖。,圖7-4.6存在一條漢密爾頓回路，它是漢密爾頓圖,定理7-4.3 若圖G＝具有漢密爾頓回路，則對于結(jié)點集V的每個非空子集S均有W(G-S)≤|S|，其中W(G-S)是G-S的連通分支數(shù)。,證明 設(shè)C是G的一條漢密爾頓回路，對于V的任何一個非空子集S，在C中刪去S中任一結(jié)點a1，則C-a1是連通的非回路， W(C- a1)=1， |S|≥1，這時 W(C-S)≤|S|。 若再刪去S中

51、另一結(jié)點a2，則W(C-a1-a2)≤2，而 |S|≥2，這時 W(C-S)≤|S|。由歸納法可得：W(C-S)≤|S|。同時C-S是G-S的一個生成子圖，因而W(G-S)≤W(C-S)，所以W(G-S)≤|S|。,此定理是必要條件，可以用來證明一個圖不是漢密爾頓圖。,如右圖，取S={v1,v4}，則G-S有3個連通分支，,不滿足W(G-S)≤|S|，故該圖不是漢密爾頓圖。,所以用此定理來證明某一特定圖是非漢密爾頓圖并不是總是有效的。例

52、如，著名的彼得森(Petersen)圖，在圖中刪去任一個結(jié)點或任意兩個結(jié)點，不能使它不連通；刪去3個結(jié)點，最多只能得到有兩個連通分支的子圖；刪去4個結(jié)點，只能得到最多三個連通分支的子圖；刪去5個或5個以上的結(jié)點，余下子圖的結(jié)點數(shù)都不大于6，故必不能有5個以上的連通分支數(shù)。所以該圖滿足W(G-S)≤|S|，但是可以證明它是非漢密爾頓圖。,說明：此定理是必要條件而不是充分條件。有的圖滿足此必要條件，但也是非漢密爾頓圖。,下面的定理給出一個無

53、向圖具有漢密爾頓路的充分條件,定理7-4.4 設(shè)圖G具有n個結(jié)點的簡單圖,如果G中每一對結(jié)點度數(shù)之和大于等于n-1,則G中存在一條漢密爾頓路。,? 證明思路：1) 先證G連通: 若G有兩個或多個互不連通的分支,設(shè)一個分圖有n1個結(jié)點,任取一個結(jié)點v1,另一分圖有n2個結(jié)點,任取一個結(jié)點v2,因為deg(v1)≤n1-1, deg(v2)≤n2-1, deg(v1)+ deg(v2)≤n1+n2-2<n-1 ,與假設(shè)

54、矛盾, G是連通的。,2) 先證(構(gòu)造)要求的漢密爾頓路存在: 設(shè)G中有p-1條邊的路,p<n,它的結(jié)點序列為v1, v2,…, vp。如果有v1或vp鄰接于不在這條路上的一個結(jié)點,立刻擴展該路,使它包含這個結(jié)點,從而得到p條邊的路。否則v1和vp都只鄰接于這條路上的結(jié)點,我們證明在這種情況下,存在一條回路包含結(jié)點v1, v2,…, vp。,若v1鄰接于vp,則v1, v2, …, vp即為所求。 若v1

55、鄰接于結(jié)點集{vl,vm,…,…,vj,…,vt}中之一,這里2≤l,m,...,j,...,t≤p-1,如果vp是鄰接于vl-1,vm-1,…,…,vj-1, …,vt-1中之一,譬如是vj-1,則v1v2…vj-1vpvp-1...vjv1 是所求回路（如圖7-4.9(a)所示）。 如果vp不鄰接于vl-1,vm-1,…,…,vj-1, …,vt-1中任一個,則vp最多鄰接于p-k-1個結(jié)點, deg(vp)≤p-k-1

56、, deg(v1)=k,故deg(vp)+deg(v1)≤p-k-1+k<n-1,即v1與 vp 度數(shù)之和最多為n-2，得到矛盾。,至此，已經(jīng)構(gòu)造出一條包含結(jié)點v1,v2,…,vp的回路,因為G是連通的,所以在G中必有一個不屬于該回路的結(jié)點vx與回路中某一結(jié)點vk鄰接,如圖7-4.9(b)所示, 于是就得到一條包含p條邊的回路(vx,vk,vk+1,…,vj-1,vp,vp-1,…, vj,v1, v2 , …, vk

57、-1),如圖7-4.9(c)所示,重復(fù)前述構(gòu)造方法，直到得到n-1條邊的路。 ?,例 某地有5個風(fēng)景點，若每個景點均有兩條道路與其他景點相通，問是否可經(jīng)過每個景點一次而游完這5處。,解 將景點作為結(jié)點，道路作為邊，則得到一個有5個結(jié)點的無向圖。 由題意，對每個結(jié)點vi(i=1,2,3,4,5)有 deg(vi)=2。 則對任兩點和均有

58、 deg(vi) + deg(vj)=2 + 2 =4 = 5 – 1 所以此圖有一條漢密爾頓回路。即經(jīng)過每個景點一次而游完這5個景點。,例：在七天內(nèi)安排七門課程的考試，使得同一位教師所任的兩門課程不排在接連的兩天中，試證明如果沒有教師擔(dān)任多于四門課程，則符合上述要求的考試安排總是可能的。,證明：設(shè)G為具有七個結(jié)點的圖，每個結(jié)點對應(yīng)于一門課程考試，如果這兩個結(jié)點對應(yīng)的課程考試是由不同教師擔(dān)任的，那么這兩個結(jié)點之間有一條邊

59、，因為每個教師所任課程數(shù)不超過4，故每個結(jié)點的度數(shù)至少是3，任兩個結(jié)點的度數(shù)之和至少是6，故G總是包含一條漢密爾頓路，它對應(yīng)于一個七門考試課程的一個適當(dāng)?shù)陌才拧?4.定理7-4.5 設(shè)圖G具有n個結(jié)點的簡單圖,如果G中每一對結(jié)點度數(shù)之和大于等于n,則G中存在一條漢密爾頓回路。,? 證明思路：由定理7-4.4知,必有一條漢密爾頓路,設(shè)為v1,v2,…,vn,若v1與vn鄰接,則定理得證。 若v1與vn不鄰接,假設(shè)v1鄰接于{

60、vi1,vi2,…,vik}, 2≤ij≤n-1, vn必鄰接于vi1-1,vi2-1,…,vik-1中之一。若vn不鄰接于vi1-1,vi2-1,…,vik-1中之一,則vn至多鄰接于n-k-1個結(jié)點,因而, deg(vn)≤n-k-1,而 deg(v1)=k, deg(v1)+ deg(vn)≤n-k-1+k=n-1 ,與假設(shè)矛盾, 所以必有一條漢密爾頓路v1v2…vj-1vnvn-

61、1 …vjv1,如圖7-4.11所示。 ?,圖的閉包 定義7-4.4：給定圖G=有n個結(jié)點，若將圖G中度數(shù)之和至少是n的非鄰接結(jié)點連接起來得圖G’，對圖G’重復(fù)上述步驟，直到不再有這樣的結(jié)點對存在為止，所得到的圖，稱為是原圖G的閉包，記作C(G)。,定理7-4.6：當(dāng)且僅當(dāng)一個簡單圖的閉包是漢密爾頓圖時，這個簡單圖是漢密爾頓圖。推論：n?3的有向(無向)完全圖Kn為漢密爾頓圖。,判別漢密爾頓路不

62、存在的標(biāo)號法,關(guān)于圖中沒有漢密爾頓路的判別尚沒有確定的方法，下面通過一個例子，介紹一個判別漢密爾頓路不存在的標(biāo)號法。,例 證明下圖沒有漢密爾頓路。,證明 任取一結(jié)點如v1,用A標(biāo)記，所有與它鄰接的結(jié)點標(biāo)B。,繼續(xù)不斷地用A標(biāo)記所有與B鄰接的結(jié)點，用B標(biāo)記所有與A鄰接的結(jié)點，直到圖中的所有結(jié)點全部標(biāo)記完畢。,如果圖中有一條漢密爾頓路，則必交替通過結(jié)點A和B。因此或者結(jié)點A和B數(shù)目一樣，或者兩者相差1個。而本題有3個結(jié)點標(biāo)記A，5個結(jié)

63、點標(biāo)記B，它們相差2個，所以該圖不存在漢密爾頓路。,再看310頁例題2,遇到相鄰結(jié)點出現(xiàn)相同標(biāo)記，可在此對應(yīng)邊上增加一個結(jié)點，并標(biāo)上相異標(biāo)記。見圖7-4.14,練習(xí) 311頁（7）,有7個結(jié)點標(biāo)記A，6個結(jié)點標(biāo)記B，所以該圖不存在一條漢密爾頓回路。,311頁（6）,a)畫一個有一條歐拉回路和一條漢密爾頓回路的圖。,在無孤立結(jié)點圖G中，經(jīng)過圖中每條邊一次且僅有一次的一條回路，稱為歐拉回路。,給定圖G，經(jīng)過圖中每個結(jié)點恰好一次的回路稱作漢

64、密爾頓回路。,b)畫一個有一條歐拉回路，但沒有一條漢密爾頓回路的圖。,c)畫一個沒有一條歐拉回路，但有一條漢密爾頓回路的圖。,311頁（2）構(gòu)造一個歐拉圖，其結(jié)點數(shù)v和邊數(shù)e滿足下述條件,a)v，e的奇偶性一樣。b) v，e的奇偶性相反。 如果不可能，說明原因。,v=3,e=3,v=5,e=5,v=4,e=4,v=4,e=6,v=7,e=8,v=6,e=7,無向圖G具有一條歐拉回路，當(dāng)且僅當(dāng)G是連通的，并且所有結(jié)點度數(shù)全為偶數(shù)。下面

65、的圖中所有結(jié)點度數(shù)全為偶數(shù)，所以都是歐拉圖。,5.定義7-4.2：給定有向圖G，通過圖中每邊一次且僅一次的一條單向路（回路），稱作單向歐拉路（回路）。,可以將歐拉路和歐拉回路的概念推廣到有向圖中。,6.定理7-4.2 有向圖G為具有一條單向歐拉回路，當(dāng)且僅當(dāng)G連通，并且每個結(jié)點的入度等于出度。有向圖G有單向歐拉路，當(dāng)且僅當(dāng)G連通，并且恰有兩個結(jié)點的入度與出度不等，它們中一個的出度比入度多1，另一個入度比出度多1。 證

66、明思路與定理7-4.1類似,§4歐拉圖和漢密爾頓圖,《定理》：設(shè)G是一連通有向圖，則當(dāng)且僅當(dāng)G中每一個結(jié)點的 ＝ ，G才有歐拉循環(huán)；當(dāng)且僅當(dāng)除了二個結(jié)點（其中一個的引入次數(shù)比引出次數(shù)大１，另一個的引入次數(shù)比引出次數(shù)小１）以外的所有結(jié)點的 ＝ ，則圖G才有歐拉路徑。,§4歐拉圖和漢密爾頓圖,漢密爾頓路徑：穿程無向圖的每一個結(jié)點一次且僅一

67、次的路徑。漢密爾頓循環(huán)：穿程無向圖的每一個結(jié)點一次且僅一次的循環(huán)。漢密爾頓圖：具有漢密爾頓循環(huán)的圖。到目前為止，還沒有找到哈密爾頓路徑存在的充分必要條件。下面介紹兩個定理。,§4歐拉圖和漢密爾頓圖,《定理》：設(shè)Ｇ＝＜Ｖ，Ｅ＞是具有n 個結(jié)點的簡單無向圖，若在G中每對結(jié)點次數(shù)之和大于或等于(n-1)，則在G中一定存在一條漢密爾頓路徑。實際上，此定理只是充分條件，而不是充分必要條件。例：ｎ＝７，Ｇ＝＜Ｖ，Ｅ＞見圖：