高等數(shù)學(xué)-離散數(shù)學(xué)及其應(yīng)用-課件-第十一章幾種特殊的圖

1、1第十一章第十一章 幾種特殊的圖幾種特殊的圖主要內(nèi)容主要內(nèi)容l 歐拉圖歐拉圖l 哈密頓圖哈密頓圖l 二部圖與匹配二部圖與匹配l 平面圖平面圖l 著色著色211.1 歐拉圖歐拉圖歷史背景：哥尼斯堡七橋問(wèn)題歷史背景：哥尼斯堡七橋問(wèn)題3歐拉圖定義歐拉圖定義定義定義11.1 圖圖(無(wú)向圖或有向圖無(wú)向圖或有向圖)中所有邊恰好通過(guò)一次且經(jīng)過(guò)中所有邊恰好通過(guò)一次且經(jīng)過(guò)所有頂點(diǎn)的通路稱為所有頂點(diǎn)的通路稱為歐拉通路歐拉通路. 圖中所有邊恰好通過(guò)一次且圖中所有邊恰好通過(guò)一次且經(jīng)過(guò)所有頂點(diǎn)的回路稱為經(jīng)過(guò)所有頂點(diǎn)的回路稱為歐拉回路歐拉回路具有歐拉回路的圖稱為具有歐拉回路的圖稱為歐拉圖歐拉圖. 具有歐拉通路而無(wú)歐拉回路

2、的圖稱為具有歐拉通路而無(wú)歐拉回路的圖稱為半歐拉圖半歐拉圖說(shuō)明：說(shuō)明：規(guī)定平凡圖為歐拉圖規(guī)定平凡圖為歐拉圖.環(huán)不影響圖的歐拉性環(huán)不影響圖的歐拉性.4歐拉圖實(shí)例歐拉圖實(shí)例歐拉圖歐拉圖不是不是半歐拉圖半歐拉圖歐拉圖歐拉圖不是不是半歐拉圖半歐拉圖5歐拉圖的判別法歐拉圖的判別法定理定理11.1 (1) 無(wú)向圖無(wú)向圖G是歐拉圖當(dāng)且僅當(dāng)是歐拉圖當(dāng)且僅當(dāng)G是連通的且沒(méi)有奇是連通的且沒(méi)有奇度頂點(diǎn)度頂點(diǎn)(2) 無(wú)向圖無(wú)向圖G是半歐拉圖當(dāng)且僅當(dāng)是半歐拉圖當(dāng)且僅當(dāng)G是連通的且恰有兩個(gè)奇度是連通的且恰有兩個(gè)奇度頂點(diǎn)頂點(diǎn)(3) 有向圖有向圖D是歐拉圖當(dāng)且僅當(dāng)是歐拉圖當(dāng)且僅當(dāng)D是強(qiáng)連通的且每個(gè)頂點(diǎn)的入是強(qiáng)連通的且每個(gè)頂點(diǎn)的

3、入度等于出度度等于出度(4) 有向圖有向圖D是半歐拉圖當(dāng)且僅當(dāng)是半歐拉圖當(dāng)且僅當(dāng)D是單向連通的且恰有兩個(gè)是單向連通的且恰有兩個(gè)奇度頂點(diǎn)奇度頂點(diǎn), 其中一個(gè)頂點(diǎn)的入度比出度大其中一個(gè)頂點(diǎn)的入度比出度大1, 另一個(gè)頂點(diǎn)出度另一個(gè)頂點(diǎn)出度比入度大比入度大1, 其余頂點(diǎn)的入度等于出度其余頂點(diǎn)的入度等于出度例例1 設(shè)設(shè)G是非平凡的歐拉圖，則是非平凡的歐拉圖，則 (G) 2.證證 只需證明只需證明G的任意一條邊的任意一條邊e都不是橋都不是橋. 設(shè)設(shè)C是一條歐拉回路是一條歐拉回路, e在在C上，因而上，因而G e仍是連通的，故仍是連通的，故e不是橋不是橋6Fleury算法算法算法：算法：(1) 任取任取v0

4、 V(G), 令令P0=v0, i=0. (2) 設(shè)設(shè)Pi = v0e1v1e2eivi ， 如果如果E(G)-e1,e2,ei 中沒(méi)有與中沒(méi)有與vi關(guān)聯(lián)的邊關(guān)聯(lián)的邊, 則計(jì)算結(jié)束則計(jì)算結(jié)束; 否則按下面方法從否則按下面方法從E(G) e1,e2,ei 中選取中選取ei+1： (a) ei+1與與vi 關(guān)聯(lián)；關(guān)聯(lián)； (b) 除非無(wú)別的邊可供選擇除非無(wú)別的邊可供選擇, 否則否則ei+1不應(yīng)為不應(yīng)為 G e1,e2,ei 中的橋中的橋. 設(shè)設(shè)ei+1=(vi,vi+1), 把把ei+1vi+1加入加入Pi. (3) 令令i=i+1, 返回返回(2).7實(shí)例實(shí)例一筆畫(huà)出一條歐拉回路一筆畫(huà)出一條歐拉回

5、路8實(shí)例實(shí)例一筆畫(huà)出一條歐拉回路一筆畫(huà)出一條歐拉回路911.2 哈密頓圖哈密頓圖歷史背景：哈密頓周游世界問(wèn)題歷史背景：哈密頓周游世界問(wèn)題 (1) (2) 10哈密頓圖與半哈密頓圖哈密頓圖與半哈密頓圖定義定義11.2 經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的通路稱作經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的通路稱作哈密頓哈密頓通路通路. 經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的回路稱作經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的回路稱作哈密頓回哈密頓回路路. 具有哈密頓回路的圖稱作具有哈密頓回路的圖稱作哈密頓圖哈密頓圖. 具有哈密頓通路且無(wú)具有哈密頓通路且無(wú)哈密頓回路的圖稱作哈密頓回路的圖稱作半哈密頓圖半哈密頓圖.規(guī)定規(guī)定: 平凡圖是哈密頓

6、圖平凡圖是哈密頓圖.哈密頓圖哈密頓圖半哈密頓圖半哈密頓圖哈密頓圖哈密頓圖例例不是不是11無(wú)向哈密頓圖的一個(gè)必要條件無(wú)向哈密頓圖的一個(gè)必要條件定理定理11.2 設(shè)無(wú)向圖設(shè)無(wú)向圖G=是哈密頓圖，對(duì)于任意是哈密頓圖，對(duì)于任意V1 V且且V1，均有，均有 p(G V1) |V1|證證 設(shè)設(shè)C為為G中一條哈密頓回路中一條哈密頓回路(1) p(C V1) |V1|(2) p(G V1) p(C V1) |V1| （因?yàn)椋ㄒ驗(yàn)镃 G）推論推論 設(shè)無(wú)向圖設(shè)無(wú)向圖G=是半哈密頓圖，對(duì)于任意的是半哈密頓圖，對(duì)于任意的V1 V且且V1均有均有 p(G V1) |V1|+1證證 設(shè)設(shè) 為從為從u到到v的哈密頓通路，令

