《離散數(shù)學(xué)》課件第十章

1、圖 論（Graph Theory） 直觀地表示離散對象之間的相互關(guān)系，研究它們的共性和特性解決具體問題ACDB1發(fā)展歷史18世紀(jì)七橋問題(Euler 圖)圖論之父: 歐拉Euler2請你思考？如何找到物流運(yùn)輸?shù)淖顑?yōu)路徑？如何找到最優(yōu)的網(wǎng)絡(luò)通信線路？如果你想周游全國所有城市，如何設(shè)計(jì)旅游線路？化學(xué)化合物分析：結(jié)構(gòu)是否相同？程序結(jié)構(gòu)度量：程序是否結(jié)構(gòu)相似？如何為考試分配教室，使得資源利用率最優(yōu)？如何安排工作流程而達(dá)到最高效率？如何設(shè)計(jì)為眾多的電視臺頻道分配最優(yōu)方案？如何設(shè)計(jì)通信編碼以提高信息傳輸效率？操作系統(tǒng)中,如何調(diào)度進(jìn)程而使得系統(tǒng)效率最優(yōu)？3請你思考？如何設(shè)計(jì)集成電路線路布局而達(dá)到最優(yōu)效率？如

2、何設(shè)計(jì)計(jì)算機(jī)鼓輪？七枚同重量硬幣與一枚較輕的偽幣，使用天平秤多少次就能找出偽幣？如何設(shè)計(jì)下棋程序？n-皇后問題最少用幾種顏色就能將世界地圖都著色？如何使箱子盡可能裝滿物體？ 一個船夫要把一只狼，一只羊和一棵白菜運(yùn)過河。問題是當(dāng)人不在場時，狼要吃羊，羊要吃白菜，而他的船每趟只能運(yùn)其中的一個。那么他怎樣才能把三者都運(yùn)過河呢？ 4研究主題旅行商問題：TSP問題中國郵路問題地圖著色問題：四色定理最短路徑問題網(wǎng)絡(luò)流匹配組合優(yōu)化E.W.Dijkstra（1930-2002）5七橋問題ACDBA view of Knigsberg showing the seven bridges over the Riv

3、er Pregel 6學(xué)習(xí)重點(diǎn)基本術(shù)語數(shù)學(xué)模型理論證明（構(gòu)造性）了解應(yīng)用“現(xiàn)在應(yīng)該使圖的概念滲入所有的數(shù)學(xué)教學(xué)，圖表示了一個系統(tǒng)可能的狀態(tài)以及連接這些狀態(tài)的算子”B.Thwaites7主要內(nèi)容第1講 基本概念第2講 Euler圖與Hamilton圖 第3講 樹第4講 平面圖與圖著色第5講 二分圖與匹配8第1講 基本概念 1 基本術(shù)語 2 幾種重要類型的圖、圖的運(yùn)算 3 圖的基本性質(zhì) 4 完全圖、補(bǔ)圖 5 圖的同構(gòu) 6 子圖 7 圖的連通性 8 圖的表示910.2 圖與圖模型 例2 時間安排問題。某大學(xué)計(jì)算機(jī)學(xué)院的某教研組共有10名教師，他們分別參加7個班級的討論課，每個班級可能同時需要多位教師

4、參加，有的教師可能需要參加多個班級的討論，每個班級必須單獨(dú)開展討論課，則如何安排才使得所有班級在最短時間段內(nèi)完成討論課？參加各個班級討論課的教師情況如下（ci為班級編號，數(shù)字1-10為教師編號）： 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。 1010.2 圖與圖模型 這樣，一位教師如果給多個班級都授課，則在討論課時間安排方面則不能沖突，如教師1不能同時參加班級c1與班級c2的討論課。這種情況可以用下圖直觀地表示。 在上圖中，共用了7個小圓圈來表示班級，圓圈之間的線段表示存在同一個教師參加該二

5、班級的討論課，這樣就不能安排該二班級同時開展討論課。顯然，這就給上述問題構(gòu)建了一個直觀的圖的模型。 c6c5c4c2c3c7c111 1 基本術(shù)語圖的簡單表示：圖G是一個有序二元組（V，E），其中V=v1，v2，vn是一個有限非空的集合。V中的元素稱為G的結(jié)點(diǎn)，V稱為圖G的結(jié)點(diǎn)集，常記作V（G）； E是V中不同元素的無序偶(有序偶)的集合，E中的元素稱為G的邊，E稱為圖G的邊集，常記作E（G）。無向圖常簡稱為圖(Graph)，記為G：G = (,) 若|V|=n,|E|=m，可記G為(n,m)圖，G為n階(Order)圖。m表示圖G的規(guī)模（Size）。1210.2 圖與圖模型 在圖G中，若邊集

6、E(G)=,則稱G為零圖（Null Graph），此時，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖（Trivial graph）。在圖的定義中規(guī)定結(jié)點(diǎn)集V為非空集，但在圖的運(yùn)算中可能產(chǎn)生結(jié)點(diǎn)集為空集的運(yùn)算結(jié)果，為此規(guī)定結(jié)點(diǎn)集為空集的圖為空圖（Empty Graph），并將空圖記為。階為有限的圖稱為有限圖(Finite Graph)，否則稱為無限圖(Infinite Graph)。結(jié)點(diǎn)沒有標(biāo)號的圖稱為非標(biāo)號圖（Unlabeled Graph），否則為標(biāo)號圖（Labeled Graph）。 1310.2 圖與圖模型 如果圖中存在某兩條邊的端點(diǎn)都相同，則稱該圖為多重圖(Mul

7、tigraph)，該兩條邊稱為平行邊。如果一條邊關(guān)聯(lián)的兩個結(jié)點(diǎn)是相同的結(jié)點(diǎn)，則稱該邊為圈或自環(huán)(Loop)。不存在平行邊與圈的圖即稱為簡單圖(Simple Graph)。 1410.2 圖與圖模型 定義10.2 如果uv是圖G的邊，記為e，即uvE(G),則稱結(jié)點(diǎn)u和v鄰接(Adjacent),否則稱結(jié)點(diǎn)u與v非鄰接。這里，也稱結(jié)點(diǎn)u或v與邊e是關(guān)聯(lián)（Incident）關(guān)系。與同一個結(jié)點(diǎn)關(guān)聯(lián)的兩條邊稱為鄰接邊。與結(jié)點(diǎn)v關(guān)聯(lián)的邊數(shù)稱為結(jié)點(diǎn)v的度，記作deg(v)。與結(jié)點(diǎn)v關(guān)聯(lián)的環(huán)對v的度數(shù)的貢獻(xiàn)要計(jì)算兩次。如果結(jié)點(diǎn)v的度為0，則稱之為孤立點(diǎn)(Isolated Vertex)。一度的結(jié)點(diǎn)稱為懸掛點(diǎn)

