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

1、1,第十一章 幾種特殊的圖,主要內(nèi)容歐拉圖哈密頓圖二部圖與匹配平面圖著色,2,11.1 歐拉圖,歷史背景：哥尼斯堡七橋問(wèn)題,3,歐拉圖定義,定義11.1 圖(無(wú)向圖或有向圖)中所有邊恰好通過(guò)一次且經(jīng)過(guò)所有頂點(diǎn)的通路稱(chēng)為歐拉通路. 圖中所有邊恰好通過(guò)一次且經(jīng)過(guò)所有頂點(diǎn)的回路稱(chēng)為歐拉回路．具有歐拉回路的圖稱(chēng)為歐拉圖. 具有歐拉通路而無(wú)歐拉回路的圖稱(chēng)為半歐拉圖．說(shuō)明：規(guī)定平凡圖為歐拉圖.環(huán)不影響圖的歐拉性.,4,歐拉

2、圖實(shí)例,歐拉圖,不是,半歐拉圖,歐拉圖,不是,半歐拉圖,5,歐拉圖的判別法,定理11.1 (1) 無(wú)向圖G是歐拉圖當(dāng)且僅當(dāng)G是連通的且沒(méi)有奇度頂點(diǎn)．(2) 無(wú)向圖G是半歐拉圖當(dāng)且僅當(dāng)G是連通的且恰有兩個(gè)奇度頂點(diǎn)．(3) 有向圖D是歐拉圖當(dāng)且僅當(dāng)D是強(qiáng)連通的且每個(gè)頂點(diǎn)的入度等于出度．(4) 有向圖D是半歐拉圖當(dāng)且僅當(dāng)D是單向連通的且恰有兩個(gè)奇度頂點(diǎn), 其中一個(gè)頂點(diǎn)的入度比出度大1, 另一個(gè)頂點(diǎn)出度比入度大1, 其余頂點(diǎn)的

3、入度等于出度．,例1 設(shè)G是非平凡的歐拉圖，則?(G)?2.證 只需證明G的任意一條邊e都不是橋. 設(shè)C是一條歐拉回路, e在C上，因而G?e仍是連通的，故e不是橋．,6,Fleury算法,算法：(1) 任取v0?V(G), 令P0=v0, i=0. (2) 設(shè)Pi = v0e1v1e2…eivi ， 如果E(G)-{e1,e2,…,ei }中沒(méi)有與vi關(guān)聯(lián)的邊, 則計(jì)算結(jié)束; 否則按下面方法從

4、E(G)?{e1,e2,…,ei }中選取ei+1： (a) ei+1與vi 關(guān)聯(lián)； (b) 除非無(wú)別的邊可供選擇, 否則ei+1不應(yīng)為 G?{e1,e2,…,ei } 中的橋. 設(shè)ei+1=(vi,vi+1), 把ei+1vi+1加入Pi. (3) 令i=i+1, 返回(2).,7,實(shí)例,一筆畫(huà)出一條歐拉回路,,,,,,,,,,,,,,,,,8,實(shí)例,一筆畫(huà)出一條歐拉回路

5、,,,,,,,,,,,,,,,,,9,11.2 哈密頓圖,歷史背景：哈密頓周游世界問(wèn)題,(1) (2),10,哈密頓圖與半哈密頓圖,定義11.2 經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的通路稱(chēng)作哈密頓通路. 經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的回路稱(chēng)作哈密頓回路. 具有哈密頓回路的圖稱(chēng)作哈密頓圖. 具有哈密頓通路且無(wú)哈密頓回路的圖稱(chēng)作半哈密頓圖.規(guī)定

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

7、 p(G?V1) ? |V1|+1,證 設(shè)? 為從u到v的哈密頓通路，令G? = G?(u,v)，則G?為哈密頓圖. 于是 p(G?V1) = p(G??V1?(u,v)) ? p(G??V1)+1 ? |V1|+1,12,例題,例2 判斷下面的圖是不是哈密頓圖, 是不是半哈密頓圖.,解 (a)取V1={a,f}, p(G?V1)=|{b,c,d,e}|=4>|V1|=2