7、的哈密頓通路，令G = G (u,v)，則，則G 為為哈密頓圖哈密頓圖. 于是于是 p(G V1) = p(G V1 (u,v) p(G V1)+1 |V1|+112例題例題例例2 判斷下面的圖是不是哈密頓圖判斷下面的圖是不是哈密頓圖, 是不是半哈密頓圖是不是半哈密頓圖.解解 (a)取取V1=a,f, p(G V1)=|b,c,d,e|=4|V1|=2, 不是哈密頓圖，不是哈密頓圖，也不是半哈密頓圖也不是半哈密頓圖(b)取取V1=a,g,h,i,c, p(G V1)=| b,e,f,j,k,d|=6|V1|=5, 不是哈密不是哈密頓圖頓圖. 而而baegjckhfid是一條哈密頓通路是一條哈密

8、頓通路, 是半哈密頓圖是半哈密頓圖(c) abcdgihjefa是一條哈密頓回路，是哈密頓圖是一條哈密頓回路，是哈密頓圖13例題例題例例3 設(shè)設(shè)G為為n階無(wú)向連通簡(jiǎn)單圖，若階無(wú)向連通簡(jiǎn)單圖，若G中有割點(diǎn)或橋，則中有割點(diǎn)或橋，則G不不是哈密頓圖是哈密頓圖.證證 設(shè)設(shè)v為割點(diǎn)，則為割點(diǎn)，則 p(G v) 2|v|=1. K2有橋，它顯然不是哈密頓圖有橋，它顯然不是哈密頓圖. 除除K2外，其他有橋的連外，其他有橋的連通圖均有割點(diǎn)通圖均有割點(diǎn).14無(wú)向哈密頓圖的一個(gè)充分條件無(wú)向哈密頓圖的一個(gè)充分條件定理定理11.3 設(shè)設(shè)G是是n階無(wú)向簡(jiǎn)單圖階無(wú)向簡(jiǎn)單圖, 若對(duì)于任意不相鄰的頂點(diǎn)若對(duì)于任意不相鄰的頂點(diǎn)v

9、i,vj, 均有均有 d(vi)+d(vj) n 1 ( )則則G 中存在哈密頓通路中存在哈密頓通路. 推論推論 設(shè)設(shè)G為為n (n 3) 階無(wú)向簡(jiǎn)單圖階無(wú)向簡(jiǎn)單圖, 若對(duì)于若對(duì)于G中任意兩個(gè)不相中任意兩個(gè)不相鄰的頂點(diǎn)鄰的頂點(diǎn)vi,vj, 均有均有 d(vi)+d(vj) n （）則則G中存在哈密頓回路中存在哈密頓回路.15判斷是否為哈密頓圖判斷是否為哈密頓圖 判斷是否為判斷是否為(半半)哈密頓圖至今還是一個(gè)難題哈密頓圖至今還是一個(gè)難題.(1) 觀察出一條哈密頓回路或哈密頓通路觀察出一條哈密頓回路或哈密頓通路.(2) 證明滿足充分條件證明滿足充分條件.(3) 證明不滿足必要條件證明不滿足必要條

10、件.例例4 證明右圖證明右圖(周游世界問(wèn)題周游世界問(wèn)題)是哈密頓圖是哈密頓圖證證 a b c d e f g h i j k l m n o p q r s t a是一條哈密頓回路是一條哈密頓回路.注意，此圖不滿足定理注意，此圖不滿足定理11.3推論的條件推論的條件.例例5 完全圖完全圖Kn (n 3)是哈密頓圖是哈密頓圖.證證 任何兩個(gè)頂點(diǎn)任何兩個(gè)頂點(diǎn)u,v，d(u)+d(v) = 2(n 1) n16貨郎問(wèn)題貨郎問(wèn)題貨郎問(wèn)題貨郎問(wèn)題: 有有n個(gè)城市個(gè)城市, 給定城市之間道路的長(zhǎng)度給定城市之間道路的長(zhǎng)度(長(zhǎng)度可以為長(zhǎng)度可以為 , 對(duì)應(yīng)這兩個(gè)城市之間無(wú)交通線對(duì)應(yīng)這兩個(gè)城市之間無(wú)交通線). 貨郎

11、從某個(gè)城市出發(fā)貨郎從某個(gè)城市出發(fā), 要要經(jīng)過(guò)每個(gè)城市一次且僅一次經(jīng)過(guò)每個(gè)城市一次且僅一次, 最后回到出發(fā)的城市最后回到出發(fā)的城市, 問(wèn)如何走問(wèn)如何走才能使他走的路線最短才能使他走的路線最短? 圖論方法描述如下圖論方法描述如下: 設(shè)設(shè)G=為一個(gè)為一個(gè)n階完全帶權(quán)圖階完全帶權(quán)圖Kn, 各邊的權(quán)非負(fù)各邊的權(quán)非負(fù), 且可能為且可能為 . 求求G中的一條最短的哈密頓回路中的一條最短的哈密頓回路.不計(jì)出發(fā)點(diǎn)和方向不計(jì)出發(fā)點(diǎn)和方向, Kn(n 3)中有中有(n 1)!/2 條不同的哈密頓回條不同的哈密頓回路路17 解解 C1= a b c d a, W(C1)=10 C2= a b d c a, W(C2)

12、=11 C3= a c b d a, W(C3)=9 最短最短 例例6 求下面帶權(quán)圖求下面帶權(quán)圖K4中最短哈密頓回路中最短哈密頓回路. 例題例題1811.3 二部圖與匹配二部圖與匹配定義定義11.3 設(shè)設(shè) G=為一個(gè)無(wú)向圖為一個(gè)無(wú)向圖, 若能將若能將 V分成分成 V1和和V2(V1 V2=V, V1 V2=), 使得使得 G 中的每條邊的兩個(gè)端點(diǎn)都是一中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于個(gè)屬于V1, 另一個(gè)屬于另一個(gè)屬于V2, 則稱則稱 G 為為二部圖二部圖 ( 或稱或稱二分圖二分圖, 偶偶圖圖), 稱稱V1和和V2為為互補(bǔ)頂點(diǎn)子集互補(bǔ)頂點(diǎn)子集, 常將二部圖常將二部圖G記為記為. 又若又若G是簡(jiǎn)單

13、二部圖是簡(jiǎn)單二部圖, V1中每個(gè)頂點(diǎn)均與中每個(gè)頂點(diǎn)均與V2中所有的頂點(diǎn)相鄰，中所有的頂點(diǎn)相鄰，則稱則稱G為為完全二部圖完全二部圖, 記為記為 Kr,s, 其中其中r=|V1|, s=|V2|. 19實(shí)例實(shí)例例例K2,3K3,320二部圖的判別法二部圖的判別法定理定理11.4 無(wú)向圖無(wú)向圖G=是二部圖當(dāng)且僅當(dāng)是二部圖當(dāng)且僅當(dāng)G中無(wú)奇圈中無(wú)奇圈 .證證 必要性必要性. 若若G中無(wú)圈中無(wú)圈, 結(jié)論成立結(jié)論成立. 若若G中有圈中有圈, 設(shè)設(shè)G中的一個(gè)中的一個(gè)圈圈C=v1v2vlv1, l2. 不妨設(shè)不妨設(shè)v1 V1, v1,v2,vl 依次交替屬于依次交替屬于V1, V2且且vl V2, 因而因而l為

14、偶數(shù)為偶數(shù). 得證得證C為偶圈為偶圈充分性充分性. 不妨設(shè)不妨設(shè)G為連通圖為連通圖, 否則可對(duì)每個(gè)連通分支進(jìn)行討論否則可對(duì)每個(gè)連通分支進(jìn)行討論, 孤立點(diǎn)可根據(jù)需要分屬孤立點(diǎn)可根據(jù)需要分屬V1和和V2. 設(shè)設(shè)v0為為G中任意一個(gè)頂點(diǎn)中任意一個(gè)頂點(diǎn), 令令 V1=v | v V(G) d(v0,v)為偶數(shù)為偶數(shù) V2=v | v V(G) d(v0,v)為奇數(shù)為奇數(shù)d(v0,v)是是v0到到v的最短路徑的邊數(shù)的最短路徑的邊數(shù)(每條邊的權(quán)為每條邊的權(quán)為1). V1，V2, V1 V2=, V1 V2=V(G). 要證要證V1中任意兩點(diǎn)不相鄰中任意兩點(diǎn)不相鄰21證明證明假若存在假若存在vi,vj V1

15、相鄰相鄰, 記記e=(vi,vj), 設(shè)設(shè)v0到到vi,vj的最短路徑分別的最短路徑分別為為 i, j, 由由 i, j和和e構(gòu)成一條長(zhǎng)度為奇數(shù)的回路構(gòu)成一條長(zhǎng)度為奇數(shù)的回路. 這條回路可這條回路可能是一條復(fù)雜回路能是一條復(fù)雜回路, 可以分解成若干由可以分解成若干由 i, j共有的邊構(gòu)成的共有的邊構(gòu)成的回路回路(實(shí)際上是每條邊重復(fù)一次的路徑實(shí)際上是每條邊重復(fù)一次的路徑)和由和由 i, j不共有的邊不共有的邊及及e構(gòu)成的圈構(gòu)成的圈. 由由 i, j共有的邊構(gòu)成的回路的長(zhǎng)度為偶數(shù)共有的邊構(gòu)成的回路的長(zhǎng)度為偶數(shù), 故在故在由由 i, j不共有的邊不共有的邊(可以還包括可以還包括e)構(gòu)成的圈中一定有奇

16、圈構(gòu)成的圈中一定有奇圈, 這這與已知條件矛盾與已知條件矛盾. 得證得證V1中任意兩頂點(diǎn)不相鄰中任意兩頂點(diǎn)不相鄰. 由對(duì)稱性由對(duì)稱性, V2中也不存在相鄰的頂點(diǎn)中也不存在相鄰的頂點(diǎn), 得證得證G為二部圖為二部圖22最大匹配最大匹配定義定義11.4 設(shè)設(shè)G=為二部圖為二部圖, M E, 如果如果M中的任意兩中的任意兩條邊都不相鄰條邊都不相鄰, 則稱則稱M是是G的一個(gè)的一個(gè)匹配匹配. G中邊數(shù)最多的匹配中邊數(shù)最多的匹配稱作稱作最大匹配最大匹配. 又設(shè)又設(shè)|V1| |V2|, 如果如果M是是G的一個(gè)匹配且的一個(gè)匹配且|M|=|V1|, 則稱則稱M是是V1到到V2的的完備匹配完備匹配. 當(dāng)當(dāng)|V2|=|

17、V1|時(shí)時(shí), 完備匹完備匹配又稱作配又稱作完美匹配完美匹配例例完備匹配完備匹配完美匹配完美匹配最大匹配最大匹配23與匹配有關(guān)的概念與匹配有關(guān)的概念定義定義11.5 設(shè)設(shè)M是二部圖是二部圖G=的一個(gè)匹配的一個(gè)匹配. 稱稱M中的邊中的邊為為匹配邊匹配邊, 不在不在M中的邊為中的邊為非匹配邊非匹配邊. 與匹配邊相關(guān)聯(lián)的頂點(diǎn)與匹配邊相關(guān)聯(lián)的頂點(diǎn)為為飽和點(diǎn)飽和點(diǎn), 不與匹配邊相關(guān)聯(lián)的頂點(diǎn)為不與匹配邊相關(guān)聯(lián)的頂點(diǎn)為非飽和點(diǎn)非飽和點(diǎn). G中由匹配中由匹配邊和非匹配邊交替構(gòu)成的路徑稱為邊和非匹配邊交替構(gòu)成的路徑稱為交錯(cuò)路徑交錯(cuò)路徑, 起點(diǎn)和終點(diǎn)都是起點(diǎn)和終點(diǎn)都是非飽和點(diǎn)的交錯(cuò)路徑稱為非飽和點(diǎn)的交錯(cuò)路徑稱為可增

18、廣的交錯(cuò)路徑可增廣的交錯(cuò)路徑M為為G的完備匹配當(dāng)且僅當(dāng)?shù)耐陚淦ヅ洚?dāng)且僅當(dāng)V1或或V2中的每個(gè)頂點(diǎn)都是飽和點(diǎn)中的每個(gè)頂點(diǎn)都是飽和點(diǎn)M為為G的完美匹配當(dāng)且僅當(dāng)?shù)耐昝榔ヅ洚?dāng)且僅當(dāng)G中的每個(gè)頂點(diǎn)都是飽和點(diǎn)中的每個(gè)頂點(diǎn)都是飽和點(diǎn)24可增廣的交錯(cuò)路徑可增廣的交錯(cuò)路徑例例左圖左圖, 飽和點(diǎn)飽和點(diǎn):u1,u3,u4,v1,v2,v3; 非飽和點(diǎn)非飽和點(diǎn):u2,v4;可增廣的交錯(cuò)路徑可增廣的交錯(cuò)路徑 : u2v3u4v2u1v4. 由由 得到多一條邊的匹配得到多一條邊的匹配.設(shè)設(shè)M為為G的一個(gè)匹配的一個(gè)匹配, 是關(guān)于是關(guān)于M的可增廣的交錯(cuò)路徑的可增廣的交錯(cuò)路徑, 則則 M =M E( )=(M E( ) (M

19、E( )是比是比M多一條邊的匹配多一條邊的匹配. 定理定理11.5 M為為G的最大匹配的最大匹配G中不含中不含M的可增廣的交錯(cuò)路徑的可增廣的交錯(cuò)路徑.u1u1u2u2u3u3u4u4v1v2v3v4v1v2v3v425Hall定理定理定理定理11.6 (Hall定理定理) 設(shè)二部圖設(shè)二部圖G=, 其中其中|V1| |V2|, 則則 G中存在從中存在從V1到到V2的完備匹配當(dāng)且僅當(dāng)?shù)耐陚淦ヅ洚?dāng)且僅當(dāng)V1中任意中任意k(1 k |V1|)個(gè)頂點(diǎn)至少與個(gè)頂點(diǎn)至少與V2中的中的k個(gè)頂點(diǎn)相鄰個(gè)頂點(diǎn)相鄰.(相異性條件相異性條件) 證證 必要性顯然必要性顯然. 證充分性證充分性. 設(shè)設(shè)M為為G的最大匹配的最