8、（Pendant Vertex）。圖G的所有結(jié)點(diǎn)度數(shù)的最小度數(shù)稱為G的最小度，記作(G)，而所有結(jié)點(diǎn)度數(shù)的最大者稱為G的最大度，記作(G)。各結(jié)點(diǎn)的度均相同的圖稱為正則圖（Regular Graph）。各結(jié)點(diǎn)度均為k的正則圖稱為k-正則圖。 1510.2 圖與圖模型 定義10.3 如果圖的每條邊是二結(jié)點(diǎn)構(gòu)成的有序?qū)?，則該圖稱為有向圖(Directed Graph)，上文所定義的圖都是無向圖(Undirected Graph)。有向圖中邊uv與vu是兩條不同的邊，對于邊uv，稱u為始點(diǎn)，v為終點(diǎn)。 有向圖中，結(jié)點(diǎn)v的度分為入度，即與該結(jié)點(diǎn)相關(guān)聯(lián)并以該結(jié)點(diǎn)為終點(diǎn)的邊的數(shù)目，以及出度,即與該結(jié)點(diǎn)相關(guān)

9、聯(lián)并以該結(jié)點(diǎn)為始點(diǎn)的邊的數(shù)目,分別記作deg+(v)，deg-(v)。 1610.2 圖與圖模型v1v2e1e2v1v2e1e2無向圖有向圖17 1 基本術(shù)語環(huán)loop- (偽圖)非簡單圖simple graph邊e2(directed edge有向圖)關(guān)聯(lián)incident結(jié)點(diǎn)v1、v2，鄰接adjacent結(jié)點(diǎn)vertex/vertices(結(jié)點(diǎn))平行邊/重邊multiedge多重圖multigraph多重圖且偽圖擬圖(pseudograph)孤立點(diǎn)(isolated vertex)懸掛邊(pendant edge)懸掛點(diǎn)(pendant vertex)分離邊v3結(jié)點(diǎn)度degree為3,與3

10、個結(jié)點(diǎn)鄰接，1出度2入度v3v1v2e1e218 2 幾種重要類型的圖圖的類型：（1）有向圖/無向圖；簡單圖/多重圖/偽圖；零圖，平凡圖，空圖；有限圖/無限圖；帶權(quán)圖、標(biāo)記圖；（2）特殊圖：環(huán)圖(Cn)、輪圖(Wn)、立方圖(Qn)、網(wǎng)格、正則圖(r-圖)；偶圖(G(V1,V2), 二分圖/二部圖, Bipartite graph) 、完全偶圖(Km,n)；（3）特殊圖：子圖、完全圖、補(bǔ)圖（4）特殊圖：Euler圖、Hamilton圖、樹圖、平面圖19 3 圖基本性質(zhì)定理10.1（歐拉定理） （1）圖論第一定理（握手定理）：設(shè) 圖G =為無向圖或有向圖，V=v1, v2, ,vn, |E|=m

11、(m為邊數(shù))則 d(vi) = 2m.推論:任何圖(無向的或有向的)中,度為奇數(shù)的結(jié)點(diǎn)個為偶數(shù).20示例 1 已知圖G中有10條邊,4個3度結(jié)點(diǎn),其余結(jié)點(diǎn)的度數(shù)均小于等于2,問G中至少有多少個結(jié)點(diǎn)? 21 3 圖基本性質(zhì)（2）設(shè)有向圖D =,V =v1, v2, ,vn, |E| = m, 則有 d (vi) = d (vi) = m. 22 4 完全圖、補(bǔ)圖完全圖（Complete graph）、補(bǔ)圖n階無向完全圖：設(shè)G =是n階無向簡單圖,若G中任何結(jié)點(diǎn)都與其余的n1個結(jié)點(diǎn)相鄰。記作Kn.n階有向完全圖：設(shè)D =為n階有向簡單圖,若對于任意的結(jié)點(diǎn) , u,vV (u v) ,既有有向邊,又

12、有 示例 223 4 完全圖、補(bǔ)圖討論：完全圖性質(zhì)設(shè)無向完全圖G有n個結(jié)點(diǎn)，則G有n(n-1)/2條邊。24 4 完全圖、補(bǔ)圖絕對補(bǔ)圖，記為示例 325 5 子圖子圖(Subgraph)設(shè)G =,G =是兩個圖.若（1）V V,（2）E E,則稱 G 是G的子圖,G是 G 的超圖（母圖）,記作 G G.若G G且 G G(即 V V或 E E),則稱 G 是G的真子圖.若G G且 V V,則稱 G 是G的生成子圖.26 5 子圖導(dǎo)出子圖（Induced Subgraph） 設(shè) V1V,且 V1 ,以 V1為結(jié)點(diǎn)集,以兩端點(diǎn)均在V1中的全體邊為邊集的G的子圖,稱為結(jié)點(diǎn)集V1導(dǎo)出的導(dǎo)出子圖.設(shè) E

