1、Discrete Mathematics離散數(shù)學(xué)講義（電子版）天津財(cái)經(jīng)大學(xué) 信息科學(xué)與技術(shù)系 王寧1第四篇 圖論2圖論的誕生圖論哥尼斯堡七橋問題1736年，瑞士數(shù)學(xué)家歐拉（Euler）證明“哥尼斯堡七橋問題”無解圖論創(chuàng)始年。1936年，匈牙利數(shù)學(xué)家寇尼格（Konig）出版了圖論的第一部專著有限圖與無限圖理論。3圖論的特點(diǎn)圖論（續(xù)）只關(guān)心點(diǎn)之間是否有連線，而不關(guān)心點(diǎn)的 位置以及連線的曲直。與幾何學(xué)的區(qū)別可直觀地表示離散對(duì)象之間的相互關(guān)系。4圖論的應(yīng)用廣泛應(yīng)用于計(jì)算機(jī)科學(xué)、物理學(xué)、化學(xué)、運(yùn)籌學(xué)、信息論、控制論、網(wǎng)絡(luò)通訊、社會(huì)科學(xué)以及經(jīng)濟(jì)管理、軍事、國防、工農(nóng)業(yè)生產(chǎn)等方面異軍突起，活躍非凡圖論（續(xù)）

2、5 18世紀(jì)時(shí)，歐洲有一個(gè)風(fēng)景秀麗的小城哥尼斯堡，那里有七座橋。如圖1所示：河中的小島A與河的左岸B、右岸C各有兩座橋相連結(jié)，河中兩支流間的陸地D與A、B、C各有一座橋相連結(jié)。當(dāng)時(shí)哥尼斯堡的居民中流傳著一道難題：一個(gè)人怎樣才能一次走遍七座橋，每座橋只走過一次，最后回到出發(fā)點(diǎn)？大家都試圖找出問題的答案，但是誰也解決不了這個(gè)問題 這個(gè)問題無解哥尼斯堡七橋問題(Seven bridges of Knigsberg problem): River Pregel, Kaliningrad, Russia圖論（續(xù)）6“七橋問題”的圖論解法1736年,圖論和拓?fù)鋵W(xué)誕生CBADcdabfge圖論（續(xù)）7Leo

3、nhardEuler(1707-1783)瑞士數(shù)學(xué)家對(duì)數(shù)學(xué)多個(gè)領(lǐng)域做出貢獻(xiàn)最多產(chǎn)的數(shù)學(xué)家，一生發(fā)表1100多篇論著（論文）。死后47年才出版完其全部論著。圖論（續(xù)）8第七章 圖論9第七章 圖論本章包括以下內(nèi)容：7-1 圖的基本概念7-2 路與回路7-3 圖的矩陣表示7-4 歐拉圖與漢密爾頓圖7-5 平面圖7-6 對(duì)偶圖與著色7-7 樹與生成樹7-8 根樹及其應(yīng)用107-1 圖的基本概念圖的定義三元組G =V(G)，E(G)，j(G)，稱為一個(gè)圖：(1) V , 頂點(diǎn)集,其中元素稱為頂點(diǎn)或結(jié)點(diǎn)(vertex / node)。(2) E(G)，邊集，其中元素稱為邊(edge / link)(3)

4、j(G)表示V與E之間的關(guān)系，是從邊集E到結(jié)點(diǎn)無序偶（有序偶）集合上的函數(shù)。abej(e)=(a,b)j(e)=a,babe11 一般用就G =V，E來表示圖。 用|V(G)|表示G的頂點(diǎn)數(shù) 用|E(G)|表示G的邊數(shù)7-1 圖的基本概念注：圖中的邊總與兩個(gè)結(jié)點(diǎn)相關(guān)聯(lián)。也就是說，不存在只有邊沒有結(jié)點(diǎn)的圖。abeabe12（1）若邊e與結(jié)點(diǎn)u,v的無序偶（記作(u,v)）相關(guān)聯(lián)，則稱該邊為無向邊，每一條邊都為無向邊的圖稱為無向圖。7-1 圖的基本概念（2）若邊e與結(jié)點(diǎn)u,v的有序偶（記作u,v）相關(guān)聯(lián)，則稱該邊為有向邊，每一條邊都為有向邊的圖稱為有向圖。（3）圖中一些邊為有向邊，一些邊為無向邊，

5、則稱該圖為混合圖。無向圖，有向圖，混合圖13v1v4v2v3e5e2e4e6e3e1例如：右圖為無向圖G=V,E,7-1 圖的基本概念（續(xù)）v1v4v2v3e6e2e5e3e4e1V=v1, v2, v3, v4E=e1, e2, e3, e4, e5, e6：e1= (v1,v1) e2= (v1,v2) e3= (v2,v3) e4= (v3,v4) e5= (v4,v1) e6= (v4,v2) 例如：右圖為有向圖D=V,E,V=v1, v2, v3, v4E=e1, e2, e3, e4, e5, e6：e1=v1,v1 e2=v1,v2 e3=v2,v3 e4=v3,v4 e5=v1