20、大匹配, 若若M不是完備不是完備的的, 則存在非飽和點(diǎn)則存在非飽和點(diǎn)vx V1. 于是于是, 存在存在e E1=E M與與vx關(guān)聯(lián)關(guān)聯(lián), 且且V2中與中與vx相鄰的頂點(diǎn)都是飽和點(diǎn)相鄰的頂點(diǎn)都是飽和點(diǎn). 考慮從考慮從vx出發(fā)的盡可能長(zhǎng)的出發(fā)的盡可能長(zhǎng)的所有交錯(cuò)路徑所有交錯(cuò)路徑, 這些交錯(cuò)路徑都不是可增廣的這些交錯(cuò)路徑都不是可增廣的, 因此每條路徑因此每條路徑的另一個(gè)端點(diǎn)一定是飽和點(diǎn)的另一個(gè)端點(diǎn)一定是飽和點(diǎn), 從而全在從而全在V1中中. 令令 S=v | v V1且且v在從在從vx出發(fā)的交錯(cuò)路徑上出發(fā)的交錯(cuò)路徑上 T=v | v V2且且v在從在從vx出發(fā)的交錯(cuò)路徑上出發(fā)的交錯(cuò)路徑上除除vx外外,

21、 S和和T中的頂點(diǎn)都是飽和點(diǎn)中的頂點(diǎn)都是飽和點(diǎn), 且由匹配邊給出兩者之間且由匹配邊給出兩者之間的一一對(duì)應(yīng)的一一對(duì)應(yīng), 因而因而|S|=|T|+1. 這說(shuō)明這說(shuō)明V1中有中有|T|+1個(gè)頂點(diǎn)只與個(gè)頂點(diǎn)只與V2中中|T|個(gè)頂點(diǎn)相鄰個(gè)頂點(diǎn)相鄰, 與相異性條件矛盾與相異性條件矛盾. 26t條件條件定理定理11.7 設(shè)二部圖設(shè)二部圖G=, 如果存在如果存在t使得使得, V1中每個(gè)頂中每個(gè)頂點(diǎn)至少關(guān)聯(lián)點(diǎn)至少關(guān)聯(lián)t條邊條邊, 而而V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián)中每個(gè)頂點(diǎn)至多關(guān)聯(lián) t 條邊條邊, 則則G 中存中存在在V1到到V2的完備匹配的完備匹配.(t條件條件)證證 V1中任意中任意k(1 k |V1|)個(gè)頂點(diǎn)至少