13、1 E,且 E1 ,以E1為邊集,以E1中邊關(guān)聯(lián)的結(jié)點(diǎn)的全體為結(jié)點(diǎn)集G的子圖,稱為邊集E1導(dǎo)出的導(dǎo)出子圖.27 5 子圖示例 8v1v2v1v4v1v2v2v4v3v1v2v3v2v1v3v3v2e4e5e4e5e1e3e2e4e1e3e1e3e1e3e2e1e4(1)(2)(3)(4)(5)(6)28 6 子圖示例 9 畫出完全圖K5的含4條邊的所有非同構(gòu)的生成子圖29 5 子圖示例 10 畫出有向完全圖K4的含2條邊的所有非同構(gòu)的生成子圖.30問題探討請你思考一個州的立法機(jī)關(guān)由許多委員會組成某些資深的立法委員身兼數(shù)職，因而各委員會的委員互相交迭。說明怎樣用圖來描述這種委員會委員的互相交迭如

14、果委員會A有委員（編號）1，3，5，6；B有2，4，8，10；C有1，7，9；D有2，5，8；E有2，4，10；F有 11，12，13試?yán)L出描述委員會委員互相交疊的圖。田徑賽的時間安排：假設(shè)某校的田徑選拔賽共設(shè)六個項(xiàng)目的比賽，即跳高、跳遠(yuǎn)、標(biāo)槍、鉛球、100米和200米短跑，規(guī)定每個選手至多參加三個項(xiàng)目的比賽現(xiàn)有七名選手報(bào)名。如果已知選手報(bào)名情況，請?jiān)O(shè)計(jì)一個比賽日程安排表，使得在盡可能短的時間內(nèi)完成比賽31問題探討假定有一個矩形國際象棋盤（代替標(biāo)準(zhǔn)的棋盤是否存在一連串符合規(guī)定的著法，使馬可以從某個指定的方格走到另一個指定的方格 在一個足球賽季中，某足球聯(lián)合會內(nèi)每兩隊(duì)間比賽一次，假定每次比賽結(jié)束

15、后總有一方獲勝（即無平局），如何用圖來表示該比賽的結(jié)局，即確定比賽名次。 3210.3 路徑與圖連通性 圖論中的許多概念和應(yīng)用都與對圖的遍歷有關(guān)，即是從一個結(jié)點(diǎn)u出發(fā)，到達(dá)與之相鄰接的結(jié)點(diǎn)，在從該鄰接結(jié)點(diǎn)出發(fā)到達(dá)其鄰接的結(jié)點(diǎn)，依次類推，最后可以到達(dá)圖中的某結(jié)點(diǎn)v，從而就得到一條從u到v的通路。3310.3 路徑與圖連通性 如果通路上首尾結(jié)點(diǎn)相同，則稱該通路是閉的(Closed)，否則稱該通路是開的(Opened)。如果通路上沒有相同的邊，則稱該通路為跡(Trail)，如果跡上的開始結(jié)點(diǎn)與結(jié)束結(jié)點(diǎn)相同，則稱之為回路(Circuit)，如果回路上除了開始結(jié)點(diǎn)與結(jié)束結(jié)點(diǎn)沒有相同的結(jié)點(diǎn)，則稱之為環(huán)(C

16、ycle)。如果通路上沒有相同的結(jié)點(diǎn)，則稱該通路為路或路徑(Path)，有n個結(jié)點(diǎn)的路常記作Pn。 3410.3 路徑與圖連通性 通路遍歷過的邊的數(shù)目為通路的長度，如果通路長度為0，則稱之為平凡通路（Trivial Walk）。兩結(jié)點(diǎn)u，v間的路可能不只一條，將其中的最短的路稱為u，v間的距離。3510.3 路徑與圖連通性 定理10.2 如果圖G上存在一條u-v通路，則必然存在一條u-v路；如果G上存在一條閉通路，則必然存在一條回路(環(huán))。 這是因?yàn)椋绻飞洗嬖谙嗤慕Y(jié)點(diǎn)vi,vj，則可將vi,vj之間的一段通路刪除，并合并vi，vj為一個結(jié)點(diǎn)，從而得到一條更短的u-v通路。如果所得到的u

17、-v通路上還存在相同的結(jié)點(diǎn)，則可以依此繼續(xù)執(zhí)行刪除操作，最終一定可以得到一條沒有相同結(jié)點(diǎn)的u-v通路，也就是一條u-v路。類似地，如果G上存在一條閉通路，則必然存在一條回路（環(huán)）。 3610.3 路徑與圖連通性例10.11 在右圖中，1) 找出一條包含圖所有結(jié)點(diǎn)的通道；2) 找出一條包含圖所有結(jié)點(diǎn)的跡； 3) 找出所有a-d路，并求出其長度；4) 找出圖中所有的環(huán)。解 1) 包含圖所有結(jié)點(diǎn)的不是跡的通道：aebcaebd。2) 包含所有結(jié)點(diǎn)的跡：beacbd。3) a-d路：aebd,acbd,長度均為3。4) 環(huán)：acbea，長度為4。abedc3710.3 路徑與圖連通性 例10.12 每

18、個結(jié)點(diǎn)的度數(shù)至少為2的圖必包含一個回路。 證明 設(shè)P是圖G中最長路經(jīng)中的一條，并設(shè)其長度為m, P的一個端點(diǎn)為u?？疾霨中與u關(guān)聯(lián)的邊，由于G中每個結(jié)點(diǎn)的度至少為2，故u必關(guān)聯(lián)一條不在P上的邊e，從而e的另一個端點(diǎn)v必然在P上，否則，將這個結(jié)點(diǎn)加入P上，則可以得到更長的路。于是，P上u到v的的路與邊e構(gòu)成回路。 uvP3810.3 路徑與圖連通性 練習(xí)4 已知關(guān)于a,b,c,d,e,f,g的下述事實(shí)： a說英語； b說英語和西班牙語； c說英語、意大利語和俄語； d說日語和西班牙語； e說德語和意大利語； f說法語、日語和俄語； g說法語和德語； 試問：上述7人中是否任意兩人都能交談（如果必要