8、, 不是哈密頓圖，也不是半哈密頓圖．,(b)取V1={a,g,h,i,c}, p(G?V1)=| {b,e,f,j,k,d}|=6>|V1|=5, 不是哈密頓圖. 而baegjckhfid是一條哈密頓通路, 是半哈密頓圖．,(c) abcdgihjefa是一條哈密頓回路，是哈密頓圖．,13,例題,例3 設(shè)G為n階無(wú)向連通簡(jiǎn)單圖，若G中有割點(diǎn)或橋，則G不是哈密頓圖.,證 設(shè)v為割點(diǎn)，則 p(G?v) ? 2>|{v}|=

9、1. K2有橋，它顯然不是哈密頓圖. 除K2外，其他有橋的連通圖均有割點(diǎn).,14,無(wú)向哈密頓圖的一個(gè)充分條件,定理11.3 設(shè)G是n階無(wú)向簡(jiǎn)單圖, 若對(duì)于任意不相鄰的頂點(diǎn)vi,vj, 均有 d(vi)+d(vj) ? n?1 (?)則G 中存在哈密頓通路. 推論 設(shè)G為n (n?3) 階無(wú)向簡(jiǎn)單圖, 若對(duì)于G中任意兩個(gè)

10、不相鄰的頂點(diǎn)vi,vj, 均有 d(vi)+d(vj) ? n （??）則G中存在哈密頓回路.,15,判斷是否為哈密頓圖,判斷是否為(半)哈密頓圖至今還是一個(gè)難題.(1) 觀察出一條哈密頓回路或哈密頓通路.(2) 證明滿(mǎn)足充分條件.(3) 證明不滿(mǎn)足必要條件.,例4 證明右圖(周游世界問(wèn)題)是哈密頓圖,證 a b c d e f g

11、h i j k l m n o p q r s t a是一條哈密頓回路.注意，此圖不滿(mǎn)足定理11.3推論的條件.,例5 完全圖Kn (n?3)是哈密頓圖.,證 任何兩個(gè)頂點(diǎn)u,v，d(u)+d(v) = 2(n?1) ? n,16,貨郎問(wèn)題,貨郎問(wèn)題: 有n個(gè)城市, 給定城市之間道路的長(zhǎng)度(長(zhǎng)度可以為?, 對(duì)應(yīng)這兩個(gè)城市之間無(wú)交通線). 貨郎從某個(gè)城市出發(fā), 要經(jīng)過(guò)每個(gè)城市一次且僅一次, 最后回到出發(fā)的城市, 問(wèn)如何走才能

12、使他走的路線最短? 圖論方法描述如下: 設(shè)G=為一個(gè)n階完全帶權(quán)圖Kn, 各邊的權(quán)非負(fù), 且可能為?. 求G中的一條最短的哈密頓回路.不計(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)=11 C3= a c b d a, W(C3)=9

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

14、，則稱(chēng)G為完全二部圖, 記為 Kr,s, 其中r=|V1|, s=|V2|.,19,實(shí)例,例,K2,3,K3,3,20,二部圖的判別法,定理11.4 無(wú)向圖G=是二部圖當(dāng)且僅當(dāng)G中無(wú)奇圈 .證 必要性. 若G中無(wú)圈, 結(jié)論成立. 若G中有圈, 設(shè)G中的一個(gè)圈C=v1v2?vlv1, l≥2. 不妨設(shè)v1?V1, v1,v2,?,vl 依次交替屬于V1, V2且vl?V2, 因而l為偶數(shù). 得證C為偶圈．充分性. 不妨設(shè)G為

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

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

17、盾. 得證V1中任意兩頂點(diǎn)不相鄰. 由對(duì)稱(chēng)性, V2中也不存在相鄰的頂點(diǎn), 得證G為二部圖．,22,最大匹配,定義11.4 設(shè)G=為二部圖, M?E, 如果M中的任意兩條邊都不相鄰, 則稱(chēng)M是G的一個(gè)匹配. G中邊數(shù)最多的匹配稱(chēng)作最大匹配. 又設(shè)|V1|?|V2|, 如果M是G的一個(gè)匹配且|M|=|V1|, 則稱(chēng)M是V1到V2的完備匹配. 當(dāng)|V2|=|V1|時(shí), 完備匹配又稱(chēng)作完美匹配．例,完備匹配,完美匹配,最大匹配,