22、關(guān)聯(lián)個(gè)頂點(diǎn)至少關(guān)聯(lián)kt條邊條邊, 而而V2中每個(gè)頂中每個(gè)頂點(diǎn)至多關(guān)聯(lián)點(diǎn)至多關(guān)聯(lián)t條邊條邊, 這這kt條邊至少關(guān)聯(lián)條邊至少關(guān)聯(lián)V2中中k個(gè)頂點(diǎn)個(gè)頂點(diǎn). G滿足相異滿足相異性條件性條件第第2個(gè)圖不滿足個(gè)圖不滿足t條件條件, 但有完備匹配但有完備匹配.例例前兩個(gè)滿足相異性條件前兩個(gè)滿足相異性條件, 第第3個(gè)不滿足個(gè)不滿足27一個(gè)應(yīng)用實(shí)例一個(gè)應(yīng)用實(shí)例例例7 某課題組要從某課題組要從a, b, c, d, e 5人中派人中派3人分別到上海、廣州、人分別到上海、廣州、香港去開(kāi)會(huì)香港去開(kāi)會(huì). 已知已知a只想去上海，只想去上海，b只想去廣州，只想去廣州，c, d, e都表示都表示想去廣州或香港想去廣州或香港.

23、 問(wèn)該課題組在滿足個(gè)人要求的條件下，共問(wèn)該課題組在滿足個(gè)人要求的條件下，共有幾種派遣方案？有幾種派遣方案？ 解解 令令G=，其中，其中V1=s, g, x，s, g, x分別表示上海、分別表示上海、廣州和香港廣州和香港. V2=a, b, c, d, e, E=(u,v) | u V1, v V2, v想去想去u. 每個(gè)每個(gè)V1到到V2的完備匹配給的完備匹配給出一個(gè)派遣方案出一個(gè)派遣方案, 共有共有9種種.如如a到上海到上海, b到廣州到廣州, c到香到香港港. 28(2)是是(1) 的平面嵌入，的平面嵌入，(4)是是(3)的平面嵌入的平面嵌入.11.4 平面圖平面圖定義定義11.6 如果能將

24、無(wú)向圖如果能將無(wú)向圖G畫(huà)在平面上使得除頂點(diǎn)處外無(wú)邊相畫(huà)在平面上使得除頂點(diǎn)處外無(wú)邊相交交, 則稱則稱G是是可平面圖可平面圖, 簡(jiǎn)稱簡(jiǎn)稱平面圖平面圖. 畫(huà)出的無(wú)邊相交的圖稱為畫(huà)出的無(wú)邊相交的圖稱為G的的平面嵌入平面嵌入. 無(wú)平面嵌入的圖稱為無(wú)平面嵌入的圖稱為非平面圖非平面圖例例 (1) (2) (3) (4)29平面圖的性質(zhì)平面圖的性質(zhì)l K5, K3,3都是非平面圖（都是非平面圖（定理定理11.13）l 平行邊與環(huán)不影響平面性平行邊與環(huán)不影響平面性. 定理定理11.8 平面圖的子圖都是平面圖平面圖的子圖都是平面圖, 非平面圖的母圖都是非非平面圖的母圖都是非平面圖平面圖例如例如, 所有度數(shù)不超過(guò)所