19、，可由其余5人中所組成的譯員鏈幫忙？）39407 圖的連通性討論1 Dijkstra算法輸入：一個帶權(quán)圖G，G的任意兩個結(jié)點(diǎn)間有路徑存在，G中任意邊(v,x)的權(quán)值w(v,x)0；結(jié)點(diǎn)a與z輸出：L(z)，從結(jié)點(diǎn)a到z的最短路徑長度1 Procedure Dijkstra(G)2 For 所有結(jié)點(diǎn)xa 3 L(x)=; 4End for;5 L(a)=0;6 T=V(G);7S=;8 While(zT)9 從T中找出具有最小L(v)的結(jié)點(diǎn)v;10 For 所有與v相鄰的結(jié)點(diǎn)uT11 L(u)=minL(u),L(v)+w(v,u)12 End For13 T=T-v;14 S=Sv;15 En

20、d While16 End Procedure41 ()()()()()(0) v1 v2 v3 v4az42(4)(2)()()()(0) v1 v2 v3 v4az43(3)(2)(10)(12)()(0) v1 v2 v3 v4az44(3)(2)(8)(12)()(0) v1 v2 v3 v4az45(3)(2)(8)(10)(14)(0) v1 v2 v3 v4az46(3)(2)(8)(10)(13)(0) v1 v2 v3 v4az47(3)(2)(8)(10)(13)(0) v1 v2 v3 v4az48 10.3 路徑與圖連通性 定義10.5 如果圖G中結(jié)點(diǎn)u到v有一條路徑，

21、則稱結(jié)點(diǎn)u到v是可達(dá)的（Accesible）或連通的（Connected）。結(jié)點(diǎn)u到其自身也定義為連通的。 定義10.6 如果圖G的任何兩個結(jié)點(diǎn)都是相互可達(dá)的，稱G是連通的（Connected）,并稱G為連通圖(Connected Graph)。有向連通圖 弱連通、單向連通、強(qiáng)連通圖4910.3 路徑與圖連通性 容易判斷，強(qiáng)連通圖必定是單向連通圖，單向連通圖必定是弱連通圖。 例10.14 下圖中，(a)為連通圖，(b)為由兩個連通分支的非連通圖，c為強(qiáng)連通圖，d為單向連通圖，e為弱連通圖。 a b c d e5010.3 路徑與圖連通性 若將圖中兩個結(jié)點(diǎn)間的連通性看作圖的結(jié)點(diǎn)間的一種關(guān)系，容易

22、判定圖中兩個結(jié)點(diǎn)間的連通性是一個等價關(guān)系，因?yàn)榻Y(jié)點(diǎn)u到u是連通的滿足自反性；若u到v是連通的，則v到u也是連通的，滿足對稱性；若u到v連通，v到w連通，則u到w存在一條通路，從而存在一條u到w的路徑，故u到w是連通的，滿足傳遞性。但對于有向圖，結(jié)點(diǎn)間的連通性不滿足對稱性，是偏序關(guān)系。 5110.3 路徑與圖連通性 現(xiàn)在可以利用結(jié)點(diǎn)的連通性對圖G的結(jié)點(diǎn)集進(jìn)行劃分，于是利用這個劃分可以得到G的多個連通子圖，如 Gv=(Vv,Ev), 稱Gv為G的連通分支或連通分圖（Connected Component）,也稱為極大連通子圖。 52 10.3 路徑與圖連通性討論：連通圖有關(guān)性質(zhì)1 （定理10.3）

23、設(shè)G是一(n，m)圖，G有個分圖，則 n-m(n-)(n-+1)/22 二分圖G中無長度為奇數(shù)的環(huán)。3 有向圖D強(qiáng)連通 D中有閉通路過每個結(jié)點(diǎn)至少一次.4 有向圖D單向連通 D中有通路過每個結(jié)點(diǎn)至少一次.53 7 圖的連通性3 證明: () 顯然 () 設(shè)V(D)=v1,v2,vn, 設(shè)i,j是從vi到vj的有向路徑, 則1,2+2,3+n-1,n+n,1是過每個結(jié)點(diǎn)至少一次的閉通路. 思考：進(jìn)一步地，一定存在滿足條件的環(huán)？請舉例。5410.3 路徑與圖連通性 練習(xí)5在任何n (n2)個頂點(diǎn)的簡單圖G中，至少有兩個頂點(diǎn)具有相同的度。 證明 如果G有兩個或更多孤立頂點(diǎn)，那么它們便是具有相同的度的

24、兩個頂點(diǎn)。 如果G恰有一個孤立頂點(diǎn)，那么我們可對有n1 個頂點(diǎn)但沒有孤立頂點(diǎn)的G（它由G刪除孤立頂點(diǎn)后得到）作討論；如果G有分圖，則也可以直接對分圖進(jìn)行討論。因此，不妨設(shè)G沒有孤立頂點(diǎn)，那么G 的n個頂點(diǎn)的度數(shù)應(yīng)是：1，2，3，n1 這n1種可能之一，顯然，必定有兩個頂點(diǎn)具有相同的度。5510.3 路徑與圖連通性 練習(xí)6給定簡單圖G=，且|V|=n，|E|(n-1)(n-2)/2，試證G是連通圖。試給出|V|=n，|E|=(n-1)(n-2)/2的簡單無向圖G=是不連通的例子。 5610.3 路徑與圖連通性 定義10.9 設(shè)S為圖G的結(jié)點(diǎn)集V的子集，稱S為G的點(diǎn)割集（Cut Set of Ve