18、23,與匹配有關(guān)的概念,定義11.5 設(shè)M是二部圖G=的一個(gè)匹配. 稱(chēng)M中的邊為匹配邊, 不在M中的邊為非匹配邊. 與匹配邊相關(guān)聯(lián)的頂點(diǎn)為飽和點(diǎn), 不與匹配邊相關(guān)聯(lián)的頂點(diǎn)為非飽和點(diǎn). G中由匹配邊和非匹配邊交替構(gòu)成的路徑稱(chēng)為交錯(cuò)路徑, 起點(diǎn)和終點(diǎn)都是非飽和點(diǎn)的交錯(cuò)路徑稱(chēng)為可增廣的交錯(cuò)路徑．M為G的完備匹配當(dāng)且僅當(dāng)V1或V2中的每個(gè)頂點(diǎn)都是飽和點(diǎn)．M為G的完美匹配當(dāng)且僅當(dāng)G中的每個(gè)頂點(diǎn)都是飽和點(diǎn)．,24,可增廣的交錯(cuò)路徑,

19、例,左圖, 飽和點(diǎn):u1,u3,u4,v1,v2,v3; 非飽和點(diǎn):u2,v4;可增廣的交錯(cuò)路徑? : u2v3u4v2u1v4. 由? 得到多一條邊的匹配.設(shè)M為G的一個(gè)匹配, ?是關(guān)于M的可增廣的交錯(cuò)路徑, 則 M? =M?E(? )=(M?E(? ))?(M?E(? ))是比M多一條邊的匹配. 定理11.5 M為G的最大匹配?G中不含M的可增廣的交錯(cuò)路徑.,25,Hall定理,

20、定理11.6 (Hall定理) 設(shè)二部圖G=, 其中|V1|?|V2|, 則 G中存在從V1到V2的完備匹配當(dāng)且僅當(dāng)V1中任意k(1?k?|V1|)個(gè)頂點(diǎn)至少與V2中的k個(gè)頂點(diǎn)相鄰.(相異性條件) 證 必要性顯然. 證充分性. 設(shè)M為G的最大匹配, 若M不是完備的, 則存在非飽和點(diǎn)vx?V1. 于是, 存在e?E1=E?M與vx關(guān)聯(lián), 且V2中與vx相鄰的頂點(diǎn)都是飽和點(diǎn). 考慮從vx出發(fā)的盡可能長(zhǎng)的所有交錯(cuò)路徑, 這些交錯(cuò)路

21、徑都不是可增廣的, 因此每條路徑的另一個(gè)端點(diǎn)一定是飽和點(diǎn), 從而全在V1中. 令 S={v | v?V1且v在從vx出發(fā)的交錯(cuò)路徑上} T={v | v?V2且v在從vx出發(fā)的交錯(cuò)路徑上}除vx外, S和T中的頂點(diǎn)都是飽和點(diǎn), 且由匹配邊給出兩者之間的一一對(duì)應(yīng), 因而|S|=|T|+1. 這說(shuō)明V1中有|T|+1個(gè)頂點(diǎn)只與V2中|T|個(gè)頂點(diǎn)相鄰, 與相異性條件矛盾.,26,t條件

22、,定理11.7 設(shè)二部圖G=, 如果存在t使得, V1中每個(gè)頂點(diǎn)至少關(guān)聯(lián)t條邊, 而V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián) t 條邊, 則G 中存在V1到V2的完備匹配.(t條件)證 V1中任意k(1?k?|V1|)個(gè)頂點(diǎn)至少關(guān)聯(lián)kt條邊, 而V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián)t條邊, 這kt條邊至少關(guān)聯(lián)V2中k個(gè)頂點(diǎn). G滿(mǎn)足相異性條件．第2個(gè)圖不滿(mǎn)足t條件, 但有完備匹配.,例,前兩個(gè)滿(mǎn)足相異性條件, 第3個(gè)不滿(mǎn)足,27,一個(gè)應(yīng)用實(shí)例,例7