6、,v4 e6=v2,v414鄰接(adjacent)點(diǎn)：圖中兩個(gè)結(jié)點(diǎn)由一條有向（或無向）邊關(guān)聯(lián)。術(shù)語7-1 圖的基本概念（續(xù)）uv鄰接邊：關(guān)聯(lián)于同一結(jié)點(diǎn)的兩條邊。n階圖(order-n graph)：|V(G)|=n有限圖(finite graph)：|V(G)|，且|E(G)|W(G); (2) 極小性: VV，W(G-V)=W(G)。則稱V為點(diǎn)割集。割點(diǎn)：若某一個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)點(diǎn)割集，則稱該結(jié)點(diǎn)為割點(diǎn)。說明: “極小性”是為了保證點(diǎn)割集概念的非平凡性39G1: f, a,e,c, g,k,j, b,e,f,k,hG2: f, a,e,c, g,k,j, b,e,f,k,habcdfeghkj

7、iabcefdjighkG2G17-2 路與回路（續(xù)）割點(diǎn): v是割點(diǎn) v是割集G1中f是割點(diǎn), G2中無割點(diǎn) 定理：一個(gè)連通無向圖G中的結(jié)點(diǎn)v是割點(diǎn)的充要條件是存在兩個(gè)結(jié)點(diǎn)u和w，使得結(jié)點(diǎn)u和w之間的每一條路都通過v。40如何定義點(diǎn)連通度?為了破壞連通性,至少需要?jiǎng)h除多少個(gè)頂點(diǎn)?說明：“破壞連通性”指 p(G-V)p(G), 或p(G-E)p(G),即“變得更加不連通”。點(diǎn)連通度：k(G)=min|V| | V是G的點(diǎn)割集 。定義7-2 路與回路（續(xù)）注：k(G)是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的點(diǎn)的最少數(shù)目。不連通圖的連通度為0；存在割點(diǎn)的連通圖的連通度為1完全圖Kp中，刪去任何m（mW(G

8、); (2) 極小性: EE，W(G-E)=W(G)。則稱E為邊割集。割邊：若某一個(gè)邊構(gòu)成一個(gè)邊割集，則稱該邊為割邊或橋。說明: “極小性”是為了保證點(diǎn)割集概念的非平凡性43e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是邊割集.邊割集舉例7-2 路與回路（續(xù)）44G1: (a,f),(e,f),(d,f), (f,g),(f,k),(j,k),(j,i)(a,f),(e,f),(d,f),(f,g),(f,k),(f,j)G2: (b,a),(b,e),(b,c)acdfeghkjiabcefdjighkG1G2邊割集舉例7-2 路與回路（續(xù)）45邊連通

9、度： l (G)=min|V| | V是G的點(diǎn)割集為G的邊連通度。定義7-2 路與回路（續(xù)）定理：對(duì)任何一個(gè)圖G，有k(G) l(G) (G) = min degG(v) | vV(G) 注：點(diǎn)連通度 邊連通度 圖的最小度 圖的最大度注：l (G)是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的邊的最少數(shù)目。 平凡圖的連通度為0；不連通圖的連通度也為0。46邊連通度(edge-connectivity)例: (G)=1, (H)=2, (F)=3, (K5)=4邊連通度越大，邊連通程度越高。GHF7-2 路與回路（續(xù)）注：無向圖的連通性不能直接推廣到有向圖。477-2 路與回路（續(xù)）可達(dá)：有向圖G中，從結(jié)點(diǎn)u

10、到v存在一條路，稱從u可達(dá)v。定義 有向圖的連通性注：可達(dá)關(guān)系不是等價(jià)關(guān)系，滿足自反，傳遞，但是一般不滿足對(duì)稱性。距離：在所有u可達(dá)v的路中，最短路的長(zhǎng)度稱為結(jié)點(diǎn)u和v之間的距離（或短程線）。記作du,v。它滿足（1）du,v 0（2） du,u = 0（3） du,v+ dv,w du,w圖的直徑：D=maxu,vVdu,v487-2 路與回路（續(xù)）簡(jiǎn)單有向圖G中單側(cè)連通：任何一對(duì)結(jié)點(diǎn)間至少有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的，責(zé)成圖G為單側(cè)連通的。強(qiáng)連通：如果對(duì)于圖G的任何一對(duì)結(jié)點(diǎn)兩者之間是相互可達(dá)的，則稱這個(gè)圖是強(qiáng)連通的。弱連通：如果圖G中略去邊的方向，將它看成無向圖后圖是連通的，則稱該圖為弱

11、連通的。注：強(qiáng)連通 單側(cè)連通 弱連通強(qiáng)分圖：具有強(qiáng)連通性質(zhì)的最大子圖。單側(cè)分圖：具有單側(cè)連通性質(zhì)的最大子圖。弱分圖：具有弱連通性質(zhì)的最大子圖。49可達(dá)性舉例baedcced ced強(qiáng)連通分支: Ga,Gb,Gc,e,dabeabdcedc7-2 路與回路（續(xù)）50弱連通(weakly connected)abcdejfghiabcdejfghi7-2 路與回路（續(xù)）51單向連通abcdejfghiabejficdgh7-2 路與回路（續(xù)）52強(qiáng)連通(strongly connected)abejficdgh7-2 路與回路（續(xù)）53各種連通間關(guān)系：強(qiáng)連通 單側(cè)連通 弱連通強(qiáng)連通單向連通弱連通7