25、rtex）,如果從G中刪除S中的所有結(jié)點(diǎn)后G的連通分支數(shù)增加，但S的任何真子集均無這一特性。當(dāng)點(diǎn)割集為單元素集合v時，v稱為割點(diǎn)（Cut Vertex）。 設(shè)S為連通圖G邊集E的子集，稱S為G的邊割集（Cut set of Edge），如果從G中刪除S的所有邊后G的連通分支數(shù)增加，但S的任何真子集均無這一特性。當(dāng)割集為單元素集e時，稱e為橋(Bridge)或割邊（Cut Edge）。 5710.3 路徑與圖連通性 例10.17 下圖中的圖有點(diǎn)割集1，5，2，3是割點(diǎn)，而4，7不是點(diǎn)割集。e1,e3,e4,e5,e6,e8等均是邊割集，e9是割邊。126735e1e3e2e4e7e8 e64e9

26、e55810.3 路徑與圖連通性 例10.18 試證明：圖G的任一邊，若其不是割邊，則必出現(xiàn)于G的某一環(huán)里。 證明 設(shè)圖G的邊e=(vi，vj)不是分割邊，去掉e后，與vi相連接的接點(diǎn)集為V1，與vj相連接的結(jié)點(diǎn)集為V2，由割邊定義知，V1V2。因而存在一結(jié)點(diǎn)vV1V2，使得在去掉e后，vi與v有路相連，v與vj有路相連。于是vi與vj有路相連接，因而必存在一條連接vi與vj的路P=vi，v1，v2，v，vj，從而P與邊(vi，vj)組成一個環(huán)。 5910.3 路徑與圖連通性 定義10.10 圖G的點(diǎn)連通度（Vertex Connectivity）是指把G變成非連通圖或平凡圖至少要刪除的結(jié)點(diǎn)數(shù)

27、，記作(G) (讀作卡帕)。定義中的平凡圖主要針對G為完全圖時而言的，因?yàn)橥耆珗D無論刪除多少結(jié)點(diǎn)都不會變得不連通。根據(jù)定義，(G)可以具體定義如下：(G)= 6010.3 路徑與圖連通性 類似地，有邊連通度的定義。G的邊連通度（Edge Connectivity）是指把G變成非連通圖或平凡圖至少要刪除的邊數(shù)，記作(G)。根據(jù)定義，當(dāng)G為非連通圖或?yàn)镵1時(G)=0。 例10.17中圖的點(diǎn)連通度為1，邊連通度為1。 顯然，點(diǎn)（邊）連通度越小，圖的連通性越脆弱。 6110.3 路徑與圖連通性 令(G)表示圖G中結(jié)點(diǎn)度數(shù)的最小值（常稱圖G的最小度），那么我們有以下定理。 定理10.4 對于圖G，有下

28、面不等式成立： (G)(G)(G) 從直觀上看，圖的連通度應(yīng)當(dāng)與圖中任兩點(diǎn)之間的路的條數(shù)有關(guān)。連通度越高，連接兩點(diǎn)的路應(yīng)當(dāng)越多。 6210.3 路徑與圖連通性 定義10.11 設(shè)G=(V，E)是連通圖，SV，u，vV。若在G-S中u，v不可達(dá)，則稱S分離u，v。設(shè)FE，若在G-F中u，v不可達(dá)，則稱F分離u，v。 定理10.5 在一個連通(p，q)圖中，分離兩個不相鄰接的點(diǎn)u，v的點(diǎn)集中，點(diǎn)的最少數(shù)目等于連接u，v的不相交的路的最多數(shù)。 6310.3 路徑與圖連通性 證明 設(shè)G=(p，q)，u，v是G中任二不相鄰的結(jié)點(diǎn)，且分離u，v的點(diǎn)集至少有k個點(diǎn)，連接u，v的不相交的路(點(diǎn)不相重)共有m條

29、。 1) 因?yàn)檫B接u，v的不相交的路共有m條，這m條路除端點(diǎn)外無公共點(diǎn)，所以要分離u，v，至少要從每一條路上去掉一個點(diǎn)，即mk。 2) 若分離u，v的點(diǎn)集中至少要k個點(diǎn)，而連接u，v的路共有m條，則只要在這m條互不相交的路上各取一點(diǎn)，即可組成一個由m個點(diǎn)組成的點(diǎn)集S，S分離u，v。所以km。 由(1)、(2)結(jié)論可得k=m。證畢。 6410.3 路徑與圖連通性 定理10.6 若u，v是圖G中兩個不同的點(diǎn)，G中連接u，v的邊不相交的路的最多數(shù)目，等于分離u，v的邊集中邊的最少數(shù)目。 以上兩個定理屬于Menger定理的圖論形式。Menger定理具有普遍意義，它的圖論形式還有多種。并且，在其它領(lǐng)域中