25、有度數(shù)不超過(guò)4的簡(jiǎn)單圖都是平面圖的簡(jiǎn)單圖都是平面圖. 當(dāng)當(dāng)|V1|=1和和2時(shí)二部圖時(shí)二部圖G=是平面圖是平面圖. Kn(n 5)和和Ks,t(s,t 3)都是非平面圖都是非平面圖.30平面圖的面與次數(shù)平面圖的面與次數(shù)定義定義11.7 給定平面圖給定平面圖G的平面嵌入的平面嵌入, G的邊將平面劃分成若干的邊將平面劃分成若干個(gè)區(qū)域個(gè)區(qū)域, 每個(gè)區(qū)域都稱為每個(gè)區(qū)域都稱為G的一個(gè)的一個(gè)面面, 其中有一個(gè)面的面積無(wú)其中有一個(gè)面的面積無(wú)限限, 稱為稱為無(wú)限面無(wú)限面或或外部面外部面, 其余面的面積有限其余面的面積有限, 稱為稱為有限面有限面或或內(nèi)部面內(nèi)部面. 包圍每個(gè)面的所有邊組成的回路組稱為該面的包圍每

26、個(gè)面的所有邊組成的回路組稱為該面的邊界邊界，邊界的長(zhǎng)度稱為該面的邊界的長(zhǎng)度稱為該面的次數(shù)次數(shù)面面R的次數(shù)記為的次數(shù)記為deg(R)deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8. 例例31次數(shù)的性質(zhì)次數(shù)的性質(zhì)定理定理17.4 平面圖平面圖各面次數(shù)之和等于邊數(shù)的兩倍各面次數(shù)之和等于邊數(shù)的兩倍. 證證 對(duì)每一條邊對(duì)每一條邊e, 若若e在兩個(gè)面的公共邊界上在兩個(gè)面的公共邊界上, 則在計(jì)算這兩則在計(jì)算這兩個(gè)面的次數(shù)時(shí)個(gè)面的次數(shù)時(shí), e各提供各提供1. 而當(dāng)而當(dāng)e只在某一個(gè)面的邊界上出現(xiàn)只在某一個(gè)面的邊界上出現(xiàn)時(shí)時(shí), 它必在該面的邊界上出現(xiàn)兩次它必在該面的邊界上出現(xiàn)

27、兩次, 從而在計(jì)算該面的次數(shù)時(shí)從而在計(jì)算該面的次數(shù)時(shí),e提供提供232極大平面圖極大平面圖定義定義11.8 G為簡(jiǎn)單平面圖為簡(jiǎn)單平面圖, 若在若在G的任意兩個(gè)不相鄰的頂點(diǎn)的任意兩個(gè)不相鄰的頂點(diǎn)之間加一條邊所得圖為非平面圖之間加一條邊所得圖為非平面圖, 則稱則稱G為為極大平面圖極大平面圖.例如例如, K5,K33刪去一條邊后是極大平面圖刪去一條邊后是極大平面圖 K1, K2, K3, K4都是極大平面圖都是極大平面圖.定理定理11.10 設(shè)設(shè)G為為n(n 3)階簡(jiǎn)單連通的平面圖階簡(jiǎn)單連通的平面圖, G為極大平面為極大平面圖當(dāng)且僅當(dāng)圖當(dāng)且僅當(dāng)G的每個(gè)面的次數(shù)均為的每個(gè)面的次數(shù)均為3. 證證 現(xiàn)只證

28、必要性現(xiàn)只證必要性. 各面次數(shù)都大于或等于各面次數(shù)都大于或等于3. 假如假如deg(Ri)=s 4, 若若v1與與v3不相鄰不相鄰, 則在則在Ri內(nèi)加邊內(nèi)加邊(v1,v3)不不破壞平面性破壞平面性, 與與G是極大平面圖矛盾是極大平面圖矛盾, 因因而而v1與與v3必相鄰必相鄰, 且邊且邊(v1,v3)必在必在Ri外部外部.同樣地同樣地, v2與與v4也相鄰且邊也相鄰且邊(v2,v4)在在Ri的的外部外部. 于是于是, (v1,v3)與與(v2,v4)相交于相交于Ri的外的外部部, 與與G是平面圖矛盾是平面圖矛盾.33例例 是否是極大平面圖是否是極大平面圖?定理的應(yīng)用定理的應(yīng)用只有只有(3)為極大

29、平面圖為極大平面圖 (1) (2) (3) 34極小非平面圖極小非平面圖定義定義11.9 若在非平面圖若在非平面圖G中任意刪除一條邊中任意刪除一條邊, 所得圖為平面圖所得圖為平面圖, 則稱則稱G為為極小非平面圖極小非平面圖.l K5, K3,3都是極小非平面圖都是極小非平面圖l 極小非平面圖必為簡(jiǎn)單圖極小非平面圖必為簡(jiǎn)單圖35 歐拉公式歐拉公式定理定理11.11 設(shè)設(shè)G為為n階階m條邊條邊r個(gè)面的連通平面圖個(gè)面的連通平面圖, 則則n m+r=2證證 對(duì)對(duì)m做歸納證明做歸納證明. m=0時(shí)時(shí), G為平凡圖為平凡圖, n=1,m=0,r=1,成立成立.設(shè)設(shè)m=k(k 0)時(shí)結(jié)論成立時(shí)結(jié)論成立. 當(dāng)

30、當(dāng)m=k+1時(shí)時(shí), 分兩者情況討論分兩者情況討論:(1) G中有一個(gè)中有一個(gè)1度頂點(diǎn)度頂點(diǎn)v, 令令G =G v, 仍是連通的仍是連通的, n =n 1, m =m 1=k, r =r. 由歸納假設(shè)由歸納假設(shè), n m +r =2. 于是于是 n m+r = (n +1) (m +1)+r = n m +r = 2(2) G中沒(méi)有中沒(méi)有1度頂點(diǎn)度頂點(diǎn), 則每一條邊都在某兩個(gè)面的公共邊界則每一條邊都在某兩個(gè)面的公共邊界上上. 任取一條邊任取一條邊e, 令令G =G e, 仍連通且仍連通且n =n, m =m 1=k, r =r 1. 由歸納假設(shè)由歸納假設(shè), n m +r =2. 于是于是 n m