12、-2 路與回路（續(xù)）54強(qiáng)連通圖判別定理證明: () 顯然() 設(shè)V(D)=v1,v2,vn, 設(shè)I,j是從vl到vj的有向通路, 則1,2+2,3+n-1,n+n,1是過每個(gè)頂點(diǎn)至少一次的回路. #定理：有向圖G強(qiáng)連通 G中有經(jīng)過每個(gè)頂點(diǎn)至少一次的回路.定理：有向圖G中，每一個(gè)結(jié)點(diǎn)位于且只位于一個(gè)強(qiáng)分圖中。7-2 路與回路（續(xù)）說明: 不一定有簡(jiǎn)單回路,反例如圖：55圖的鄰接矩陣：設(shè)G=V，E是一個(gè)簡(jiǎn)單圖，它有n個(gè)結(jié)點(diǎn)依序排列V=v1,v2,vn，則n階方陣A(G)=(aij)稱為G的鄰接矩陣。其中7-3 圖的矩陣表示注：簡(jiǎn)單無向圖的鄰接矩陣為對(duì)稱的，簡(jiǎn)單有向圖的鄰接矩陣不一定對(duì)稱。例如：5

13、6置換等價(jià)：對(duì)于給定圖G，顯然不會(huì)因結(jié)點(diǎn)編序不同而使其結(jié)構(gòu)發(fā)生任何變化，即圖的結(jié)點(diǎn)所有不同的編序?qū)嶋H上仍表示同一個(gè)圖。換句話說，這些結(jié)點(diǎn)的不同編序的圖都是同構(gòu)的，并且它們的鄰接矩陣都是相似的。于是GH存在置換矩陣P，使A(H)=P-1A(G)P今后將略去這種由于V中結(jié)點(diǎn)編序而引起鄰接矩陣的任意性，而取該圖的任一個(gè)鄰接矩陣作為該圖的矩陣表示。7-3 圖的矩陣表示（續(xù)）注：（1）由鄰接矩陣A可以讀出結(jié)點(diǎn)vi的出度：第i行中值為1的元素?cái)?shù)目；入度：第i列中值為1的元素?cái)?shù)目。（2）零圖（僅由孤立結(jié)點(diǎn)組成的圖） 零矩陣57 分別表示i和j之間長(zhǎng)度為2，3，4的路徑數(shù)。7-3 圖的矩陣表示（續(xù)）定理：設(shè)圖

14、G的鄰接矩陣A(G)，則(A(G)l中的i行j列元素aij(l)等于G中連接vi與vj的長(zhǎng)度為l路的數(shù)目。連接vi與vj的長(zhǎng)度為l路的數(shù)目ij587-3 圖的矩陣表示（續(xù)）圖的可達(dá)性矩陣：設(shè)G=V, E是簡(jiǎn)單有向圖，|V|=n，給定G的結(jié)點(diǎn)的一個(gè)編序V=v1,v2,vn，定義一個(gè)nn矩陣P=(pij)，它的元素為：則P稱為圖G的可達(dá)性矩陣。注：對(duì)于無向圖，將每條無向邊看作方向相反的兩條邊，則可轉(zhuǎn)化為有向圖討論。 圖的可達(dá)性矩陣計(jì)算方法：（1）由圖的鄰接矩陣A可計(jì)算出可達(dá)性矩陣，令Bn=A+A2+.+An，若Bn中(i,j)是非“0”元素，則對(duì)應(yīng)的pij=1，否則pij=0。（2）將矩陣A，A2

15、，.，An分別改為布爾矩陣A，A(2)，.，A(n)，則P=AA(2).A(n)=Mt(R) 597-3 圖的矩陣表示（續(xù)）無向圖的完全關(guān)聯(lián)矩陣：設(shè)無向圖G，結(jié)點(diǎn)和邊分別記作v1,v2,vp，e1,e2,eq，則矩陣M(G)=(mij)pq，它的元素為：稱為完全關(guān)聯(lián)矩陣。性質(zhì)：（1）M(G)的每一列中只有兩個(gè)1（表示圖的每一條邊關(guān)聯(lián)兩個(gè)結(jié)點(diǎn)）。 （2）每一行中元素的和數(shù)是對(duì)應(yīng)的結(jié)點(diǎn)數(shù)。（3）一行中元素全為0對(duì)應(yīng)孤立結(jié)點(diǎn)。（4）兩個(gè)平行邊對(duì)應(yīng)的兩列相同。（5）同一個(gè)圖結(jié)點(diǎn)或邊的編序不同時(shí)，其對(duì)應(yīng)的M(G)只有行序，列序的差別。607-3 圖的矩陣表示（續(xù)）例：有向圖的完全關(guān)聯(lián)矩陣：設(shè)簡(jiǎn)單有向圖G

16、=V，E，V=v1,v2,vp，E=e1,e2,eq，矩陣M(G)=(mij)pq：稱為完全關(guān)聯(lián)矩陣。617-3 圖的矩陣表示（續(xù)）完全關(guān)聯(lián)矩陣的運(yùn)算： 將完全關(guān)聯(lián)矩陣的兩行相加 將相應(yīng)的兩個(gè)結(jié)點(diǎn)vi和vj合并成一個(gè)結(jié)點(diǎn)vij。規(guī)則：（1）若 ，則結(jié)點(diǎn)vij是er的端點(diǎn)（起點(diǎn)或終點(diǎn)）。（2）若 ，則a）vi和vj都不是er的端點(diǎn)，則vij也不是er的端點(diǎn)。b）vi和vj都是er的端點(diǎn)，則er為vij的自回路，在簡(jiǎn)單圖中，可將自回路刪去。（3）若M(G)中某些列變成全為0，則該列所對(duì)應(yīng)的邊消失。627-3 圖的矩陣表示（續(xù)）定理：設(shè)連通圖G有r個(gè)結(jié)點(diǎn)，則其完全關(guān)聯(lián)矩陣M(G)的秩rank M(G

17、) = r-1。推論：設(shè)圖G有r個(gè)結(jié)點(diǎn)，w個(gè)最大連通子圖，則圖G的完全關(guān)聯(lián)矩陣M(G)的秩rank M(G) = r-w。637-4 歐拉圖與漢密爾頓圖哥尼斯堡七橋問題(Seven bridges of Knigsberg problem): River Pregel, Kaliningrad, Russia“七橋問題”的圖論解法1736年,圖論和拓?fù)鋵W(xué)誕生CBADcdabfge647-4 歐拉圖與漢密爾頓圖（續(xù)）定義：給定無孤立結(jié)點(diǎn)的圖G，若存在一條路，經(jīng)過圖中每邊一次且僅一次，該條路稱為歐拉路。若存在一條回路，經(jīng)過圖中每邊一次且僅一次，該回路成為歐拉回路。具有歐拉回路的圖稱作歐拉圖。定理：