23、某課題組要從a, b, c, d, e 5人中派3人分別到上海、廣州、香港去開(kāi)會(huì). 已知a只想去上海，b只想去廣州，c, d, e都表示想去廣州或香港. 問(wèn)該課題組在滿(mǎ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è)V1到V2的完備匹配給出一個(gè)派遣方案

24、, 共有9種.如a到上海, b到廣州, c到香港.,28,(2)是(1) 的平面嵌入，(4)是(3)的平面嵌入.,11.4 平面圖,定義11.6 如果能將無(wú)向圖G畫(huà)在平面上使得除頂點(diǎn)處外無(wú)邊相交, 則稱(chēng)G是可平面圖, 簡(jiǎn)稱(chēng)平面圖. 畫(huà)出的無(wú)邊相交的圖稱(chēng)為G的平面嵌入. 無(wú)平面嵌入的圖稱(chēng)為非平面圖．例,(1) (2) (3)

25、 (4),29,平面圖的性質(zhì),K5, K3,3都是非平面圖（定理11.13）平行邊與環(huán)不影響平面性. 定理11.8 平面圖的子圖都是平面圖, 非平面圖的母圖都是非平面圖．例如, 所有度數(shù)不超過(guò)4的簡(jiǎn)單圖都是平面圖. 當(dāng)|V1|=1和2時(shí)二部圖G=是平面圖. Kn(n?5)和Ks,t(s,t?3)都是非平面圖.,30,平面圖的面與次數(shù),定義11.7 給定平面圖G的平

26、面嵌入, G的邊將平面劃分成若干個(gè)區(qū)域, 每個(gè)區(qū)域都稱(chēng)為G的一個(gè)面, 其中有一個(gè)面的面積無(wú)限, 稱(chēng)為無(wú)限面或外部面, 其余面的面積有限, 稱(chēng)為有限面或內(nèi)部面. 包圍每個(gè)面的所有邊組成的回路組稱(chēng)為該面的邊界，邊界的長(zhǎng)度稱(chēng)為該面的次數(shù)．面R的次數(shù)記為deg(R)．,deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8.,例,31,次數(shù)的性質(zhì),定理17.4 平面圖各面次數(shù)之和等于邊數(shù)的兩倍. 證

27、對(duì)每一條邊e, 若e在兩個(gè)面的公共邊界上, 則在計(jì)算這兩個(gè)面的次數(shù)時(shí), e各提供1. 而當(dāng)e只在某一個(gè)面的邊界上出現(xiàn)時(shí), 它必在該面的邊界上出現(xiàn)兩次, 從而在計(jì)算該面的次數(shù)時(shí),e提供2．,32,極大平面圖,定義11.8 G為簡(jiǎn)單平面圖, 若在G的任意兩個(gè)不相鄰的頂點(diǎn)之間加一條邊所得圖為非平面圖, 則稱(chēng)G為極大平面圖.例如, K5,K33刪去一條邊后是極大平面圖 K1, K2, K3, K4都是極大平面

28、圖.,定理11.10 設(shè)G為n(n?3)階簡(jiǎn)單連通的平面圖, G為極大平面圖當(dāng)且僅當(dāng)G的每個(gè)面的次數(shù)均為3. 證 現(xiàn)只證必要性. 各面次數(shù)都大于或等于3. 假如deg(Ri)=s?4, 若v1與v3不相鄰, 則在Ri內(nèi)加邊(v1,v3)不破壞平面性, 與G是極大平面圖矛盾, 因而v1與v3必相鄰, 且邊(v1,v3)必在Ri外部.同樣地, v2與v4也相鄰且邊(v2,v4)在Ri的外部. 于是, (v1,v3)與(v2,v

29、4)相交于Ri的外部, 與G是平面圖矛盾.,33,例 是否是極大平面圖?,定理的應(yīng)用,只有(3)為極大平面圖,(1) (2) (3),34,極小非平面圖,定義11.9 若在非平面圖G中任意刪除一條邊, 所得圖為平面圖, 則稱(chēng)G為極小非平面圖. K5, K3,3都是極小非平面圖 極小非平面圖必為簡(jiǎn)單圖,35,歐