31、+r = n (m +1)+(r +1) = n m +r = 236 歐拉公式的推廣歐拉公式的推廣推論推論 對(duì)于有對(duì)于有k個(gè)連通分支的平面圖個(gè)連通分支的平面圖G, 有有n m + r = k+1 其中其中n, m, r分別為分別為G的頂點(diǎn)數(shù)的頂點(diǎn)數(shù), 邊數(shù)和面數(shù)邊數(shù)和面數(shù).證證 設(shè)設(shè)G的連通分支為的連通分支為G1,G2,Gk, 由歐拉公式由歐拉公式 ni mi + ri = 2, i=1,2,k.G的面數(shù)的面數(shù) . 于是，于是，整理得整理得 n m + r = k+1 kiikrr1)1(1)(21 krmnrmnkkiiii37)2(2 nllm)2()deg(21nmlrlRmrii )

32、2(2 nllm解得解得 與歐拉公式有關(guān)的定理與歐拉公式有關(guān)的定理定理定理11.12 設(shè)設(shè)G為連通的平面圖為連通的平面圖, 每個(gè)面的次數(shù)至少為每個(gè)面的次數(shù)至少為l 3，則，則 證證 由定理由定理11.9及及歐拉公式歐拉公式,定理定理11.13 K5, K3,3都是非平面圖都是非平面圖.證證 假設(shè)假設(shè)K5是平面圖是平面圖, K5無(wú)環(huán)和平行邊無(wú)環(huán)和平行邊, 每個(gè)面的次數(shù)均大于等每個(gè)面的次數(shù)均大于等于于3. 應(yīng)該有應(yīng)該有矛盾矛盾.9)25(23310 38證證(續(xù)續(xù)) 假設(shè)假設(shè)K3,3是平面圖是平面圖, K3,3中最短圈的長(zhǎng)度為中最短圈的長(zhǎng)度為4, 每個(gè)面的每個(gè)面的次數(shù)均大于等于次數(shù)均大于等于4.

33、應(yīng)該有應(yīng)該有矛盾矛盾.8)26(2449 定理定理11.14 設(shè)設(shè)G為為n(n 3)階階m條邊的極大平面圖條邊的極大平面圖, 則則m=3n 6.證證 極大平面圖是連通圖極大平面圖是連通圖, 由歐拉公式得由歐拉公式得 r = 2+m n. 又由定理又由定理11.10的必要性的必要性, G的每個(gè)面的次數(shù)均為的每個(gè)面的次數(shù)均為3, 所以所以2m=3r. 得得m=3n 6推論推論 設(shè)設(shè)G是是n(n 3)階階m條邊的簡(jiǎn)單平面圖條邊的簡(jiǎn)單平面圖, 則則 m 3n 6與歐拉公式有關(guān)的定理與歐拉公式有關(guān)的定理39如果簡(jiǎn)單連通平面圖如果簡(jiǎn)單連通平面圖G的每個(gè)面的次數(shù)都等于的每個(gè)面的次數(shù)都等于3, 則則G為極大平

34、為極大平面圖面圖.證證 由定理由定理11.9, 2m=3r由歐拉公式由歐拉公式, r = 2 + m n 整理得整理得 m = 3n 6若若G不是極大平面圖不是極大平面圖, 則則G中存在不相鄰的頂點(diǎn)中存在不相鄰的頂點(diǎn)u,v, 使得使得G =G (u,v)還是簡(jiǎn)單平面圖還是簡(jiǎn)單平面圖, 而而G 的邊數(shù)的邊數(shù)m =m+1, n =n, 故故 m 3n 6與定理與定理11.14的推論矛盾的推論矛盾定理定理11.10充分性證明充分性證明40 同胚同胚定義定義11.10 設(shè)設(shè)e=(u,v)為圖為圖G的一條邊的一條邊, 在在G中刪除中刪除e, 增加新的增加新的頂點(diǎn)頂點(diǎn)w, 使使u,v均與均與w相鄰相鄰,

35、稱為在稱為在G中中插入插入2度頂點(diǎn)度頂點(diǎn)w. 設(shè)設(shè)w為為G中一個(gè)中一個(gè)2度頂點(diǎn)度頂點(diǎn), w與與u,v相鄰相鄰, 刪除刪除w, 增加新邊增加新邊(u,v), 稱為在稱為在G中中消去消去2度頂點(diǎn)度頂點(diǎn)w. 若兩個(gè)圖若兩個(gè)圖G1與與G2同構(gòu)同構(gòu), 或通過(guò)反復(fù)插入、消去或通過(guò)反復(fù)插入、消去2度頂點(diǎn)后同度頂點(diǎn)后同構(gòu)構(gòu), 則稱則稱G1與與G2同胚同胚例例 插入與消去插入與消去2度頂點(diǎn)度頂點(diǎn)收縮邊收縮邊41庫(kù)拉圖斯基定理庫(kù)拉圖斯基定理定理定理11.15 G是平面圖是平面圖 G中不含與中不含與K5和和K3,3同胚的子圖同胚的子圖.定理定理11.16 G是平面圖是平面圖 G中無(wú)可收縮為中無(wú)可收縮為K5或或K3,

36、3的子圖的子圖.例例8 證明下邊兩個(gè)圖為非平面圖證明下邊兩個(gè)圖為非平面圖. 與與K5同胚同胚 。 。 。 與與K3,3同胚同胚 。 。 42例題例題例例9 證明彼得森圖為非平面圖證明彼得森圖為非平面圖. 與與K5同胚同胚收縮收縮(a,f),(b,g),(c,h),(d,i),(e,j) 與與K3,3同胚同胚收縮收縮(b,g),(c,h),(d,i),(e,j) 43點(diǎn)著色點(diǎn)著色定義定義11.11 設(shè)無(wú)向圖設(shè)無(wú)向圖G無(wú)環(huán)無(wú)環(huán), 對(duì)對(duì)G的每個(gè)頂點(diǎn)涂一種顏色的每個(gè)頂點(diǎn)涂一種顏色, 使相使相鄰的頂點(diǎn)涂不同的顏色鄰的頂點(diǎn)涂不同的顏色, 稱為圖稱為圖G的一種的一種點(diǎn)著色點(diǎn)著色,簡(jiǎn)稱簡(jiǎn)稱著色著色. 若若能用

37、能用k種顏色給種顏色給G的頂點(diǎn)著色，的頂點(diǎn)著色， 則稱則稱G是是k-可著色的可著色的圖的著色問(wèn)題圖的著色問(wèn)題: 要用盡可能少的顏色給圖著色要用盡可能少的顏色給圖著色. 偶圈用偶圈用2種顏色種顏色, 奇圈用奇圈用3種種. 奇階輪圖用奇階輪圖用3種種, 偶階輪圖用偶階輪圖用4種種.例例11 G是是2-可著色的當(dāng)且僅當(dāng)可著色的當(dāng)且僅當(dāng)G是二部圖是二部圖.1212121232123323123243例例1044應(yīng)用應(yīng)用1. 有有n項(xiàng)工作項(xiàng)工作, 每項(xiàng)工作需要一天的時(shí)間每項(xiàng)工作需要一天的時(shí)間, 有些工作不能同時(shí)有些工作不能同時(shí)進(jìn)行進(jìn)行, 問(wèn)至少需要幾天才能完成所有的工作問(wèn)至少需要幾天才能完成所有的工作?

38、 頂點(diǎn)表示工作頂點(diǎn)表示工作, 兩點(diǎn)之間有一條邊兩點(diǎn)之間有一條邊這這兩項(xiàng)工作不能同時(shí)進(jìn)行兩項(xiàng)工作不能同時(shí)進(jìn)行. 工作的時(shí)間工作的時(shí)間安排對(duì)應(yīng)于這個(gè)圖的點(diǎn)著色安排對(duì)應(yīng)于這個(gè)圖的點(diǎn)著色: 著同一種顏色的頂點(diǎn)對(duì)應(yīng)的工著同一種顏色的頂點(diǎn)對(duì)應(yīng)的工作可安排在同一天作可安排在同一天, 所需的最少天數(shù)是所需要的最少顏色數(shù)所需的最少天數(shù)是所需要的最少顏色數(shù).2. 寄存器分配寄存器分配. 計(jì)算機(jī)有計(jì)算機(jī)有k個(gè)寄存器個(gè)寄存器, 要給每一個(gè)變量分配一要給每一個(gè)變量分配一個(gè)寄存器個(gè)寄存器. 如果兩個(gè)變量要在同一時(shí)刻使用如果兩個(gè)變量要在同一時(shí)刻使用, 則不能把它們分則不能把它們分配給同一個(gè)寄存器配給同一個(gè)寄存器. 每一個(gè)變

39、量是一個(gè)頂點(diǎn)每一個(gè)變量是一個(gè)頂點(diǎn), 如果兩個(gè)變量要如果兩個(gè)變量要在同一時(shí)刻使用在同一時(shí)刻使用, 則用一條邊連接這兩個(gè)變量則用一條邊連接這兩個(gè)變量. 這個(gè)圖的這個(gè)圖的k-著著色對(duì)應(yīng)給變量分配寄存器的一種安全方式色對(duì)應(yīng)給變量分配寄存器的一種安全方式: 給著同一種顏色給著同一種顏色的變量分配同一個(gè)寄存器的變量分配同一個(gè)寄存器.45應(yīng)用應(yīng)用3. 無(wú)線交換設(shè)備的波長(zhǎng)分配無(wú)線交換設(shè)備的波長(zhǎng)分配. 有有n臺(tái)設(shè)備和臺(tái)設(shè)備和k個(gè)發(fā)射波長(zhǎng)個(gè)發(fā)射波長(zhǎng), 要給要給每一臺(tái)設(shè)備分配一個(gè)波長(zhǎng)每一臺(tái)設(shè)備分配一個(gè)波長(zhǎng). 如果兩臺(tái)設(shè)備靠得太近如果兩臺(tái)設(shè)備靠得太近, 則不能給則不能給它們分配相同的波長(zhǎng)它們分配相同的波長(zhǎng). 以設(shè)備為

40、頂點(diǎn)以設(shè)備為頂點(diǎn), 如果兩臺(tái)設(shè)備靠得太近如果兩臺(tái)設(shè)備靠得太近, 則用一條邊連接它們則用一條邊連接它們. 這個(gè)圖的這個(gè)圖的k-著色給出一個(gè)波長(zhǎng)分配方案著色給出一個(gè)波長(zhǎng)分配方案: 給著同一種顏色的設(shè)備分配同一個(gè)波長(zhǎng)給著同一種顏色的設(shè)備分配同一個(gè)波長(zhǎng). 46地圖著色與對(duì)偶圖地圖著色與對(duì)偶圖地圖地圖: 連通無(wú)橋平面圖的平面嵌入連通無(wú)橋平面圖的平面嵌入. 每一個(gè)面是一個(gè)國(guó)家每一個(gè)面是一個(gè)國(guó)家(或省或省, 市市, 區(qū)等區(qū)等). 若兩個(gè)國(guó)家有公共的邊界，則稱這兩個(gè)國(guó)家是相鄰若兩個(gè)國(guó)家有公共的邊界，則稱這兩個(gè)國(guó)家是相鄰的的. 對(duì)地圖的每個(gè)國(guó)家涂上一種顏色，使相鄰的國(guó)家涂不同對(duì)地圖的每個(gè)國(guó)家涂上一種顏色，使相鄰

41、的國(guó)家涂不同的顏色，稱為對(duì)地圖的面著色的顏色，稱為對(duì)地圖的面著色, 簡(jiǎn)稱簡(jiǎn)稱地圖著色地圖著色. 地圖著色問(wèn)題地圖著色問(wèn)題: 用盡可能少的顏色給地圖著色用盡可能少的顏色給地圖著色. 定義定義11.12 設(shè)設(shè)G是一個(gè)平面嵌入是一個(gè)平面嵌入, 構(gòu)造圖構(gòu)造圖G*如下如下: 在在G的每一個(gè)的每一個(gè)面面Ri中放置一個(gè)頂點(diǎn)中放置一個(gè)頂點(diǎn)vi*. 設(shè)設(shè)e為為G的一條邊的一條邊, 若若e在在G的面的面Ri與與Rj的公共邊界上的公共邊界上, 則作邊則作邊e*=(vi*,vj*)與與e相交相交, 且不與其他任何邊且不與其他任何邊相交相交. 若若e為為G中的橋且在面中的橋且在面Ri的邊界上的邊界上, 則作以則作以vi

42、*為端點(diǎn)的環(huán)為端點(diǎn)的環(huán)e*=(vi*,vi*). 稱稱G*為為G的的對(duì)偶圖對(duì)偶圖. 47實(shí)例實(shí)例實(shí)線和空心點(diǎn)是平面嵌入實(shí)線和空心點(diǎn)是平面嵌入, 虛線和實(shí)心點(diǎn)是對(duì)偶圖虛線和實(shí)心點(diǎn)是對(duì)偶圖. 注意注意: 這兩個(gè)平面嵌入是同一個(gè)平面圖的平面嵌入這兩個(gè)平面嵌入是同一個(gè)平面圖的平面嵌入.48四色定理四色定理四色猜想四色猜想(19世紀(jì)世紀(jì)50年代年代, 德摩根德摩根) 五色定理五色定理(1890年年, 希伍德希伍德) 四色定理四色定理(1976年年, 阿佩爾與黑肯阿佩爾與黑肯)定理定理11.17 任何平面圖都是任何平面圖都是4-可著色的可著色的. 49第十一章第十一章 習(xí)題課習(xí)題課 主要內(nèi)容主要內(nèi)容l 歐

43、拉通路與歐拉回路歐拉通路與歐拉回路, 歐拉圖與半歐拉圖及判別歐拉圖與半歐拉圖及判別l 哈密頓通路與哈密頓回路哈密頓通路與哈密頓回路, 哈密頓圖與半哈密頓圖及判別哈密頓圖與半哈密頓圖及判別l 貨郎問(wèn)題貨郎問(wèn)題l 二部圖及其判別二部圖及其判別l 二部圖匹配及相關(guān)概念二部圖匹配及相關(guān)概念l 二部圖最大匹配的充要條件二部圖最大匹配的充要條件, 存在完備匹配的條件存在完備匹配的條件l 平面圖及其性質(zhì)平面圖及其性質(zhì)(歐拉公式歐拉公式)l 平面圖的判別平面圖的判別l 著色問(wèn)題著色問(wèn)題l 地圖著色與平面圖的對(duì)偶圖地圖著色與平面圖的對(duì)偶圖l 四色定理四色定理l 應(yīng)用應(yīng)用50基本要求基本要求基本要求基本要求l 深

44、刻理解歐拉圖深刻理解歐拉圖, 半歐拉圖半歐拉圖, 哈密頓圖哈密頓圖, 半哈密頓圖的定義半哈密頓圖的定義l 掌握歐拉圖掌握歐拉圖, 半歐拉圖的判別半歐拉圖的判別l 會(huì)用哈密頓圖與半哈密頓圖的必要條件和充分條件會(huì)用哈密頓圖與半哈密頓圖的必要條件和充分條件l 會(huì)一筆畫(huà)出歐拉回路會(huì)一筆畫(huà)出歐拉回路l 了解貨郎問(wèn)題了解貨郎問(wèn)題l 深刻理解二部圖的定義深刻理解二部圖的定義, 掌握二部圖的判別掌握二部圖的判別l 深刻理解二部圖匹配及相關(guān)概念深刻理解二部圖匹配及相關(guān)概念l 了解二部圖最大匹配了解二部圖最大匹配的充要條件的充要條件, 會(huì)用存在完備匹配的條會(huì)用存在完備匹配的條件件(Hall定理與定理與t條件條件)

45、51基本要求基本要求l 深刻理解平面圖及相關(guān)的概念深刻理解平面圖及相關(guān)的概念l 牢記極大平面圖的主要性質(zhì)和判別方法牢記極大平面圖的主要性質(zhì)和判別方法l 熟記歐拉公式及推廣形式，并能用歐拉公式及推廣形式熟記歐拉公式及推廣形式，并能用歐拉公式及推廣形式證明有關(guān)定理與命題證明有關(guān)定理與命題l 會(huì)用庫(kù)拉圖斯基定理證明非平面圖會(huì)用庫(kù)拉圖斯基定理證明非平面圖 l 了解對(duì)偶圖的概念了解對(duì)偶圖的概念l 了解著色問(wèn)題了解著色問(wèn)題, 地圖著色問(wèn)題和四色定理地圖著色問(wèn)題和四色定理l 會(huì)用上述概念和有關(guān)定理解決簡(jiǎn)單的實(shí)際問(wèn)題會(huì)用上述概念和有關(guān)定理解決簡(jiǎn)單的實(shí)際問(wèn)題521. 設(shè)設(shè)G為為n(n 2)階無(wú)向歐拉圖階無(wú)向歐拉

46、圖, 證明證明G中無(wú)橋中無(wú)橋.證二證二 用反證法用反證法. 假設(shè)假設(shè)e=(u,v)是橋是橋, 則則G e產(chǎn)生兩個(gè)連通分支產(chǎn)生兩個(gè)連通分支G1, G2, 不妨設(shè)不妨設(shè)u在在G1中中, v在在G2中中. G中沒(méi)有奇度頂點(diǎn)中沒(méi)有奇度頂點(diǎn), 而刪除而刪除e,只使只使u,v 的度數(shù)各減的度數(shù)各減1, 因而因而G1(G2)中只含一個(gè)奇度頂點(diǎn)中只含一個(gè)奇度頂點(diǎn), 與任與任何圖中奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù)矛盾何圖中奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù)矛盾.練習(xí)練習(xí)1證一證一 設(shè)設(shè)C為為G中一條歐拉回路中一條歐拉回路, e E(G), e在在C上上, C e 連通連通, G e也連通也連通, 所以所以e不為橋不為橋. 532. 證明