18、無向圖G具有一條歐拉路，當(dāng)且僅當(dāng)G是連通的，且有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)。推論：無向圖G具有一條歐拉回路，當(dāng)且僅當(dāng)G是連通的，且所有結(jié)點(diǎn)度數(shù)全為偶數(shù)。注：若無奇度數(shù)頂點(diǎn)，則通路為回路。若有兩個(gè)奇度數(shù)頂點(diǎn)，則它們必定是G中每條歐拉通路的兩個(gè)端點(diǎn)。657-4 歐拉圖與漢密爾頓圖（續(xù)）定義：給定有向圖G，通過圖中每邊一次且僅一次的一條單向路（回路），稱作單向歐拉路（回路）。定理：有向圖G具有一條單向歐拉回路，當(dāng)且僅當(dāng)G是連通的，且每個(gè)結(jié)點(diǎn)的入度等于出度。一個(gè)有向圖G具有單向歐拉路，當(dāng)且僅當(dāng)它是連通的，而且除兩個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)的入度等于出度，而這兩個(gè)結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大1，另一個(gè)結(jié)點(diǎn)的入度比出

19、度小1。66歐拉圖舉例：（跳馬問題）. 在8x8國際象棋盤上跳動(dòng)一只馬，不論跳動(dòng)方向如何，問這只馬是否可能一次（恰好一次）完成所有的跳動(dòng)？7-4 歐拉圖與漢密爾頓圖（續(xù)）672度頂點(diǎn)2222跳馬問題-8x8國際象棋棋盤7-4 歐拉圖與漢密爾頓圖（續(xù)）683度頂點(diǎn)333333337-4 歐拉圖與漢密爾頓圖（續(xù)）跳馬問題-8x8國際象棋棋盤694度頂點(diǎn)444444444444444444447-4 歐拉圖與漢密爾頓圖（續(xù)）跳馬問題-8x8國際象棋棋盤706度頂點(diǎn)66666666666666667-4 歐拉圖與漢密爾頓圖（續(xù)）跳馬問題-8x8國際象棋棋盤718度頂點(diǎn)88888888888888887

20、-4 歐拉圖與漢密爾頓圖（續(xù)）跳馬問題-8x8國際象棋棋盤727-4 歐拉圖與漢密爾頓圖（續(xù)）跳馬問題-8x8國際象棋棋盤732344443222333344444444444433444466666666666666668888888888888888有8個(gè)3度頂點(diǎn)7-4 歐拉圖與漢密爾頓圖（續(xù)）跳馬問題-8x8國際象棋棋盤747-4 歐拉圖與漢密爾頓圖（續(xù)）周游世界問題與漢密爾頓圖 用正十二面體的每個(gè)頂點(diǎn)代表一個(gè)城市，沿著正十二面體的棱尋找一條旅行路線，通過每個(gè)城市恰好一次又回到出發(fā)城市。這便是Hamilton回路問題。 757-4 歐拉圖與漢密爾頓圖（續(xù)）定義：給定圖G，若存在一條路經(jīng)過

21、圖中每個(gè)結(jié)點(diǎn)恰好一次，這條路稱作漢密爾頓(Hamilton)路。若存在一條回路經(jīng)過圖中每個(gè)結(jié)點(diǎn)恰好一次，這條路稱作Hamilton回路。具有漢密爾頓回路的圖稱作Hamilton圖。例如：由m個(gè)節(jié)點(diǎn)構(gòu)成的完全圖Km顯然是Hamilton圖。定理：（漢密爾頓回路的必要條件） 若圖G=V, E具有漢密爾頓回路，則對(duì)于結(jié)點(diǎn)集V的每個(gè)非空子集S均有W(G-S) |S|成立。其中W(G-S)是G-S中連通分支數(shù)。定理：（漢密爾頓路的充分條件） 設(shè)G是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，如果G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n-1（n），則在G中存在一條漢密爾頓路（漢密爾頓回路）。767-4 歐拉圖與漢密爾頓圖（續(xù)）例1：取

22、X=V1,V3，則|X|=2。W(G-X)=3，W(G-X)|X|由定理知，該圖不是Hamilton圖。V6V7V5V8V2V4G-XV1V6V7V5V8V2V3V4G77Gfade123cbG-a,b,cfde123例2：7-4 歐拉圖與漢密爾頓圖（續(xù)）取X =a,b,c ，則|X|=3。W(G-X)=4，W(G-X)|X|由定理知，該圖不是Hamilton圖。78關(guān)于Hamilton路和Hamilton回路下面的性質(zhì)是顯然的1. 若圖中有一點(diǎn)的度為1，則無Hamilton回路。2. 若圖中有一點(diǎn)的度為0，則既無Hamilton路，又無Hamilton回路。3. 設(shè)圖中有一點(diǎn)的度為2，若有H