30、，類似的定理也被一再發(fā)現(xiàn)。例如，網(wǎng)絡(luò)最優(yōu)化理論中有名的最大流最小割定理、集族理論中的霍爾定理、格論中關(guān)于有限格中不可比元素的數(shù)目等于包含所有元素的鏈集中鏈的最少數(shù)的定理，等等。這些定理從不同領(lǐng)域中發(fā)現(xiàn)，相互之間有著內(nèi)在聯(lián)系，它們都是Menger定理的變形。 65 10.5 圖的同構(gòu)圖的同構(gòu)定義10.12 設(shè)(有向)圖G1=, G2=, 若存在雙射 f:V1V2, 滿足 uV1,vV1, (u,v)E1 (f(u),f(v)E2(E1 E2)則稱G1與G2同構(gòu), 記作G1G266 10.5 圖的同構(gòu)示例 5(1)(2)(3)(4)(5)(6)abcdev1v2v3v4v567 10.5 圖的同構(gòu)

31、示例 6G1G2G3G1G3, G1G268 10.5 圖的同構(gòu)示例 7G1G2G3G1G2G369 10.5 圖的同構(gòu)示例 7G1G2G3G1G2, G2G370 10.5 圖的同構(gòu)示例 9 畫出完全圖K5的含4條邊的所有非同構(gòu)的生成子圖71 10.5 圖的同構(gòu)思考：（1）畫出4個結(jié)點(diǎn)3條邊的所有可能非同構(gòu)無向簡單圖；（2）畫出3個結(jié)點(diǎn)2條邊的所有可能非同構(gòu)的有向簡單圖;（3）如何判定兩個圖不同構(gòu)？72 10.5 圖的表示圖的矩陣表示圖的表示的三種方法：（1）集合表示（2）鄰接表（adjacency list）表示（3）矩陣（ matrix）表示 1、鄰接矩陣（adjacency matri

32、x）表示 2、關(guān)聯(lián)矩陣（incidence matrix）表示7310.5 圖的表示示例 鄰接矩陣及其應(yīng)用aedcbA(G)= ca b c d eA(G)2=7410.5 圖的表示定理10.7 如果A是一個圖G的鄰接矩陣，那么An（n=1，2，3，）中元素(ij)等于從結(jié)點(diǎn)i到結(jié)點(diǎn)j的長度為n的通路的數(shù)目。7510.6 歐拉圖 Euler Graph定義：歐拉圖:圖中存在一條經(jīng)過每條邊一 次且僅一次的回路。歐拉路：經(jīng)過圖中每邊一次且僅一次的通路。7610.6 歐拉圖 Euler Graph哥尼斯堡七橋問題7710.6 歐拉圖 Euler Graph781 歐拉圖哥尼斯堡七橋問題 尋找走遍哥尼

33、斯堡（Knigsberg）城的七座橋一次且僅一次最后又回到原出發(fā)點(diǎn)的路是否存在.研究方法抽象 將哥尼斯堡七橋問題抽象為一個數(shù)學(xué)問題.791 歐拉圖A view of Knigsberg showing the seven bridges over the River Pregel CADB？ABCD802 歐拉圖的判定歐拉圖判定定理 圖G具有一條歐拉回路（即G為歐拉圖），當(dāng)且僅當(dāng)G是連通的，并且所有結(jié)點(diǎn)度數(shù)均為偶數(shù)。812 歐拉圖的判定A view of Knigsberg showing the seven bridges over the River Pregel CADB822 歐拉圖的

34、判定示例 請判斷下列各圖中，哪些是歐拉圖？832 歐拉圖的判定歐拉圖判定定理的證明v0構(gòu)造法842 歐拉路的判定 圖G具有一條歐拉路，當(dāng)且僅當(dāng)G是連通的，且有零個或兩個奇數(shù)度結(jié)點(diǎn)。兩個奇數(shù)度結(jié)點(diǎn)是歐拉路的兩個端點(diǎn)。853 歐拉圖的應(yīng)用 1 一筆畫問題 示例2 試問下列各圖能否一筆畫出？ 請你思考：完全圖Kn可以幾筆畫出？863 歐拉圖的應(yīng)用2 “街道清掃車”小區(qū)大門873 歐拉圖的應(yīng)用2 “街道清掃車”小區(qū)大門21883 歐拉圖的應(yīng)用推廣之：中國郵路問題 一個郵遞員從郵局出發(fā)，到所管轄的街道投遞郵件，最后返回郵局，若必須走遍所轄各街道中每一條至少一次，則怎樣選擇投遞路線使所走的路程最短？ 89

35、3 歐拉圖的應(yīng)用我國的數(shù)學(xué)家管梅谷教授，于1962年寫出了論文解決了這一問題，被國際數(shù)學(xué)界稱之為中國郵路問題。它的解題思路大體包括三個方面：第一 若G沒有奇數(shù)度結(jié)點(diǎn)，則G是歐拉圖，于是歐拉回路C是唯一的最小長度。第二 若G恰有兩個奇數(shù)度結(jié)點(diǎn)vi和vj，則G具有歐拉路，且郵局位于結(jié)點(diǎn)vi，則郵遞員走遍所有的街道一次到達(dá)結(jié)點(diǎn)vj；從vj返回vi可選擇其間的一條最短路徑。這樣，最短郵路問題轉(zhuǎn)化為求vi到vj的歐拉路和vj到vi的最短路徑問題。第三 若G中奇數(shù)度結(jié)點(diǎn)數(shù)多于2，則回路中必須增加更多的重復(fù)邊(路徑）。這時，怎樣使重復(fù)邊的總長度最??？有定理給出了判斷條件。 904 有向歐拉圖有向歐拉回路（跡

36、）: 給定有向圖G，通過圖中每邊一次且僅一次的一條有向回路(跡)。存在有向歐拉回路（跡）的圖即有向歐拉圖（有向半歐拉圖）。判定？有向圖G為有向歐拉圖，當(dāng)且僅當(dāng)G是連通的，且每個結(jié)點(diǎn)入度等于出度。一個有向圖G為有向半歐拉圖，當(dāng)且僅當(dāng)它是連通的，而且除兩個結(jié)點(diǎn)，每個結(jié)點(diǎn)入度等于出度，但這兩個結(jié)點(diǎn)中，一個結(jié)點(diǎn)的入度比出度大1，另一個結(jié)點(diǎn)的入度比出度小1。914 有向歐拉圖計(jì)算機(jī)鼓輪的設(shè)計(jì) 設(shè)有旋轉(zhuǎn)鼓輪其表面被等分成24個部分。 其中每一部分分別用絕緣體或?qū)w組成，絕緣體部分給出信號0，導(dǎo)體部分給出信號1，圖中陰影部分表示導(dǎo)體，空白部分表示絕緣體，根據(jù)鼓輪的位置，觸點(diǎn)將得到信息1101，如果鼓輪沿順時

37、針方向旋轉(zhuǎn)一個部分，觸點(diǎn)將有信息1010。 問鼓輪上16個部分怎樣安排導(dǎo)體和絕緣體，才能使鼓輪每旋轉(zhuǎn)一個部分，四個觸點(diǎn)能得到一組不同的四位二進(jìn)制數(shù)信息。924 有向歐拉圖的應(yīng)用每個結(jié)點(diǎn)的入度等于2，出度等于2，故在圖中必可找到一條歐拉回路如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8根據(jù)鄰接邊的標(biāo)號記法，這16個二進(jìn)制數(shù)可寫成對應(yīng)的二進(jìn)制數(shù)序列 0000100110101111把這個序列排成環(huán)狀，即與所求的鼓輪相對應(yīng). 0100101101010193小結(jié)與作業(yè)小結(jié)1 歐拉圖2 歐拉圖的判定3 應(yīng)用作業(yè) 習(xí)題 26、27 構(gòu)造法94哈密爾頓圖Hamilton G

38、raph95主要內(nèi)容 1 哈密爾頓圖2 哈密爾頓圖判定定理3 建模：哈密爾頓圖應(yīng)用重點(diǎn)難點(diǎn)：哈密爾頓圖判定定理961 哈密爾頓圖幾個問題在一個大城市，有很多取款機(jī)，那么，如何制定出一個最優(yōu)的路線，使運(yùn)鈔車過每個提款機(jī)一次就能運(yùn)送完錢鈔？ 貨郎擔(dān)問題旅行商人問題 (Traveling Salesman Problem ,TSP) 優(yōu)化算法近似解演化算法運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多問題都可以轉(zhuǎn)化為哈密爾頓圖問題 971 哈密爾頓圖幾個問題在一個大城市，有很多取款機(jī)，那么，如何制定出一個最優(yōu)的路線，使運(yùn)鈔車過每個提款機(jī)一次就能運(yùn)送完錢鈔？ 貨郎擔(dān)問題旅行商人問題(TSP)考慮在七天內(nèi)安排七門

39、課程的考試，要求同一位教師所任教的兩門課程考試不安排在接連的兩天里，如果教師所擔(dān)任的課程都不多于四門，則是否存在滿足上述要求的考試安排方案？ 時間表問題國際象棋的跳馬是否可以遍歷其棋盤，即從任一格出發(fā)跳到每一格僅一次并最后回到出發(fā)的棋盤格子？在一個至少有5人出席的圓桌會議上（會議需要舉行多次），為達(dá)到充分交流的目的，會議主持者希望每次會議每人兩側(cè)的人均與前次不同，這是否可行？請應(yīng)用圖論知識進(jìn)行論證。 周游世界問題981 哈密爾頓圖問題 1859年愛爾蘭數(shù)學(xué)家威廉哈密爾頓（Sir William Hamilton）發(fā)明了一個小游戲玩具：一個木刻的正十二面體，每面系正五角形，三面交于一角，共有20

40、個角，每角標(biāo)有世界上一個重要城市。哈密爾頓提出一個問題：要求沿正十二面體的邊尋找一條路通過20個城市，而每個城市只通過一次，最后返回原地。哈密爾頓將此問題稱為周游世界問題。游戲) 求解 抽象為圖論問題 哈密爾頓給出了肯定回答，該問題的解是存在的哈密爾頓回路(圈)哈密爾頓圖991 哈密爾頓圖2002年“離散數(shù)學(xué)與計(jì)算機(jī)科學(xué)研究中心”在福州大學(xué)成立范更華教授獲2005年度國家自然科學(xué)獎二等獎 研究主題：哈密爾頓圈及圈覆蓋理論 “范定理” ( “范條件”、“范類型”)1001 哈密爾頓圖范更華：歪打正著學(xué)了圖論 靈光一閃發(fā)現(xiàn)定理科學(xué)中國人（2005）年度人物哈密爾頓圈問題是圖論最古老的研究課題之一，