30、拉公式,定理11.11 設(shè)G為n階m條邊r個(gè)面的連通平面圖, 則n?m+r=2證 對(duì)m做歸納證明. m=0時(shí), G為平凡圖, n=1,m=0,r=1,成立.設(shè)m=k(k?0)時(shí)結(jié)論成立. 當(dāng)m=k+1時(shí), 分兩者情況討論:(1) G中有一個(gè)1度頂點(diǎn)v, 令G? =G?v, 仍是連通的, n? =n?1, m? =m?1=k, r? =r. 由歸納假設(shè), n??m? +r? =2. 于是 n?m+r =

31、(n? +1)?(m? +1)+r? = n? ?m? +r? = 2(2) G中沒(méi)有1度頂點(diǎn), 則每一條邊都在某兩個(gè)面的公共邊界上. 任取一條邊e, 令G? =G?e, 仍連通且n? =n, m? =m?1=k, r? =r?1. 由歸納假設(shè), n? ?m? +r? =2. 于是 n?m+r = n? ?(m? +1)+(r? +1) = n? ?m? +r? = 2,36,歐拉公式的推廣,推論 對(duì)于有

32、k個(gè)連通分支的平面圖G, 有n ? m + r = k+1 其中n, m, r分別為G的頂點(diǎn)數(shù), 邊數(shù)和面數(shù).證 設(shè)G的連通分支為G1,G2,…,Gk, 由歐拉公式 ni ? mi + ri = 2, i=1,2,…,k.G的面數(shù) . 于是，整理得 n

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

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

35、, 則G為極大平面圖.證 由定理11.9, 2m=3r由歐拉公式, r = 2 + m ? n 整理得 m = 3n?6若G不是極大平面圖, 則G中存在不相鄰的頂點(diǎn)u,v, 使得G? =G?(u,v)還是簡(jiǎn)單平面圖, 而G?

36、 的邊數(shù)m? =m+1, n? =n, 故 m? >3n??6與定理11.14的推論矛盾．,定理11.10充分性證明,40,同胚,定義11.10 設(shè)e=(u,v)為圖G的一條邊, 在G中刪除e, 增加新的頂點(diǎn)w, 使u,v均與w相鄰, 稱(chēng)為在G中插入2度頂點(diǎn)w. 設(shè)w為G中一個(gè)2度頂點(diǎn), w與u,v相鄰, 刪除w, 增加新邊(u,v), 稱(chēng)為在G中消去2度頂點(diǎn)w.

37、 若兩個(gè)圖G1與G2同構(gòu), 或通過(guò)反復(fù)插入、消去2度頂點(diǎn)后同構(gòu), 則稱(chēng)G1與G2同胚．,例 插入與消去2度頂點(diǎn),收縮邊,41,庫(kù)拉圖斯基定理,定理11.15 G是平面圖 ? G中不含與K5和K3,3同胚的子圖.定理11.16 G是平面圖 ? G中無(wú)可收縮為K5或K3,3的子圖.,例8 證明下邊兩個(gè)圖為非平面圖.,42,例題,例9 證明彼得森圖為非平面圖.,與K5同胚收縮(a,f),(b,g),(c,h),(d,

38、i),(e,j),與K3,3同胚收縮(b,g),(c,h),(d,i),(e,j),43,點(diǎn)著色,定義11.11 設(shè)無(wú)向圖G無(wú)環(huán), 對(duì)G的每個(gè)頂點(diǎn)涂一種顏色, 使相鄰的頂點(diǎn)涂不同的顏色, 稱(chēng)為圖G的一種點(diǎn)著色,簡(jiǎn)稱(chēng)著色. 若能用k種顏色給G的頂點(diǎn)著色， 則稱(chēng)G是k-可著色的．圖的著色問(wèn)題: 要用盡可能少的顏色給圖著色.,偶圈用2種顏色, 奇圈用3種. 奇階輪圖用3種, 偶階輪圖用4種.,例11 G是2-可著色的當(dāng)且僅當(dāng)G是二

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

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