23、amilton回路，則以此點(diǎn)為端點(diǎn)的兩條邊均出現(xiàn)在此回路中。4. 設(shè)圖中有一點(diǎn)的度大于2，若有Hamilton回路，則只用其中的兩條邊。 7-4 歐拉圖與漢密爾頓圖（續(xù)）797-4 歐拉圖與漢密爾頓圖（續(xù)）定義：給定圖G =V, E有n個(gè)結(jié)點(diǎn)，若將圖G中度數(shù)之和至少是n的非鄰接結(jié)點(diǎn)連接起來得圖G，對(duì)圖G重復(fù)上述步驟，直到不再有這樣的結(jié)點(diǎn)對(duì)存在為止，所得到的圖，稱為原圖G的閉包，記作C(G)。定理：（漢密爾頓圖的充要條件） 當(dāng)且僅當(dāng)一個(gè)簡(jiǎn)單圖的閉包是漢密爾頓圖時(shí)，這個(gè)簡(jiǎn)單圖是漢密爾頓圖。漢密爾頓回路（漢密爾頓圖）的判定定理：807-4 歐拉圖與漢密爾頓圖（續(xù)）例3：G1e5234abcd81例4

24、：跳馬問題7-4 歐拉圖與漢密爾頓圖（續(xù)）82跳馬問題跳動(dòng)路線22322333333344447-4 歐拉圖與漢密爾頓圖（續(xù)）832232233333334444跳馬問題跳動(dòng)路線7-4 歐拉圖與漢密爾頓圖（續(xù)）84X=4,4,4,4，p(G-X)=6|X|跳馬問題跳動(dòng)路線7-4 歐拉圖與漢密爾頓圖（續(xù)）85解：用“最臨近方法”求解。以5個(gè)城鎮(zhèn)為例，得到完全圖K5。以a為起始點(diǎn)的路徑是：adbeca。長(zhǎng)度為：47。例3：流動(dòng)售貨員問題 設(shè)有一名售貨員要從商店出發(fā)，行銷附近的所有城鎮(zhèn)后回到商店。他應(yīng)如何安排路線，才能使旅行的總距離為最??？7-4 歐拉圖與漢密爾頓圖（續(xù)）125a598498167b

25、cde867-5 平面圖平面圖的引入：電子線路板布線問題，相交的布線會(huì)導(dǎo)致短路，抽象為圖論問題，即邊與邊不能相交。 先看一個(gè)例子：有六個(gè)結(jié)點(diǎn)的圖如右，試問：能否轉(zhuǎn)變成與其同構(gòu)的，但沒有任何交線的平面上的圖？877-5 平面圖定義：設(shè)G是一個(gè)無向圖，若能把G的所有結(jié)點(diǎn)一個(gè)無向圖G=V，E，如果能把它畫在平面上，且除V中的結(jié)點(diǎn)外，任意兩條邊均不相交，則稱該圖G為平面圖。面：由連通平面圖中的邊所包圍的區(qū)域，在區(qū)域內(nèi)既不包含圖的結(jié)點(diǎn)，也不包含圖的邊。邊界：包圍該面的各邊所構(gòu)成的回路。次數(shù)：面的邊界的回路長(zhǎng)度。定理：一個(gè)有限平面圖，面的次數(shù)之和等于其邊數(shù)的兩倍。887-5 平面圖（續(xù)）討論定義：（1）平

26、面上的圖，一開始就畫成如定義所講的圖；（2）原來在平面上的圖形似交叉，但經(jīng)過若干次的改畫后，變成符合定義所規(guī)定的圖；例：（3）并非所有的圖經(jīng)過處理之后都可變?yōu)槠矫鎴D。897-5 平面圖（續(xù)）如何判斷一個(gè)圖是否為平面圖，介紹以下幾種方法：1.觀察法（直觀方法）：找出基本循環(huán)，將交叉的邊分別放置在基本循環(huán)內(nèi)或外而避免交叉。根據(jù)平面的定義，無圈的圖顯然是平面圖。故，研究圖的平面性問題，只需要限制有圈的一類圖即可。判別方法是：(1) 對(duì)于有圈的圖找出一個(gè)長(zhǎng)度盡可能大的且邊不相交的基本圈。(2) 將圖中那些相交于非結(jié)點(diǎn)的邊，適當(dāng)放置在已選定的基本圈內(nèi)側(cè)或外側(cè)，若能避免除結(jié)點(diǎn)之外邊的相交，則該圖是平面圖；

27、否則，便是非平面圖。902.歐拉定理定理：（歐拉定理）設(shè)有一個(gè)連通的平面圖G共有v個(gè)結(jié)點(diǎn)e條邊和r個(gè)面，則歐拉公式v-e+r=2成立。推論：設(shè)有一個(gè)連通的簡(jiǎn)單平面圖G共有v個(gè)結(jié)點(diǎn)e條邊，若v3，則e3v-6。 定理和推論給出了是平面圖的必要條件，若不滿足這些條件，則一定不是平面圖。例如：7-5 平面圖（續(xù)）K591兩個(gè)重要的非平面圖： K3,3和K5 在圖論中，稱K3,3和K5是庫拉圖斯基圖。這是因?yàn)椴ㄌm數(shù)學(xué)家?guī)炖瓐D斯基(K.Kuratowski)于1930年給出了的判別平面圖充要條件(后稱庫拉圖斯基定理)曾用到這兩個(gè)圖。7-5 平面圖（續(xù)）92 下面就來介紹庫拉圖斯基定理，不過它要用到兩個(gè)圖