47、右圖不是哈密頓圖證明右圖不是哈密頓圖. 證一證一 取取 V1 = a, c, e, h, j, l， p(G V1) = 7 6=|V1|練習(xí)練習(xí) 2證二證二 G為二部圖為二部圖, V1 = a, c, e, h, j, l, V2 = b, d, f, g, i, k, m, |V1| |V2|. 證三證三 n = 13, m = 21. h, l, j為為4度頂點(diǎn)度頂點(diǎn), a, c, e為為3度頂點(diǎn)度頂點(diǎn), 且它且它們關(guān)聯(lián)不相同的邊們關(guān)聯(lián)不相同的邊. 而在哈密頓回路上而在哈密頓回路上, 每個(gè)頂點(diǎn)關(guān)聯(lián)兩條邊每個(gè)頂點(diǎn)關(guān)聯(lián)兩條邊, 于是可能用于哈密頓回路的邊至多有于是可能用于哈密頓回路的邊至多有

48、21 (3 2+3 1) = 12. 12條條邊不可能構(gòu)成經(jīng)過(guò)邊不可能構(gòu)成經(jīng)過(guò)13個(gè)頂點(diǎn)的回路個(gè)頂點(diǎn)的回路. 543某次國(guó)際會(huì)議某次國(guó)際會(huì)議8人參加人參加, 已知每人至少與其余已知每人至少與其余7人中的人中的4人人能用相同的語(yǔ)言能用相同的語(yǔ)言, 問(wèn)服務(wù)員能否將他們安排在同一張圓桌就問(wèn)服務(wù)員能否將他們安排在同一張圓桌就座座, 使得每個(gè)人都能與兩邊的人交談？使得每個(gè)人都能與兩邊的人交談？解解 做無(wú)向圖做無(wú)向圖G=, 其中其中V=v| v為與會(huì)者為與會(huì)者， E=(u,v) | u,v V, u與與v有能用相同的語(yǔ)言有能用相同的語(yǔ)言, 且且u v. G為簡(jiǎn)單圖且為簡(jiǎn)單圖且 v V, d(v) 4. 于是于是, u,v V, d(u)+d(v) 8,故故G為哈密頓圖為哈密頓圖. 服務(wù)員在服務(wù)員在G中找一條哈密頓回路中找一條哈密頓回路, 按回路按回路中相鄰關(guān)系安排座位即可中相鄰關(guān)系安排座位即可. 練習(xí)練習(xí) 3554. 某公司招聘了某公司招聘了3名大學(xué)畢業(yè)生名大學(xué)畢業(yè)生,