41、: 給著同一種顏色的設(shè)備分配同一個(gè)波長(zhǎng).,46,地圖著色與對(duì)偶圖,地圖: 連通無(wú)橋平面圖的平面嵌入. 每一個(gè)面是一個(gè)國(guó)家(或省, 市, 區(qū)等). 若兩個(gè)國(guó)家有公共的邊界，則稱(chēng)這兩個(gè)國(guó)家是相鄰的. 對(duì)地圖的每個(gè)國(guó)家涂上一種顏色，使相鄰的國(guó)家涂不同的顏色，稱(chēng)為對(duì)地圖的面著色, 簡(jiǎn)稱(chēng)地圖著色. 地圖著色問(wèn)題: 用盡可能少的顏色給地圖著色. 定義11.12 設(shè)G是一個(gè)平面嵌入, 構(gòu)造圖G*如下: 在G的每一個(gè)面Ri中放置一個(gè)頂點(diǎn)vi*.

42、 設(shè)e為G的一條邊, 若e在G的面Ri與Rj的公共邊界上, 則作邊e*=(vi*,vj*)與e相交, 且不與其他任何邊相交. 若e為G中的橋且在面Ri的邊界上, 則作以vi*為端點(diǎn)的環(huán)e*=(vi*,vi*). 稱(chēng)G*為G的對(duì)偶圖.,47,實(shí)例,實(shí)線和空心點(diǎn)是平面嵌入, 虛線和實(shí)心點(diǎn)是對(duì)偶圖. 注意: 這兩個(gè)平面嵌入是同一個(gè)平面圖的平面嵌入.,48,四色定理,四色猜想(19世紀(jì)50年代, 德摩根) ?? 五色定理(1890年, 希伍

43、德) ?? 四色定理(1976年, 阿佩爾與黑肯)定理11.17 任何平面圖都是4-可著色的.,49,第十一章 習(xí)題課,主要內(nèi)容歐拉通路與歐拉回路, 歐拉圖與半歐拉圖及判別哈密頓通路與哈密頓回路, 哈密頓圖與半哈密頓圖及判別貨郎問(wèn)題二部圖及其判別二部圖匹配及相關(guān)概念二部圖最大匹配的充要條件, 存在完備匹配的條件平面圖及其性質(zhì)(歐拉公式)平面圖的判別著色問(wèn)題地圖著色與平面圖的對(duì)偶圖四色定理應(yīng)用,50,基本要求

44、,基本要求深刻理解歐拉圖, 半歐拉圖, 哈密頓圖, 半哈密頓圖的定義掌握歐拉圖, 半歐拉圖的判別會(huì)用哈密頓圖與半哈密頓圖的必要條件和充分條件會(huì)一筆畫(huà)出歐拉回路了解貨郎問(wèn)題深刻理解二部圖的定義, 掌握二部圖的判別深刻理解二部圖匹配及相關(guān)概念了解二部圖最大匹配的充要條件, 會(huì)用存在完備匹配的條件(Hall定理與t條件),51,基本要求,深刻理解平面圖及相關(guān)的概念牢記極大平面圖的主要性質(zhì)和判別方法熟記歐拉公式及推廣形式，并

45、能用歐拉公式及推廣形式證明有關(guān)定理與命題會(huì)用庫(kù)拉圖斯基定理證明非平面圖 了解對(duì)偶圖的概念了解著色問(wèn)題, 地圖著色問(wèn)題和四色定理會(huì)用上述概念和有關(guān)定理解決簡(jiǎn)單的實(shí)際問(wèn)題,52,1. 設(shè)G為n(n?2)階無(wú)向歐拉圖, 證明G中無(wú)橋.,證二 用反證法. 假設(shè)e=(u,v)是橋, 則G?e產(chǎn)生兩個(gè)連通分支G1, G2, 不妨設(shè)u在G1中, v在G2中. G中沒(méi)有奇度頂點(diǎn), 而刪除e,只使u,v 的度數(shù)各減1, 因而G1(G2)中只含

46、一個(gè)奇度頂點(diǎn), 與任何圖中奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù)矛盾.,練習(xí)1,證一 設(shè)C為G中一條歐拉回路, ?e?E(G), e在C上, C?e 連通, G?e也連通, 所以e不為橋.,53,2. 證明右圖不是哈密頓圖.,證一 取 V1 = {a, c, e, h, j, l}， p(G?V1) = 7 > 6=|V1|,練習(xí) 2,證二 G為二部圖, V1 = {a, c, e, h, j, l},