28、同胚的概念。給定兩個(gè)圖，我們做以下的工作：在左邊圖的中間聯(lián)線上插入一個(gè)度數(shù) 為2的結(jié)點(diǎn)，則把一條邊分成了二條邊；(2)在右邊圖中去掉一個(gè)度數(shù)為2的結(jié)點(diǎn)， 則把二條邊變成一條邊。此二項(xiàng)工作不會(huì)影響圖的平面性。稱作2度結(jié)點(diǎn)內(nèi)同構(gòu)（同胚）。例如：7-5 平面圖（續(xù)）93定義：設(shè)G1、G2是兩個(gè)圖，如果它們是同構(gòu)的，或可以通過反復(fù)插入或刪除度數(shù)為2的結(jié)點(diǎn)，使得G1和G2同構(gòu)，則稱G1 、 G2為2度結(jié)點(diǎn)內(nèi)同構(gòu)（同胚）。定理：（庫拉圖斯基定理）一個(gè)圖G是平面圖G中不含與K3,3或K5的在2度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖。平面圖的充要條件7-5 平面圖（續(xù)）947-5 平面圖（續(xù)） 例如：彼得森圖（圖(a)）是非平面

29、圖。因?yàn)楫?dāng)刪去邊v6,v8和v3,v4時(shí)，它成為含有同胚于K3,3的子圖，如圖 (b)或(c)所示。957-6 對(duì)偶圖與著色 平面圖的著色問題，最早起源于地圖的著色。在一張地圖中，若相鄰國家著以不同的顏色，那么最少需要多少種顏色呢？1840年，德國數(shù)學(xué)家麥比烏斯(A.F.Mbius)在他的講稿中第一次提出了確信用四種顏色可以對(duì)地圖著色的問題(以下簡(jiǎn)稱四色猜想)。1879年肯普(Kempe)給出了這個(gè)猜想的第一個(gè)證明，但到1890年希伍德(Hewood)發(fā)現(xiàn)肯普證明是有錯(cuò)誤的，然而他指出了肯普的方法雖不能證明地圖著色用四種顏色就夠了，但卻可以證明用五種顏色是夠的，即五色定理成立。 在這里，研究的

30、方法并不直接去考察地圖著色問題，而是把它轉(zhuǎn)化成平面圖。為此，先給出對(duì)偶圖的概念。967-6 對(duì)偶圖與著色（續(xù)）定義：給定平面圖G=V，E，具有面F1，F(xiàn)2，F(xiàn)n。若有圖G*=V*，E*滿足下列條件：(1) 對(duì)于任意面Fi內(nèi)部有且僅有一個(gè)結(jié)點(diǎn)v*i V*；(2) 對(duì)于G中面Fi和面Fj的公共邊ek有且僅有一條邊e*kE*，使得ek*=v*i，v*j且e*k與ek相交；(3) 當(dāng)且僅當(dāng)ek只是一個(gè)面fi的邊界時(shí)，v*i存在一個(gè)環(huán)ek*且e*k與ek相交。則稱圖G*是圖G的對(duì)偶圖。定義：若圖G的對(duì)偶圖G*同構(gòu)于G，則稱G是自對(duì)偶圖。*定理：若平面圖G=V，E是自對(duì)偶圖，則|E|=2(|V|-1)97

31、7-6 對(duì)偶圖與著色（續(xù)）98 從對(duì)偶圖的定義可以看出，若G*=V*，E*是平面圖G=V，E的對(duì)偶圖，則G也G*的對(duì)偶圖。 一個(gè)連通平面圖G的對(duì)偶圖G*，也是平面圖。 從對(duì)偶圖的定義容易知道，對(duì)于地圖的著色問題，可以化為一種等價(jià)的對(duì)于平面圖的結(jié)點(diǎn)的著色問題。因此，四色問題可以歸結(jié)為要證明：對(duì)任意平面圖一定可以用四種顏色，對(duì)其結(jié)點(diǎn)進(jìn)行著色，使得相鄰結(jié)點(diǎn)都有不同顏色。7-6 對(duì)偶圖與著色（續(xù)）99 平面圖G=V，E的著色是從結(jié)點(diǎn)集V到顏色集C=c1，c2，cn上一個(gè)映射，使對(duì)任意邊vi，vjE均有(vi)(vj)，即對(duì)G的每個(gè)結(jié)點(diǎn)指派一種顏色，使得相鄰結(jié)點(diǎn)都有不同的顏色。 對(duì)于平面圖G著色時(shí)，需要