41、是至今未解決的世界難題，在許多領(lǐng)域有著重要應(yīng)用。經(jīng)過多年艱苦攻克，范更華的這一項(xiàng)目在這一問題的研究上開辟 了一條新的途徑，證明若圖中每對距離為2的點(diǎn)中有一點(diǎn)的度數(shù)至少是圖的點(diǎn)數(shù)的一半，則該圖存在哈密爾頓圈。了此成果引發(fā)了大量后續(xù)工作，以“范定理”、“范 條件”、“范類型”被廣泛引用而出現(xiàn)于多種國際權(quán)威學(xué)術(shù)刊物，并作為定理出現(xiàn)在國外的教科書中。 新華網(wǎng) 2006.1.101011 哈密爾頓圖哈密爾頓回路(H-回路): 一條經(jīng)過圖G中的每一個結(jié)點(diǎn)恰好一次的回路(環(huán))哈密爾頓圖(Hamilton Graph, H-圖): 具有哈密爾頓回路的圖哈密爾頓路(H-路): 一條經(jīng)過圖G中的每一個結(jié)點(diǎn)恰好一次

42、的路(通路)半哈密爾頓圖1021 哈密爾頓圖示例 請判斷下列各圖中，哪些是哈密爾頓圖？（a） (b) (c) abcde1031 哈密爾頓圖哈密爾頓圖性質(zhì)若圖G=(V，E) 具有哈密爾頓回路，則對于結(jié)點(diǎn)集V的每一個非空子集S均有(GS)|S|成立。其中(GS)是GS中連通分支數(shù)。哈密爾頓圖的必要條件也是判定非哈密爾頓圖的充分條件1041 哈密爾頓圖88馬圖(能否遍歷是否是H圖?)跳馬的步數(shù)1-64，構(gòu)成一個幻 方 1051 哈密爾頓圖 44馬圖 55馬圖1062 哈密爾頓圖判定定理(充分條件)定理10.10 設(shè)圖G為具有n(n3)個結(jié)點(diǎn)的簡單無向圖，1 如果G的每一對結(jié)點(diǎn)的度數(shù)之和都不小于n1