47、 V2 = {b, d, f, g, i, k, m}, |V1| ? |V2|.,證三 n = 13, m = 21. h, l, j為4度頂點(diǎn), a, c, e為3度頂點(diǎn), 且它們關(guān)聯(lián)不相同的邊. 而在哈密頓回路上, 每個(gè)頂點(diǎn)關(guān)聯(lián)兩條邊, 于是可能用于哈密頓回路的邊至多有21?(3?2+3?1) = 12. 12條邊不可能構(gòu)成經(jīng)過(guò)13個(gè)頂點(diǎn)的回路.,54,3．某次國(guó)際會(huì)議8人參加, 已知每人至少與其余7人中

48、的4人能用相同的語(yǔ)言, 問(wèn)服務(wù)員能否將他們安排在同一張圓桌就座, 使得每個(gè)人都能與兩邊的人交談？,解 做無(wú)向圖G=, 其中V={v| v為與會(huì)者}， E={(u,v) | u,v?V, u與v有能用相同的語(yǔ)言, 且u ? v}. G為簡(jiǎn)單圖且?v?V, d(v)?4. 于是, ?u,v?V, d(u)+d(v) ? 8,故G為哈密頓圖. 服務(wù)員在G中找一條哈密頓回路, 按回路中相鄰關(guān)系安排座位即可.,練

49、習(xí) 3,55,4. 某公司招聘了3名大學(xué)畢業(yè)生, 有5個(gè)部門(mén)需要人. 部門(mén)領(lǐng)導(dǎo)與畢業(yè)生交談后, 雙方都愿意的結(jié)果如表所示. 如果每個(gè)部門(mén)只能接收一名畢業(yè)生, 問(wèn)這3名畢業(yè)生都能到他滿(mǎn)意的部門(mén)工作嗎?試給出分配方案.,練習(xí) 4,解 作二部圖G=,一個(gè)分配方案是G的一個(gè)匹配. G滿(mǎn)足t條件, t=3, 有完備匹配.,如, A?1, B ?2, C ?3; A ?3, B ?2, C ?5等.,56,練習(xí)5,解 設(shè)G的階數(shù)

50、, 邊數(shù), 面數(shù)分別為n, m, r. (1) 用反證法. 假設(shè)所有面的次數(shù)大于等于5, 由歐拉公式得 2m? 5r = 5 (2+m?n) ①由?(G)?3及握手定理有 2m ? 3n ②得 m?30又有 r=2+m?n <12 ③ ③ 與

51、②又可得 m<30, 矛盾.,5. 設(shè)G是連通的簡(jiǎn)單平面圖, 面數(shù)r<12, ?(G)?3. (1) 證明G中存在次數(shù)?4的面.(2) 舉例說(shuō)明當(dāng)r=12時(shí), (1) 中結(jié)論不真.,(2) 正十二面體是一個(gè)反例,57,6. 設(shè)G是階數(shù)?11的非平凡簡(jiǎn)單無(wú)向圖, 證明G和 不可能全是平面圖.,練習(xí)6,58,7. 證明下圖為非平面圖,練習(xí)7,證一 含子圖K3,3:刪去頂點(diǎn)a和邊(c,d),

52、證二 含與K5同胚的子圖: 刪去(a,f), 收縮(a,e)和(f,g),59,練習(xí)8,8. 給下圖著色至少要用幾種顏色?,解 由于a, b, c 彼此相鄰, 至少要用3種顏色, 設(shè)它們分別著顏色1,2,3. 最少還要用這三種顏色給d, e, f 著色. 而g與d, e, f相鄰只能用第4種顏色. 故至少要用4種顏色.,60,練習(xí)9,9. 某校計(jì)算機(jī)系三年級(jí)學(xué)生在本學(xué)期共有6門(mén)選修課Ci, i=1, 2, …, 6. 設(shè)S(Ci)

53、為選Ci課的學(xué)生集. 已知 S(Ci)?S(C6) ? ?, i=1, 2, …, 5， S(Ci)?S(Ci+1) ? ?, i=1, 2, 3, 4， S(C5)?S(C1) ? ?. 問(wèn)這6門(mén)課至少幾天能考完？,解 做無(wú)向圖G=, 其中 V={C1, C2, …, C6}