32、的最少顏色數(shù)稱為G的著色數(shù)，記為x(G)。定理：對(duì)于n個(gè)結(jié)點(diǎn)的完全圖Kn，有x(Kn) = n。定理：設(shè)G為一個(gè)至少具有三個(gè)結(jié)點(diǎn)的連通平面圖，則G中必有一個(gè)結(jié)點(diǎn)u，使得deg(u) 5。7-6 對(duì)偶圖與著色（續(xù)）100*定理：（五色定理）對(duì)于任何簡(jiǎn)單平面圖G=V，E，均有x(G)5。由此定理及對(duì)偶圖定義，可得出下面定理。*定理：任何地圖M，M是五著色的，x(M)5。7-6 對(duì)偶圖與著色（續(xù)）101 自從四色猜想提出后，一百多年來，一直成為數(shù)學(xué)上的著名難題，它吸引許許多多的人，為之而作出大量辛勞，也得到很多重要結(jié)果，但長(zhǎng)久未能得到解決。直到1976年6月，由美國伊利諾斯大學(xué)兩名數(shù)學(xué)家愛普爾(K.

33、I.Apple)、黑肯(W.Haken)在考西(J.Koch)幫助下借助于電子計(jì)算機(jī)，用了一百多億次邏輯判斷，花了1200多機(jī)時(shí)才證明四色猜想是成立的，從此宣告，四色猜想成為四色定理。現(xiàn)將它敘述如下：*定理：（四色定理）對(duì)于任何簡(jiǎn)單平面圖G=V，E，均有x(G)4。相應(yīng)地可得出下面定理。*定理：任何地圖M，M是五著色的，x(M)4。7-6 對(duì)偶圖與著色（續(xù)）1027-7 樹與生成樹定義：連通無回路的無向圖，稱為無向樹，簡(jiǎn)稱樹。常用T表示樹樹都是無向簡(jiǎn)單圖1037-7 樹與生成樹（續(xù)）樹葉(leaf)：樹中1度頂點(diǎn)，即懸掛頂點(diǎn)。術(shù)語分支點(diǎn)：樹中2度及以上頂點(diǎn)平凡樹：平凡圖(無樹葉, 無分支點(diǎn))森

34、林(forest)：無回路的無向圖(不一定連通)。森林的每個(gè)連通分支都是樹leafleaf分支點(diǎn)104樹的等價(jià)定義定理：設(shè)G=V,E是n階m邊無向圖，則 (1) G是樹(連通無回路)。 (2) G中任何2頂點(diǎn)之間有唯一路徑。 (3) G無回路 m=n-1。 (4) G連通 m=n-1。 (5) G極小連通：連通 刪去任一邊后便不連通 (6) G極大無回路：無回路 增加任何新邊得到唯一回路。7-7 樹與生成樹（續(xù)）105證明思路：(1)(2)(3)(4)(5)(6)(1)(1) G是樹(連通無回)(2) G中任何2頂點(diǎn)之間有唯一路徑證明(1)(2)：u,vV，G連通，u,v之間的短程線是路徑.

35、如果u,v之間的路徑不唯一，則G中有回路，矛盾!定理1的證明：(1)(2)7-7 樹與生成樹（續(xù)）106 (2) G中任何2頂點(diǎn)之間有唯一路徑 (3) G無回路 m=n-1證明(2)(3): 任2點(diǎn)之間有唯一路徑無回路(反證: 有回路存在2點(diǎn),它們之間有2條路徑.) m=n-1(歸納法): n=1時(shí),m=0. 設(shè)nk時(shí)成立, 當(dāng)n=k+1時(shí), 任選1邊e, G-e有2個(gè)連通分支, m=m1+m2+1=(n1-1)+(n2-1)+1=n1+n2-1 =n-1. m1=n1-1m2=n2-1e定理1的證明：(2)(3)7-7 樹與生成樹（續(xù)）107 (3) G無回路 m=n-1 (4) G連通 m

36、=n-1證明(3)(4): G連通: 假設(shè)G有s個(gè)連通分支, 則每個(gè)連通分支都是樹, 所以 m=m1+m2+ ms=(n1-1)+(n2-1)+(ns-1) =n1+n2+ns-s=n-s=n-1, 所以s=1.m1=n1-1m2=n2-1ms=ns-1定理1的證明：(3)(4)7-7 樹與生成樹（續(xù)）108 (4) G連通 m=n-1 (5) G極小連通: 連通 刪去任一邊后便不連通證明(4)(5): 所有邊是橋: eE, G-e是n階(n-2)邊圖, 一定不連通(連通mn-1), 所以e是割邊. m=n-1em=n-2定理1的證明：(4)(5)7-7 樹與生成樹（續(xù)）109 (5) G極小

37、連通: 連通 刪去任一邊后便不連通 (6) G極大無回路: 無回路 增加任何新邊得唯一回路證明(5)(6): 所有邊是橋（刪去后便不連通）無回路. u,vV, G連通, u,v之間有唯一路徑, 則 (u,v)是唯一的回路。 定理1的證明：(5)(6)7-7 樹與生成樹（續(xù)）110 (6) G極大無回路: 無回路 增加任何新邊得唯一回路 (1) G是樹(連通無回)證明(6)(1): G連通: u,vV, G (u,v)有唯一的回路C, C-(u,v)是u,v之間的路徑. #定理1的證明：(6)(1)7-7 樹與生成樹（續(xù)）1117-7 樹與生成樹（續(xù)）定理：非平凡樹至少有2個(gè)樹葉。證明：設(shè)T有x

38、個(gè)樹葉， 2m = 2(n-1) = 2n-2 = d(v) = v是樹葉d(v) + v是分支點(diǎn)d(v) x + 2(n-x) = 2n-x 所以 x2。112無向樹的枚舉(enumeration)1-7階非同構(gòu)的n階無向樹n=1: n=2: n=3: n=4:n=5: 7-7 樹與生成樹（續(xù)）1136個(gè)頂點(diǎn)的所有非同構(gòu)無向樹7-7 樹與生成樹（續(xù)）1146個(gè)頂點(diǎn)的所有非同構(gòu)無向樹（另一種畫法）7-7 樹與生成樹（續(xù)）1157個(gè)頂點(diǎn)的所有非同構(gòu)無向樹7-7 樹與生成樹（續(xù)）116生成樹：TG、V(T)=V(G)且T是樹 （對(duì)照生成子圖的定義理解）樹枝(tree edge)：eE(T), n-