43、，那么G中有一條哈密爾頓通路； 2 如果G的每一對不相鄰結(jié)點(diǎn)的度數(shù)之和不小于n，那么G為一哈密爾頓圖。 “范定理”:若圖中每對距離為2的結(jié)點(diǎn)中有一結(jié)點(diǎn)的度數(shù)至少是圖的結(jié)點(diǎn)數(shù)的二分之一，則該圖存在哈密爾頓回路(環(huán)/圈)。1072 哈密爾頓圖判定定理判定定理1的證明首先，G是連通的? 若G有兩個或更多互不連通的分圖，設(shè)一個分圖有n1個結(jié)點(diǎn)，任取一個結(jié)點(diǎn)v1，設(shè)另一個分圖有n2個結(jié)點(diǎn)，任取一個結(jié)點(diǎn)v2，由 d(v1)n11，d(v2)n21，有 d(v1)+ d(v2) n1+ n22n1，這表明與題設(shè)矛盾，故G必連通。108其次，G有哈密爾頓通路？ 只要在G中構(gòu)造出一條長為n1的H-通路即可得證。

44、 為此，不妨令P為G中任意一條長為p1(pn)的H-通路，設(shè)其結(jié)點(diǎn)序列為v1，v2，vp。反復(fù)應(yīng)用下面方法來擴(kuò)充這一通路，直到P長度為n-1： 1）如果有v v1，v2，vp，它與v1或vp有邊相關(guān)聯(lián)，那么可立即擴(kuò)充P為長度為p的通路。 2）如果v1，vp均只與原通路P上的結(jié)點(diǎn)相鄰，則首先證明：G中有一條包含v1，v2，vp，長度為p的回路。 2.1) 如果v1與vp相鄰，則回路已找到。否則2 哈密爾頓圖判定定理1092 哈密爾頓圖判定定理 2.2) 如果v1與vi1 ,vi2 , ,vir相鄰，1i1，i2, , irp, 考慮vp： 若vp不與vi1-1 ,vi2-1 , , vir-1中

45、任何一個相鄰，則deg(vp)p-r-l， 因而 deg(v1)+deg(vp)r+prl=p1n1，與題設(shè)矛盾， 因此 vp與vi1-1 ,vi2-1 , , vir-1之一, 例如vi1-1相鄰， 于是,可得到包含v1，v2，vp 的回路：（v1，v2，vi1-1 ,vp , vp -1 , ，vi1 , v1）如圖所示。v1vpv2vi-1vi1102 哈密爾頓圖判定定理考慮G中這條包含v1，v2，vp長度為p的回路。 由于pn，故必有回路外結(jié)點(diǎn)v與回路上結(jié)點(diǎn)(例如vk)相鄰，如圖所示，可以得到一條長度為p的、包含v1，v2，vp的通路：(v, vk ,vk-1, v1,vi1 ,vi1

46、+1, vp ,vi1-1 , vk+1)。v1vpv2vkvk+1vvi-1vi1112 哈密爾頓圖判定定理請你思考 如何證明判定定理2？1 按照上述證明方法？2 其它方法，如教材方法？構(gòu)造法反證法1122 哈密爾頓圖判定定理練習(xí) 1 結(jié)點(diǎn)數(shù)目不少于3的完全圖都是哈密爾頓圖？ 2 哈密爾頓圖中的哈密爾頓回路未必是唯一的嗎？ 3 每個結(jié)點(diǎn)度數(shù)均不小于n/2的圖是哈密爾頓圖（n為圖的結(jié)點(diǎn)數(shù)）？ 4 前述判定定理給出的條件只是充分條件，不是必要條件。請舉例說明之。 5 設(shè)G為（n，m）圖。請證明：如果 ，那么G為哈密爾頓圖。 1133 哈密爾頓圖應(yīng)用舉例 問題 考慮在七天內(nèi)安排七門課程的考試，要求

47、同一位教師所任教的兩門課程考試不安排在接連的兩天里，請應(yīng)用有關(guān)圖論性質(zhì)證明：如果教師所擔(dān)任的課程都不多于四門，則存在滿足上述要求的考試安排方案.分析設(shè)G為七個結(jié)點(diǎn)的圖，每一個結(jié)點(diǎn)對應(yīng)一門功課的考試，如果這兩個結(jié)點(diǎn)對應(yīng)的考試課程是由不同教師擔(dān)任的，那么這兩個結(jié)點(diǎn)之間有一條邊，因?yàn)槊總€教師所任的課程不超過4，故每個結(jié)點(diǎn)的度數(shù)至少是3，任兩個結(jié)點(diǎn)度數(shù)的和至少是6，故根據(jù)定理，G總包含一條哈密爾頓路，它對應(yīng)于一個七門考試課目的一個適當(dāng)安排。114小結(jié)與作業(yè)小結(jié)1 哈密爾頓圖2 哈密爾頓圖的判定作業(yè) 習(xí)題 28、29 反證法構(gòu)造法115補(bǔ)充例題1 右圖是一個迷宮,其中數(shù)字表示通道、和死胡同(包括目標(biāo)) 。請用一個圖來表示這個迷宮(用結(jié)點(diǎn)表示通道、和死胡同(包括目標(biāo)),用邊表示