39、1條弦(chord)：eE(G)-E(T), m-n+1條補(bǔ)樹：T=GE(G)-E(T)術(shù)語7-7 樹與生成樹（續(xù)）1177-7 樹與生成樹（續(xù)）證明： () 顯然. () 破圈法. 定理：無向圖G連通 G有生成樹。1187-7 樹與生成樹（續(xù)）推論：G是n階m邊無向連通圖，則 mn-1。定義：假定G是一個(gè)n階m邊的連通圖，則G的生成樹正好有n-1條邊。因此要確定G的一棵生成樹，必須刪去G的m-(n-1)=m-n+1條邊。數(shù)m-n+1稱為連通圖G的秩。推論：T是n階m邊無向連通圖G的生成樹，則|E(T)|=m-n+1。定理：一條回路和任何一棵生成樹的補(bǔ)至少有一條公共邊。定理：一個(gè)邊割集和任何生

40、成樹至少有一條公共邊。1197-7 樹與生成樹（續(xù)）定義：假定G是一個(gè)n階連通圖，對(duì)應(yīng)于G的每一條邊e，指定一個(gè)正數(shù)G(e)，把C(e)稱為邊e的權(quán)（可以表示長(zhǎng)度、運(yùn)輸量、費(fèi)用等）。G的生成樹T的樹權(quán)C(T)為T的所有邊權(quán)的和。定義：圖G的所有生成樹中，樹權(quán)最小的那棵生成樹稱作最小的生成樹。1321.556231321.55623W(T1)=11.5W(T2)=18帶權(quán)樹的討論120證明：(1)(2)(3)(1)定理：設(shè)T是無向連通帶權(quán)圖G =V,E,W的生成樹，則 (1)T是G的最小生成樹 (2) eE(T), e是基本割集Se的最小邊 (3) eE(T), e是基本回路Ce的最大邊最小的生

41、成樹的性質(zhì)7-7 樹與生成樹（續(xù)）121 (1)T是G的最小生成樹 (2) eE(T), e是基本割集Se的最小邊證明： (1)(2): (反證) 假設(shè)弦eSe, W(e)W(e), 則T =(T-e) e是G的生成樹(T連通，且T與T邊數(shù)相同)。但W(T)=W(T)-W(e)+W(e)W(e), 則eSe, 與(2)矛盾!7-7 樹與生成樹（續(xù)）123eeTT (3) eE(T), e是基本回路Ce的最大邊 (1)T是G的最小生成樹證明：(3)(1): (逐步變形)設(shè)T是最小生成樹.若TT,則eE(T)-E(T).設(shè)e在T中的基本回路是Ce,則eE(Ce)-E(T). 由已知條件(3)得W(

42、e)W(e). 但是T=(T-e) e也是G的生成樹, W(T)W(T), T與T的公共邊更多. 把T當(dāng)作T重復(fù)進(jìn)行,最終T(k)=T, 所以W(T)=W(T(k) W(T) W(T). # (有bug: 重復(fù)進(jìn)行時(shí)T改變了)7-7 樹與生成樹（續(xù)）124 (3) eE(T), e是基本回路Ce的最大邊 (1) T是G的最小生成樹證明：(3)(1): (反證)假設(shè)TT是與T公共邊最多的最小生成樹(T滿足(3),(1)(3), 則eE(T)-E(T).設(shè)e在T中的基本回路是Ce,則eE(Ce) -E(T),W(e)W(e). eE(Ce)-E(T),滿足W(e)=W(e). 但是T=(T-e)

43、e也是G的最小生成樹, W(T)=W(T), T與T的公共邊更多, 矛盾! eeTT7-7 樹與生成樹（續(xù)）125求最小生成樹的算法逐步短接法(Boruvka)避圈法(Kruskal,1956) 破圈法(Rosenstiehl,1967 / 管梅谷,1975)貪心(Greedy)策略: W(e1)W(e2)W(e2)斷集法(Prim,1957, m+nlnn)7-7 樹與生成樹（續(xù)）1261553652546逐步短接法7-7 樹與生成樹（續(xù)）127155365254615536525467-7 樹與生成樹（續(xù)）128155365254615536525465536525467-7 樹與生成樹（

44、續(xù)）129155365254615536525465536554655365254615536525461553652546553655465536525467-7 樹與生成樹（續(xù)）130155365254615536525465536554655365254615536525461553652546553655465536525467-7 樹與生成樹（續(xù)）1311553652546155365254655365546553652546155365254615536525465536554655365254655655467-7 樹與生成樹（續(xù)）132155365254615536525465

45、5365546553652546155365254615536525465536554655365254655655465565567-7 樹與生成樹（續(xù)）1335565561553652546155365254655365546553652546155365254615536525465536554655365254655655465565567-7 樹與生成樹（續(xù)）13455655615536525461553652546553655465536525461553652546155365254655365546553652546556554655655656567-7 樹與生成樹（續(xù)）135155365254613524逐步短接法7-7 樹與生成樹（續(xù)）1361321.55623561321.5231321.55623561321.523561321.5231321.556231321.55623避圈法(舉例)7-7 樹與生成樹（續(xù)）1371321.55623121.55623121.5562121.552破圈法(舉例)7-7 樹與生成樹（續(xù)）138定理：