第7章 特殊圖-《離散數(shù)學(xué)（微課版）》教學(xué)課件

《離散數(shù)學(xué)》第7章特殊圖內(nèi)容導(dǎo)航CONTENTS歷史人物本章導(dǎo)讀及學(xué)習(xí)要求樹根樹歐拉圖偶圖

7.1

7.2

7.3

7.4作業(yè)

7.5平面圖特殊圖的應(yīng)用哈密頓圖

7.7

7.6

7.8本章導(dǎo)讀本章介紹幾種特殊的圖：樹歐拉圖哈密頓圖偶圖平面圖重點1無向樹的基本概念2無向樹的性質(zhì)，特別是m＝n－1和至少2個葉結(jié)點3生成樹與最小生成樹及其求解算法4

根樹的概念與分類5歐拉圖及其判定，F(xiàn)leury算法6

哈密頓圖及其判定7

偶圖及其判定，匹配8平面圖及其判定，歐拉公式，庫拉托夫斯基定理難點1

哈密頓圖的判定2

平面圖的判定3

庫拉托夫斯基定理學(xué)習(xí)要求內(nèi)容導(dǎo)航CONTENTS歷史人物本章導(dǎo)讀及學(xué)習(xí)要求樹根樹歐拉圖偶圖

7.1

7.2

7.3

7.4作業(yè)

7.5平面圖特殊圖的應(yīng)用哈密頓圖

7.7

7.6

7.8哈密頓自幼聰明，被稱為神童。3歲能讀英語，會算術(shù)；5歲能譯拉丁語、希臘語和希伯來語，并能背誦荷馬史詩；9歲便熟悉了波斯語、阿拉伯語和印地語。他自幼喜歡算術(shù)，計算很快。1818年遇到美國“計算神童”Z．科耳本（Colburn）后對數(shù)學(xué)產(chǎn)生了更深厚的興趣。到1820年已閱讀了牛頓的《自然哲學(xué)的數(shù)學(xué)原理》，并對天文學(xué)有強烈愛好，常用自己的望遠鏡觀測天體。威廉·哈密頓愛爾蘭數(shù)學(xué)家、物理學(xué)家、力學(xué)家哈密頓1820年開始讀P．S．拉普拉斯（Laplace）的著作《天體力學(xué)》，1822年指出了此書中的一個錯誤；同年他開始進行科學(xué)研究工作，對曲線和曲面的性質(zhì)進行了系列研究，并用于幾何光學(xué)。愛爾蘭科學(xué)院院士R．J．布林克萊（Brinkley）稱他是“這個年齡（17歲）的第一數(shù)學(xué)家”。首先建立了光學(xué)的數(shù)學(xué)理論，并把這種理論移植到動力學(xué)中去，提出了著名的“哈密頓最小作用原理”，即用一個變分式推出各種動力學(xué)定律。還把廣義坐標和廣義動量作為典型變量來建立動力學(xué)方程──哈密頓典型方程。威廉·哈密頓愛爾蘭數(shù)學(xué)家、物理學(xué)家、力學(xué)家哈密頓還建立了與系統(tǒng)的總能量有關(guān)的哈密頓函數(shù)，這些工作推動了變分法和微分方程理論的進一步研究。哈密頓方程是一個經(jīng)典力學(xué)方程。哈密頓函數(shù)既是經(jīng)典物理學(xué)中的一個函數(shù)，也是量子物理學(xué)中的一個算子。哈密頓圖是圖論中的一個術(shù)語。他也喜歡文學(xué)，成為數(shù)學(xué)大師后，仍不斷賦詩填詞，一直認為文學(xué)與數(shù)學(xué)是近似的學(xué)科——都是抽象思維的文字與符號。他曾寫道：“詩與數(shù)學(xué)是近親。”威廉·哈密頓愛爾蘭數(shù)學(xué)家、物理學(xué)家、力學(xué)家哈夫曼他從小聰慧好學(xué)，在俄亥俄州立大學(xué)畢業(yè)時只有17歲。然后他進入麻省理工學(xué)院（MIT）一邊工作，一邊深造，哈夫曼編碼就是他在1952年做博士論文時發(fā)明的。這是一種根據(jù)字母的使用頻率而設(shè)計的變長碼，能大大提高信息的傳輸效率，至今仍有廣泛的應(yīng)用。在MIT一直工作到1967年。之后轉(zhuǎn)入加州大學(xué)的圣克魯茲分校，成為該校計算機科學(xué)系的創(chuàng)始人，并于1970年至1973年任系主任，為此系的學(xué)術(shù)研究做出了許多杰出貢獻。1994年哈夫曼退休。戴維·哈夫曼美國計算機科學(xué)家哈夫曼除了哈夫曼編碼外，哈夫曼在其他方面也有不少創(chuàng)造，他設(shè)計的二叉最優(yōu)搜索樹算法就被認為是同類算法中效率最高的，因而被命名為哈夫曼算法，是動態(tài)規(guī)劃（DynamicProgramming）的一個范例。哈夫曼算法也廣泛應(yīng)用于傳真機、圖像壓縮和計算機安全領(lǐng)域。但他卻從未為此算法申請過專利或其他能夠為他帶來經(jīng)濟利益的東西，而是將全部的精力放在教學(xué)上，用他自己的話來說，“我所要給世界帶來的就是我的學(xué)生。”戴維·哈夫曼美國計算機科學(xué)家哈夫曼1982年獲得美國電氣與電子工程師學(xué)會（IEEE）計算機先驅(qū)獎。1973年獲得IEEE的麥克道爾（McDowell）獎。1998年IEEE下屬的信息論分會為紀念信息論創(chuàng)立50周年，授予他金禧（GoldenJubilee）獎。1999年6月，榮獲了以哈明碼發(fā)明人命名的哈明獎?wù)拢℉ammingMedal）。戴維·哈夫曼美國計算機科學(xué)家管梅谷1957年畢業(yè)于華東師范大學(xué)數(shù)學(xué)系1957年至1990年在山東師范大學(xué)工作1984年至1990年擔任山東師范大學(xué)校長1990年至1995年任復(fù)旦大學(xué)運籌學(xué)系主任一直從事運籌學(xué)、組合優(yōu)化與圖論方面的研究工作，是國內(nèi)外知名度很高的學(xué)者。代表性論著有《線性規(guī)劃》《圖論中的幾個極值問題》《奇偶點圖上作業(yè)法》等。1960年在國際上最先提出的郵遞員問題被國際圖論界命名為“中國郵路問題”，載入經(jīng)典著作。2016年，被中國運籌學(xué)會授予科學(xué)技術(shù)獎——終身成就獎。管梅谷上海市人數(shù)學(xué)家內(nèi)容導(dǎo)航CONTENTS歷史人物本章導(dǎo)讀及學(xué)習(xí)要求樹根樹歐拉圖偶圖

7.1

7.2

7.3

7.4作業(yè)

7.5平面圖特殊圖的應(yīng)用哈密頓圖

7.7

7.6

7.8引言樹是圖論中的一個非常重要的概念，而在計算機科學(xué)中有著非常廣泛的應(yīng)用，例如現(xiàn)代計算機操作系統(tǒng)均采用樹形結(jié)構(gòu)來組織文件和文件夾，本章介紹樹的基本知識和應(yīng)用。在本章中，所談到的圖都假定是簡單圖；所談到的回路均指簡單回路或基本回路。并且同一個圖形表示的回路(簡單的或基本的)，可能有不同的交替序列表示方法，但我們規(guī)定它們表示的是同一條回路。7.1.1樹的基本概念及性質(zhì)例7.12018年俄羅斯世界杯8強的比賽結(jié)果圖，最后勝利的隊捧得大力神杯。英格蘭瑞典俄羅斯克羅地亞巴西比利時烏拉圭法國英格蘭克羅地亞比利時法國克羅地亞法國法國定義7.1連通而不含回路的無向圖稱為無向樹(UndirectedTree)，簡稱樹(Tree)，常用T表示樹。樹中度數(shù)為1的結(jié)點稱為葉(Leaf)；度數(shù)大于1的結(jié)點稱為分支點(BranchPoint)或內(nèi)部結(jié)點(InteriorPoint)。每個連通分支都是樹的無向圖稱為森林(Forest)。平凡圖稱為平凡樹(TrivialTree)。不含回路的無向圖稱為森林樹中沒有環(huán)和平行邊，因此一定是簡單圖在任何非平凡樹中，都無度數(shù)為0的結(jié)點解題小貼士——無向圖G是樹的判斷（1）圖G是連通的。（2）圖G中不存在回路。例10.2.2判斷下圖中的圖哪些是樹？為什么？(a)(b)(c)(d)樹樹不是樹森林不是樹連通，無回路連通，無回路不連通有回路，無回路不是森林樹的性質(zhì)定理10.2.1設(shè)無向圖G=<V,E>，|V|=n，|E|=m，下列各命題是等價的：G連通而不含回路(即G是樹)G中無回路，且m=n-1G是連通的，且m=n-1G中無回路，但在G中任二結(jié)點之間增加一條新邊，就得到惟一的一條基本回路G是連通的，但刪除G中任一條邊后，便不連通(n≥2)G中每一對結(jié)點之間有惟一一條基本通路(n≥2)證明①②：對n作歸納。n=1時，m=0，顯然有m=n-1。假設(shè)n=k時命題成立，現(xiàn)證n=k+1時也成立。由于G連通而無回路，所以G中至少有一個度數(shù)為1的結(jié)點v0，在G中刪去v0及其關(guān)聯(lián)的邊，便得到k個結(jié)點的連通而無回路的圖，由歸納假設(shè)知它有k-1條邊。再將結(jié)點v0及其關(guān)聯(lián)的邊加回得到原圖G，所以G中含有k+1個結(jié)點和k條邊，符合公式m=n-1。所以，G中無回路，且m=n-1。G連通而不含回路(即G是樹)G中無回路，且m=n-1；②③：設(shè)G有k個連通分支G1，G2，…，Gk，其結(jié)點數(shù)分別為n1，n2，…，nk，邊數(shù)分別為m1，m2，…，mk，且，由于G中無回路，所以每個Gi(i=1,2,…,k)均為樹，因此mi=ni–1（i=1,2,…,k），于是故k=1，所以G是連通的，且m=n-1。G中無回路，且m=n-1；G是連通的，且m=n-1；③④：首先證明G中無回路。對n作歸納。n=1時，m=n-1=0，顯然無回路。假設(shè)結(jié)點數(shù)n=k-1時無回路，下面考慮結(jié)點數(shù)n=k的情況。因G連通，故G中每一個結(jié)點的度數(shù)均大于等于1。可以證明至少有一個結(jié)點v0，使得deg(v0)=1，因若k個結(jié)點的度數(shù)都大于等于2，則從而m≥k，即至少有k條邊，但這與m=n-1矛盾。G是連通的，且m=n-1；G中無回路，但在G中任二結(jié)點之間增加一條新邊，就得到惟一的一條基本回路；③④：在G中刪去v0及其關(guān)聯(lián)的邊，得到新圖G’，根據(jù)歸納假設(shè)知G’無回路，所以再將結(jié)點v0及其關(guān)聯(lián)的邊加回得到原圖G，則G也無回路。其次證明在G中任二結(jié)點vi，vj之間增加一條邊(vi,vj)，得到一條且僅一條基本回路。由于G是連通的，從vi到vj有一條通路L，再在L中增加一條邊(vi,vj)，就構(gòu)成一條回路。若此回路不是惟一和基本的，則刪去此新邊，G中必有回路，得出矛盾。由于deg(v0)=1，④⑤：若G不連通，則存在兩結(jié)點vi和vj，在vi和vj之間無通路，此時增加邊(vi,vj)，不會產(chǎn)生回路，但這與題設(shè)矛盾。由于G無回路，所以刪去任一邊，圖便不連通。G中無回路，但在G中任二結(jié)點之間增加一條新邊，就得到惟一的一條基本回路；G是連通的，但刪除G中任一條邊后，便不連通；(n≥2)G是連通的，但刪除G中任一條邊后，便不連通；(n≥2)G中每一對結(jié)點之間有惟一一條基本通路。(n≥2)⑤⑥：由于G是連通的，因此G中任二結(jié)點之間都有通路，于是有一條基本通路。若此基本通路不惟一，則G中含有回路，刪去回路上的一條邊，G仍連通，這與題設(shè)不符。所以此基本通路是惟一的。⑥①：顯然G是連通的。若G中含回路，則回路上任二結(jié)點之間有兩條基本通路，這與題設(shè)矛盾。因此，G連通且不含回路。G中每一對結(jié)點之間有惟一一條基本通路

(n≥2)G連通而不含回路(即G是樹)樹的特點在結(jié)點給定的無向圖中，樹是邊數(shù)最多的無回路圖樹是邊數(shù)最少的連通圖由此可知，在無向圖G=(n,m)中，若m＜n-1，則G是不連通的若m＞n-1，則G必含回路由定理7.1(4)：G中無回路，但在G中任二結(jié)點之間增加一條新邊，就得到惟一的一條基本回路。由定理7.1(5)：G是連通的，但刪除G中任一條邊后，便不連通。定理7.2任意非平凡樹T=(n,m)都至少有兩片葉。證明因非平凡樹T是連通的，從而T中各結(jié)點的度數(shù)均大于等于1。設(shè)T中有k個度數(shù)為1的結(jié)點(即k片葉)，其余的結(jié)點度數(shù)均大于等于2。由握手定理得由于樹中有m=n-1，因此可得k≥2，

于是2(n-1)≥2n-k，這說明T中至少有兩片葉。平凡樹有多少片葉07..2生成樹及算法定義7.2給定圖G=<V,E>，若G的某個生成子圖是樹，則稱之為G的生成樹(SpanningTree)，記為TG。生成樹TG中的邊稱為樹枝(Branch)G中不在TG中的邊稱為弦(Chord)TG的所有弦的集合稱為生成樹的補(Complement)

解題小貼士——圖G'是圖G的生成樹的判斷（1）圖G'是圖G的生成子圖。（2）圖G'是樹。例7.3判斷下圖中的圖(b)、(c)、(d)、(e)是否是圖(a)的生成樹。abcdef(a)abcdef(b)abcdef(c)abcdef(d)bcdef(e)不是是不是不是樹枝：(a,c)、(a,d)、(b,f)、(c,f)、(c,e)弦：(a,b)、(b,c)、(c,d)、(d,e)、(e,f)定理7.3一個圖G=<V,E>存在生成樹TG=<V,ET>的充分必要條件是G是連通的。證明

必要性：假設(shè)TG=<V,ET>是G=<V,E>的生成樹，由定義10.2.1，TG是連通的，于是G也是連通的。充分性：假設(shè)G=<V,E>是連通的。如果G中存在回路C1，可刪除C1中一條邊得到圖G1，它仍連通且與G有相同的結(jié)點集。如果G1中無回路，G1就是生成樹。如果G1仍存在回路C2，可刪除C2中一條邊，如此繼續(xù)，直到得到一個無回路的連通圖H為止。因此，H是G的生成樹。如果G中無回路，G本身就是生成樹。

說明一個無向連通圖G，如果G是樹，則它的生成樹是唯一的，就是G本身。如果G不是樹，那么它的生成樹就不唯一了。定理7.3的證明過程就給出了求連通圖G＝(n,m)的生成樹的一種算法，稱為“破圈法”，算法的關(guān)鍵是判斷G中是否有回路。若有回路，則刪除回路中的一條邊，直到剩下的圖中無回路為止，由定理7.1知，共刪除m-n+1條邊。由定理7.3和定理7.1，連通圖G＝(n,m)一定存在生成樹，且其有n個結(jié)點，n-1條樹枝，m-n+1條弦，因此選擇G中不構(gòu)成任何回路的n-1條邊，就得到G的生成樹，這種方法稱為“避圈法”。

破圈法與避圈法算法7.1

求連通圖G=<V,E>的生成樹的破圈法：每次刪除回路中的一條邊，其刪除的邊的總數(shù)為m-n+1。算法7.2

求連通圖G=<V,E>的生成樹的避圈法：每次選取G中一條與已選取的邊不構(gòu)成回路的邊，選取的邊的總數(shù)為n-1。由于刪除回路上的邊和選擇不構(gòu)成任何回路的邊有多種選法，所以產(chǎn)生的生成樹不是惟一的。解題小貼士——求連通圖G＝(n,m)的生成樹使用破圈法：找出一條回路，并刪除該回路中的一條邊，直到圖中沒有回路為止，刪除的邊的總數(shù)為m-n+1。使用避圈法：選取一條邊，驗證該邊與已選取的邊不構(gòu)成回路，選取的邊的總數(shù)為n-1。例7.4用破圈法生成樹由于n=6，m=9，所以m-n+1=4，故要刪除的邊數(shù)為4，因此只需4步即可。123456用避圈法求生成樹由于n=6，所以n-1=5，故要選取5條邊，因此需5步即可。123456123456說明由于生成樹的形式不惟一，故上述兩棵生成樹都是所求的。破圈法和避圈法的計算量較大，主要是需要找出回路或驗證不存在回路。算法7.3求連通圖G=<V,E>的生成樹的廣度優(yōu)先搜索算法：任選s∈V，將s標記為0，令L={s}，V=V-{s}，k=0；如果V=Φ，則轉(zhuǎn)④，否則令k=k+1；依次對L中所有標記為k-1的結(jié)點v，如果它與V中的結(jié)點w相鄰接，則將w標記為k，指定v為w的前驅(qū)，令L=L∪{w}，V=V-{w}，轉(zhuǎn)②；EG={(v,w)|w∈L-{s}，v為w的前驅(qū)}，結(jié)束。解題小貼士——使用廣度優(yōu)先搜索算法求生成樹使用算法7.3，從任意結(jié)點開始，逐步搜索，完成對所有節(jié)點的標記，所有結(jié)點與其前驅(qū)連接的邊即為該生成樹的弦。if例7.50(-)1(a)1(a)2(c)2(b)3(e)3(e)3(e)4(d)4(h)bacdgjifeh0(-)1(a)1(a)2(c)2(b)3(e)3(f)3(e)4(h)4(h)bacdgjeh用廣度優(yōu)先搜索算法求生成樹最小生成樹定義10.2.3設(shè)G=<V,E>是連通的賦權(quán)圖，T是G的一棵生成樹，T的每個樹枝所賦權(quán)值之和稱為T的權(quán)(Weight)，記為w(T)。G中具有最小權(quán)的生成樹稱為G的最小生成樹(MinimalSpanningTree)。

一個無向圖的生成樹不是惟一的，同樣地，一個賦權(quán)圖的最小生成樹也不一定是惟一的。算法7.4Kruskal算法在G中選取最小權(quán)邊e1，置i=1。當i=n-1時，結(jié)束，否則轉(zhuǎn)③。設(shè)已選取的邊為e1,e2,…,ei，在G中選取不同于e1,e2,…,ei的邊ei+1，使{e1,e2,…,ei,ei+1}中無回路且ei+1是滿足此條件的最小權(quán)邊。置i=i+1，轉(zhuǎn)②。要點：在與已選取的邊不構(gòu)成回路的邊中選取最小者。

解題小貼士——使用Kruskal算法求最小生成樹按照邊的權(quán)值從小到大逐步搜索，選取那些與已選取邊不構(gòu)成回路的邊加入即可，共放入n-1條邊。注：在算法的步驟①和③中，若滿足條件的最小權(quán)邊不止一條，則可從中任選一條，這樣就會產(chǎn)生不同的最小生成樹。例7.6用Kruskal算法求圖中賦權(quán)圖的最小生成樹。解n=12，按算法要執(zhí)行n-1=11次，w(T)=36。4655761f923adbcimjkehg343446587582451f23adbcimjkehg343452算法7.5Prim算法（1）在G中任意選取一個結(jié)點v1，置VT={v1},ET=Φ，k=1；（2）在V-VT中選取與某個vi∈VT鄰接的結(jié)點vj，使得邊(vi,vj)的權(quán)最小，置VT=VT∪{vj},ET=ET∪{(vi,vj)}，k=k+1；（3）重復(fù)步驟(2)，直到k=|V|。要點：從任意結(jié)點開始，每次增加一條最小權(quán)邊構(gòu)成一棵新樹。解題小貼士——使用Prim算法求最小生成樹從平凡樹開始逐步搜索，每次選取與該樹的結(jié)點關(guān)聯(lián)的樹外的最小權(quán)邊構(gòu)成一棵新樹，共執(zhí)行n-1次。注：在算法的步驟(2)中，若滿足條件的最小權(quán)邊不止一條，則可從中任選一條，這樣就會產(chǎn)生不同的最小生成樹。例7.7用Prim算法求圖中賦權(quán)圖的最小生成樹。解n=7，按算法要執(zhí)行n-1=6次，w(T)=25。5f102dbce7g64582a5f2dbce7g452a由Prim算法可以看出，每一步得到的圖一定是樹，故不需要驗證是否有回路，因此它的計算工作量較Kruskal算法要小。

內(nèi)容導(dǎo)航CONTENTS歷史人物本章導(dǎo)讀及學(xué)習(xí)要求樹根樹歐拉圖偶圖

7.1

7.2

7.3

7.4作業(yè)

7.5平面圖特殊圖的應(yīng)用哈密頓圖

7.7

7.6

7.87.2.1根樹的定義與分類定義10.3.1一個有向圖，若略去所有有向邊的方向所得到的無向圖是一棵樹，則這個有向圖稱為有向樹(DirectedTree)。解題小貼士——有向樹的判斷（1）將所有有向邊都略去方向變?yōu)闊o向邊，得到一個無向圖。（2）判斷該無向圖是否是樹。例7.8判斷下圖中的圖哪些是有向樹？為什么？(a)(c)(e)(d)(b)不是有向樹不是有向樹有向樹有向樹有向樹一棵非平凡的有向樹，如果恰有一個結(jié)點的入度為0，其余所有結(jié)點的入度均為1，則稱之為根樹(RootTree)或外向樹(OutwardTree)。

入度為0的結(jié)點稱為根(Root)；出度為0的結(jié)點稱為葉(Leaf)；入度為1，出度大于0的結(jié)點稱為內(nèi)點(InteriorPoint)；又將內(nèi)點和根統(tǒng)稱為分支點(BranchPoint)。在根樹中，從根到任一結(jié)點v的通路長度，稱為該結(jié)點的層數(shù)(LayerNumber)；稱層數(shù)相同的結(jié)點在同一層上；所有結(jié)點的層數(shù)中最大的稱為根樹的高(Height)。定義7.5解題小貼士——根樹的判斷（1）判斷是否為有向樹。（2）計算所有結(jié)點的度數(shù)，看是否恰有一個結(jié)點的入度為0，其余所有結(jié)點的入度均為1。例7.9判斷下圖所示的圖是否是根樹？若是根樹，給出其根、葉和內(nèi)點，計算所有結(jié)點所在的層數(shù)和高。是根樹根：v1葉：v5,v6,v8,v9,v10,v12,v13內(nèi)點：v2,v3,v4,v7,v11倒置法

v1v2v3v4v5v6v7v8v9v10v11v12v13v1處在第零層，層數(shù)為0v2,v3,v4同處在第一層，層數(shù)為1v5,v6,v7,v8,v9同處在第二層，層數(shù)為2v10,v11,v12同處在第三層，層數(shù)為3v13處在第四層，層數(shù)為4這棵樹的高為4v1v2v3v4v5v6v7v8v9v10v11v12v13家族關(guān)系——根樹定義7.6在根樹中，若從結(jié)點vi到vj可達，則稱vi是vj的祖先(Ancestor)，vj是vi的后代(Descendant)；若<vi,vj>是根樹中的有向邊，則稱vi是vj的父親(Father)，vj是vi的兒子(Son)；如果兩個結(jié)點是同一個結(jié)點的兒子，則稱這兩個結(jié)點是兄弟(Brother)。定義7.7如果在根樹中規(guī)定了每一層上結(jié)點的次序，這樣的根樹稱為有序樹(OrderedTree)。一般地，在有序樹中同一層中結(jié)點的次序為從左至右。有時也可以用邊的次序來代替結(jié)點的次序。k元樹定義7.8設(shè)T為根樹。（1）若T的每個分支點至多有k個兒子，則稱T為k元樹（或k叉樹）（k-aryTree）；（2）若T的每個分支點都恰有k個兒子，則稱T為完全k元樹（Completek-aryTree）；（3）若T是k元完全樹且每個葉結(jié)點的層數(shù)均為樹高，則稱T為滿k元樹（Fullk-aryTree）；（4）若k元樹T是有序的，則稱T為有序k元樹（Orderedk-aryTree）；（5）若k元完全樹T是有序的，則稱T為有序完全k元樹（OrderedCompletek-aryTree）；（6）若T是滿k元樹且是有序的，則稱T為有序滿k元樹（FullOrderedk-aryCompleteTree）。通常，k元樹至少要有一個分支點有k個兒子。注：有些書中k叉樹專指k元有序樹完全k元樹又稱為k元完全樹，k叉正則樹滿k元樹又稱為k叉完全正則樹子樹在根樹T中，任一結(jié)點v及其所有后代導(dǎo)出的子圖T’稱為T的以v為根的子樹(Subtree)。當然，T’也可以有自己的子樹。有序2元樹的每個結(jié)點v至多有兩個兒子，分別稱為v的左兒子(LeftSon)和右兒子(RightSon)。有序2元樹的每個結(jié)點v至多有兩棵子樹，分別稱為v的左子樹(LeftSubtree)和右子樹(RightSubtree)。注意區(qū)分以v為根的子樹和v的左(右)子樹，v為根的子樹包含v，而v的左(右)子樹不包含v。解題小貼士——k元樹的判斷必須是根樹計算所有分支點的兒子數(shù)每個分支點至多有k（包含k）個兒子即為k元樹每個分支點都恰有k個兒子即為完全k元樹每個分支點都恰有k個兒子且每個葉結(jié)點的層數(shù)均相同即為滿k元樹例7.10判斷下圖所示的幾棵根樹是什么樹？2元完全樹

3元樹

3元完全樹

3元有序完全樹(b)(c)(a)122(d)133213k元完全樹中分支點與葉結(jié)點數(shù)目之間的關(guān)系定理7.4在k元完全樹中，若葉數(shù)為t，分支點數(shù)為i，則有：(k-1)×i=t-1證明由假設(shè)知，該樹有i+t個結(jié)點。由定理7.1知，該樹的邊數(shù)為i+t-1。由握手定理知，所有結(jié)點的出度之和等于邊數(shù)。而根據(jù)k元完全樹的定義知，所有分支點的出度為k×i。因此有k×i=i+t-1即 (k-1)×i=t-1例7.11假設(shè)有一臺計算機，它有一條加法指令，可計算4個數(shù)的和。如果要求16個數(shù)x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16之和，問至少要執(zhí)行幾次加法指令？解用4個結(jié)點表示4個數(shù)，將表示4個數(shù)之和的結(jié)點作為它們的父結(jié)點。這樣本問題可理解為求一個完全4元樹的分支點問題。把16個數(shù)看成葉。由定理7.4知，有(4-1)i=16-1，得i=5。所以至少要執(zhí)行5次加法指令。例7.11兩種可能的順序：（a）x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16（b）x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16例7.12——一題多解設(shè)T為任意一棵完全2元樹，m為邊數(shù)，t為葉數(shù)（t≥2），試證明：m＝2t－2證明方法一：設(shè)T中的結(jié)點數(shù)為n，分支點數(shù)為i。根據(jù)完全2元樹的定義，容易知道下面等式均成立：n＝i＋t，m＝2i，m＝n－1解關(guān)于m、n、i的三元一次方程組得m＝2t－2。方法二：在完全2元樹中，除葉外，每個結(jié)點的出度均為2；除根結(jié)點外，每個結(jié)點的入度均為1。設(shè)T中的結(jié)點數(shù)為n，由握手定理可知2m＝＝2(n－t)＋n－1＝3n－2t－1＝3(m＋1)－2t－1故

m＝2t－2

＝

＋方法三：對樹葉數(shù)t作歸納法。當t=2時，結(jié)點數(shù)為3，邊數(shù)m=2，故m=2t-2成立。假設(shè)t=k（k≥2）時，結(jié)論成立，下面證明t=k+1時結(jié)論也成立。由于T是完全2元樹，因此T中一定存在都是樹葉的兩個兄弟結(jié)點v1,v2，設(shè)v是v1,v2的父親。在T中刪除v1,v2，得樹T’，T’仍為完全2元樹，這時結(jié)點v成為樹葉，樹葉數(shù)t’=t-2+1=k+1-1=k，邊數(shù)m’=m-2，由歸納假設(shè)知，m’=2t’-2。所以m-2=2(t-2+1)-2，故m=2t-2。方法四：對分支點數(shù)i作歸納法。當i=1時，邊數(shù)m=2，樹葉數(shù)t=2，故m=2t-2成立。假設(shè)i=k(k≥1)時，結(jié)論成立，下面證明i=k+1時結(jié)論也成立。由于T是完全2元樹，因此T中一定存在兩個兒子都是樹葉的分支點，設(shè)v就是這樣一個分支點，設(shè)它的兩個兒子為v1,v2

。在T中刪除v1,v2，得樹T’，T’仍為完全2元樹，這時結(jié)點v成為樹葉，分支點數(shù)i’=i-1=k+1-1=k，樹葉數(shù)t’=t-2+1，邊數(shù)m’=m-2，由歸納假設(shè)知，m’=2t’-2。所以m-2=2(t-2+1)-2，故m=2t-2。7.2.2根樹的遍歷對于根樹，一個十分重要的問題是要找到一些方法，能系統(tǒng)地訪問樹的結(jié)點，使得每個結(jié)點恰好訪問一次，這就是根樹的遍歷(Ergode)問題。k元樹中，應(yīng)用最廣泛的是2元樹。由于2元樹在計算機中最易處理，下面先介紹二元樹的3種常用的遍歷方法，然后再介紹將任意根樹轉(zhuǎn)化為二元樹。2元樹的3種常用遍歷方法算法7.62元樹的先根次序遍歷算法：訪問根按先根次序遍歷根的左子樹按先根次序遍歷根的右子樹算法7.82元樹的后根次序遍歷算法按后根次序遍歷根的左子樹按后根次序遍歷根的右子樹訪問根算法7.72元樹的中根次序遍歷算法：按中根次序遍歷根的左子樹訪問根按中根次序遍歷根的右子樹解題小貼士——2元樹的遍歷按照根、左子樹、右子樹的不同次序，有3種不同的遍歷方法，注意對左子樹、右子樹的遍歷順序都是一致的。例7.13寫出對圖中2元樹的3種遍歷方法得到的結(jié)果。abedghklmicjf解先根遍歷次序為abdghceijklmf中根遍歷次序為gdhbaielkmjcf后根遍歷次序為ghdbilmkjefca按遍歷方法容易寫出，只要先將該樹分解為根、左子樹、右子樹三部分，然后再對子樹作分解，直到葉為止。算法7.9根樹轉(zhuǎn)化為二元樹算法：從根開始，保留每個父親同其最左邊兒子的連線，撤銷與別的兒子的連線。兄弟間用從左向右的有向邊連接。按如下方法確定2元樹中結(jié)點的左兒子和右兒子：直接位于給定結(jié)點下面的結(jié)點，作為左兒子，對于同一水平線上與給定結(jié)點右鄰的結(jié)點，作為右兒子，依此類推。解題小貼士——根樹轉(zhuǎn)化為2元樹從根開始，只保留最左邊兒子，相鄰的弟弟變?yōu)橛覂鹤?。?.14將下圖轉(zhuǎn)化為一棵二元樹。v1v2v3v4v5v6v7v10v11v9v1v2v3v4v5v6v7v8v10v11v9v1v2v3v4v5v6v7v8v10v11v9反過來，也可以還原。要點：右兒子變弟弟算法7.10有序森林轉(zhuǎn)化為二元樹算法：先把森林中的每一棵樹都表示成2元樹；除第一棵2元樹外，依次將剩下的每棵2元樹作為左邊2元樹的根的右子樹，直到所有的二元樹都連成一棵二元樹為止。解題小貼士——森林轉(zhuǎn)化為2元樹先把森林中的每一棵樹都表示成2元樹，然后從右往左，依次將每棵2元樹變?yōu)樽筮?元樹根的右子樹。例7.15將圖所示的森林轉(zhuǎn)化成一棵二元樹。v1v2v3v4v5v6v7v12v9v10v8v11v13v14v1v2v3v4v5v6v7v12v9v10v8v11v13v14將二元樹轉(zhuǎn)化為森林，要點是“先將根的右子樹變?yōu)樾露獦?，再將這些二元樹還原為根樹”。

7.2.3最優(yōu)樹與哈夫曼算法在計算機及通訊事業(yè)中，常用二進制編碼來表示符號，稱之為碼字(codeword)。例如，可用00、01、10、11分別表示字母A、B、C、D。如果字母A、B、C、D出現(xiàn)的頻率是一樣的，傳輸100個字母用200個二進制位。但實際上字母出現(xiàn)的頻率很不一樣，如A出現(xiàn)的頻率為50％，B出現(xiàn)的頻率為25％，C出現(xiàn)的頻率為20％，D出現(xiàn)的頻率為5％。能否用不等長的二進制序列表示字母A、B、C、D，使傳輸?shù)男畔⒌亩M制位盡可能少呢？事實上，可用000表示字母D，用001表示字母C，01表示B，1表示A。這樣表示，傳輸100個字母所用的二進制位為3×5+3×20+2×25+1×50=175。這種表示比用等長的二進制序列表示法好，節(jié)省了二進制位。但當我們用1表示A，用00表示B，用001表示C，用000表示D時，如果接收到的信息為001000，則無法辨別它是CD還是BAD。因而，不能用這種二進制序列表示A、B、C、D，要尋找另外的表示法。定義7.9設(shè)a1a2…an-1an為長度為n的符號串，稱其子串a(chǎn)1，a1a2，…,a1a2…an-1分別為a1a2…an-1an的長度為1、2、…、n-1的前綴（Prefix）。設(shè)A={b1,b2,…,bm}是一個符號串集合，若對任意bi,bj∈A，bi≠bj，bi不是bj的前綴，bj也不是bi的前綴，則稱A為前綴碼（PrefixedCode）。若符號串bi（i=1,2…,m）中，只出現(xiàn)0和1兩個符號，則稱A為二元前綴碼（BinaryPrefixedCode）。{1,01,001,000}是前綴碼{1,11,001,0011}不是前綴碼

用2元樹產(chǎn)生二元前綴碼給定一棵二元樹T，假設(shè)它有t片樹葉。設(shè)v是T任意一個分支點，則v至少有一個兒子至多有兩個兒子。若v有兩個兒子，則在由v引出的兩條邊上，左邊的標上0，右邊的標上1；若v只有一個兒子，在v引出的邊上可標0也可標1。設(shè)vi為T的任意一片樹葉，從樹根到vi的通路上各邊的標號組成的符號串放在vi處，t片樹葉處的t個符號串組成的集合為一個二元前綴碼。vi中的符號串的前綴均在vi所在的通路上，因而所得集合為二元(0和1組成)前綴碼。若T存在帶一個兒子的分支點，則由T產(chǎn)生的前綴碼不唯一，但T若為完全2元樹，則T產(chǎn)生的前綴碼就是唯一的了。例圖中所示的2元樹產(chǎn)生的前綴碼為：{1，00，010，011}。因此用1表示A，用00表示B，用010表示C，用011表示即可滿足要求。010011100010011當知道了傳輸?shù)姆柍霈F(xiàn)的頻率時，如何選擇前綴碼，使傳輸?shù)亩M制位盡可能地少呢？先產(chǎn)生最優(yōu)二元樹T，然后用T產(chǎn)生二元前綴碼。最優(yōu)樹定義7.10設(shè)有一棵二元樹，若對其所有的t片葉賦以權(quán)值w1、w2、…、wt，則稱之為賦權(quán)二元樹(PowerBinaryTree)；若權(quán)為wi的葉的層數(shù)為L(wi)，則稱為該賦權(quán)二元樹的權(quán)；而在所有賦權(quán)w1、w2、…、wt的二元樹中，W(T)最小的二元樹稱為最優(yōu)樹(OptimalTree)。1952年哈夫曼(Huffman)給出了求最優(yōu)樹的方法。該方法的關(guān)鍵是：從帶權(quán)為W1+W2、W3、…、Wt(這里假設(shè)W1≤W2≤…≤Wt)的最優(yōu)樹T’中得到帶權(quán)為W1、W2、…、Wt的最優(yōu)樹。算法7.11哈夫曼算法：初始：令S=｛W1,W2,…,Wt｝；從S中取出兩個最小的權(quán)Wi和Wj，畫結(jié)點vi，帶權(quán)Wi，畫結(jié)點vj，帶權(quán)Wj。畫vi和vj的父親v，連接vi和v，vj和v，令v帶權(quán)Wi+Wj；令S=(S-｛Wi,Wj｝)∪｛Wi+Wj｝；判斷S是否只含一個元素，若是，則停止，否則轉(zhuǎn)2。解題小貼士——使用哈夫曼算法求最優(yōu)樹每次先在權(quán)值序列中選兩個最小權(quán)的結(jié)點構(gòu)造它們的父親，父結(jié)點的權(quán)值為它兩個兒子的權(quán)值之和，然后在權(quán)值序列中添加父結(jié)點的權(quán)值，刪除這兩個兒子的權(quán)值。例7.16求帶權(quán)7、8、9、12、16的最優(yōu)樹。158916122131527例7.17用機器分辨一些幣值為1角、5角、1元的硬幣，假設(shè)各種硬幣出現(xiàn)的概率分別為0.1、0.4、0.5。問：如何設(shè)計一個分辨硬幣的算法，使所需的時間最少（假設(shè)每做一次判別所用的時間相同，以此為一個時間單位）？10.50.50.40.1(a)是否1元1元是5角1角(b)是否5角否是否所需時間：2×0.1+2×0.4+1×0.5=1.5(時間單位)。例7.18已知字母A、B、C、D、E、F出現(xiàn)的頻率如下：A——30％，B——25％，C——20％D——10％，E——10％，F(xiàn)——5％構(gòu)造一個表示A、B、C、D、E、F前綴碼，使得傳輸?shù)亩M制位最少。解（1）求帶權(quán)30,25,20,10,10,5

的最優(yōu)二元樹T。（2）在T上求一個前綴碼。0100110100000010101510102025301525455510010110001CFDBAE1051020253015254555100（3）傳輸100個這樣的字母所用的二進制位為：4×(5+10)+3×10+2×(20+25+30)=240（3）設(shè)樹葉vi帶權(quán)為w％×100=w，則vi處的符號串表示出現(xiàn)頻率為w％的字母。{01，10，11，001，0001，0000}為一前綴碼，其中 0000表示F， 0001表示E， 001表示D， 01表示C， 10表示B， 11表示A。傳輸100個這樣的字母所用的二進制位為：4×(5+10)+3×10+2×(20+25+30)=240。內(nèi)容導(dǎo)航CONTENTS歷史人物本章導(dǎo)讀及學(xué)習(xí)要求樹根樹歐拉圖偶圖

7.1

7.2

7.3

7.4作業(yè)

7.5平面圖特殊圖的應(yīng)用哈密頓圖

7.7

7.6

7.87.3.1歐拉圖的引入與定義哥尼斯堡（Konigsberg)七橋問題BCADb6b2b5b7b4b1b3ABCDb5b2b1b3b7b4b6歐拉圖定義11.2.1設(shè)G是無孤立結(jié)點的圖，若存在一條通路(回路)，經(jīng)過圖中每邊一次且僅一次，則稱此通路(回路)為該圖的一條歐拉通路(回路)(EulerianEntry/Circuit)。具有歐拉回路的圖稱為歐拉圖(EulerianGraph)。規(guī)定：平凡圖為歐拉圖。以上定義既適合無向圖，又適合有向圖。歐拉通路和歐拉回路的特征歐拉通路是經(jīng)過圖中所有邊的通路中長度最短的通路，即為通過圖中所有邊的簡單通路；歐拉回路是經(jīng)過圖中所有邊的回路中長度最短的回路，即為通過圖中所有邊的簡單回路。如果僅用邊來描述，歐拉通路和歐拉回路就是圖中所有邊的一種全排列。解題小貼士——歐拉圖的判斷1找到一條經(jīng)過圖中每邊一次且僅一次的通路（回路），則該圖存在歐拉通路（回路）。有歐拉回路的圖為歐拉圖。例7.19判斷下面的圖中，是否是歐拉圖？是否存在歐拉通路？歐拉圖

不是歐拉圖但存在歐拉通路

不存在歐拉通路

v3v1v2v4v3v1v2v4v3v1v2v4(c)(a)(b)例7.19判斷下面的圖中，是否是歐拉圖？是否存在歐拉通路？歐拉圖

不是歐拉圖但存在歐拉通路

不存在歐拉通路

v3v1v2v4v3v1v2v4v3v1v2v4(f)(d)(e)7.3.2歐拉圖的判定定理7.5無向圖G=<V,E>具有一條歐拉通路，當且僅當G是連通的，且僅有零個或兩個奇度數(shù)結(jié)點。證明若G為平凡圖，則定理顯然成立。故我們下面討論的均為非平凡圖。設(shè)G具有一條歐拉通路L=，由于G中無孤立結(jié)點，對歐拉通路L的任意非端點的結(jié)點，在L中每出現(xiàn)一次，都關(guān)聯(lián)兩條邊和，而當重復(fù)出現(xiàn)時，它又關(guān)聯(lián)另外的兩條邊，必要性：由于在通路L中邊不可能重復(fù)出現(xiàn)，因而每出現(xiàn)一次都將使獲得2度。若在L中重復(fù)出現(xiàn)p次，則deg()=2p。則L經(jīng)過G中的每條邊，因而L經(jīng)過G的所有結(jié)點，所以G是連通的。若端點≠，設(shè)、在通路中作為非端點分別出現(xiàn)p1和p2次，則deg()=2p1+1，deg()=2p2+1因而G有兩個度數(shù)為奇數(shù)的結(jié)點。若端點=，設(shè)在通路中作為非端點出現(xiàn)p3次，則deg()=1+2p3+1=2(p3+1)因而G無度數(shù)為奇數(shù)的結(jié)點。充分性：構(gòu)造性證明從兩個奇度數(shù)結(jié)點之一開始(若無奇度數(shù)結(jié)點，可從任一結(jié)點開始)構(gòu)造一條歐拉通路，以每條邊最多經(jīng)過一次的方式通過圖中的邊。對于度數(shù)為偶數(shù)的結(jié)點，通過一條邊進入這個結(jié)點，總可以通過一條未經(jīng)過的邊離開這個結(jié)點，因此，這樣的構(gòu)造過程一定以到達另一個奇度數(shù)結(jié)點而告終(若無奇度數(shù)結(jié)點，則以回到原出發(fā)點而告終)。如果圖中所有的邊已用這種方式經(jīng)過了，顯然這就是所求的歐拉通路。如果圖中不是所有的邊都經(jīng)過了，我們?nèi)サ粢呀?jīng)過的邊，得到一個由剩余的邊組成的子圖，這個子圖的所有結(jié)點的度數(shù)均為偶數(shù)。因為原來的圖是連通的，因此，這個子圖必與我們已經(jīng)過的通路在一個或多個結(jié)點相接。從這些結(jié)點中的一個開始，我們再通過邊構(gòu)造通路，因為結(jié)點的度數(shù)全是偶數(shù)，因此，這條通路一定最終回到起點。將這條回路加到已構(gòu)造好的通路中間組合成一條通路。如有必要，這一過程重復(fù)下去，直到得到一條通過圖中所有邊的通路，即歐拉通路。由定理7.5的證明知：

若連通的無向圖有兩個奇度數(shù)結(jié)點，則它們是G中每條歐拉通路的端點。結(jié)論推論7.1無向圖G=<V,E>具有歐拉回路，當且僅當G是連通的，并且所有結(jié)點的度數(shù)均為偶數(shù)。定理7.6有向圖G具有歐拉通路，當且僅當G是連通的，且除了兩個結(jié)點以外，其余結(jié)點的入度等于出度，而這兩個例外的結(jié)點中，一個結(jié)點的入度比出度大1，另一個結(jié)點的出度比入度大1。推論7.2有向圖G具有歐拉回路，當且僅當G是連通的，且所有結(jié)點的入度等于出度。歐拉通路與歐拉回路判別準則對任意給定的無向連通圖，只需通過對圖中各結(jié)點度數(shù)的計算，就可知它是否存在歐拉通路及歐拉回路，從而知道它是否為歐拉圖；對任意給定的有向連通圖，只需通過對圖中各結(jié)點出度與入度的計算，就可知它是否存在歐拉通路及歐拉回路，從而知道它是否為歐拉圖。利用這項準則，很容易判斷出哥尼斯堡七橋問題是無解的，因為它所對應(yīng)的圖中所有4個結(jié)點的度數(shù)均為奇數(shù)；也很容易得到例7.19的結(jié)論。解題小貼士——歐拉圖的判斷2連通圖的無向圖（1）計算所有結(jié)點的度數(shù)。（2）存在0個奇度數(shù)結(jié)點則有歐拉回路，是歐拉圖；存在2個奇度數(shù)結(jié)點則有歐拉通路。連通圖的有向圖（1）計算所有結(jié)點的出度和入度。（2）所有結(jié)點的入度等于出度則有歐拉回路，是歐拉圖；兩個結(jié)點以外，其余結(jié)點的入度等于出度，而這兩個例外的結(jié)點中，一個結(jié)點的入度比出度大1，另一個結(jié)點的出度比入度大1，則有歐拉通路。v3v1v2v4v3v1v2v4v3v1v2v4(c)(a)(b)v3v1v2v4v3v1v2v4v3v1v2v4(f)(d)(e)橋定義11.2.2設(shè)G=<V,E>，e∈E，如果p(G-e)＞p(G)稱e為G的橋(Bridge)或割邊(Cutedge)。顯然，所有的懸掛邊都是橋。v1v4v2v3v6v5橋算法7.12求歐拉圖G=<V,E>的歐拉回路的Fleury算法：（1）任取v0∈V，令P0=v0，i=0；（2）按下面的方法從E-{e1,e2,…,ei}中選取ei+1：①

ei+1與vi相關(guān)聯(lián)；②

除非無別的邊可選取，否則ei+1不應(yīng)該為G’=G-{e1,e2,…,ei}中的橋；（3）將邊ei+1加入通路P0中，令 P0=v0e1v1e2…eiviei+1vi+1，i=i+1；（4）如果i=|E|，結(jié)束，否則轉(zhuǎn)（2）。要點：

在可能的情況下，不選橋僅有歐拉通路的圖中如何找出其中的歐拉通路從v1出發(fā)的一條歐拉回路為：v1e1v2e4v5e7v8e11v6例7.20用Fleury算法求歐拉圖的一條歐拉回路。v1v7v5v3v2v8v4e1e2e3e4e5e6e10e7e8e9e11e12v6不選橋e8e2v3e5v6e9v2e12v8e3v4e6v7e10v4e8v1

P12=內(nèi)容導(dǎo)航CONTENTS歷史人物本章導(dǎo)讀及學(xué)習(xí)要求樹根樹歐拉圖偶圖

7.1

7.2

7.3

7.4作業(yè)

7.5平面圖特殊圖的應(yīng)用哈密頓圖

7.7

7.6

7.87.4.1哈密頓的引入與定義1859年，威廉.哈密頓爵士正十二面體每個面都是正五邊形，三面交于一角20個頂點、30條邊和12個面1234567208910111213141516171819平面展開哈密頓圖定義7.13經(jīng)過圖中每個結(jié)點一次且僅一次的通路（回路）稱為哈密頓通路（回路）（HamiltonianEntry/circuit）。存在哈密頓回路的圖稱為哈密頓圖（HamiltonianGraph）。規(guī)定：平凡圖為哈密頓圖。以上定義既適合無向圖，又適合有向圖。哈密頓通路和哈密頓回路的特征哈密頓通路是經(jīng)過圖中所有結(jié)點的通路中長度最短的通路，即為通過圖中所有結(jié)點的基本通路哈密頓回路是經(jīng)過圖中所有結(jié)點的回路中長度最短的回路，即為通過圖中所有結(jié)點的基本回路如果我們僅用結(jié)點來描述的話哈密頓通路就是圖中所有結(jié)點的一種全排列哈密頓回路就是圖中所有結(jié)點的一種全排列再加上該排列中第一個結(jié)點的一種排列從定義可看出，若圖中存在哈密頓通路（回路），則該圖是連通的。又可知平行邊與環(huán)存在與否不影響圖中是否存在哈密頓通路（回路），約定以后討論均為連通的簡單圖。解題小貼士——哈密頓圖的判斷1找到一條經(jīng)過圖中每個結(jié)點一次且僅一次的通路（回路），則該圖存在哈密頓通路（回路）。有哈密頓回路的圖則為哈密頓圖。例7.21判斷下面6個圖中，是否是哈密頓圖？是否存在哈密頓通路？哈密頓圖

不存在哈密頓通路

不是哈密頓圖，但存在哈密頓通路

哈密頓圖

不是哈密頓圖，但存在哈密頓通路不存在哈密頓通路

v3v1v2v4(a)v3v1v2v4(d)v3v1v2v4(b)v5v6v7v2v4v1v5(c)v3v3v1v2v4(e)v3v1v2v4(f)7.4.2哈密頓圖的判定定理7.7設(shè)無向圖G=<V,E>是哈密頓圖，V1是V的任意非空子集，則p(G-V1)≤|V1|其中p(G-V1)是從G中刪除V1后所得到圖的連通分支數(shù)。證明設(shè)C是G中的一條哈密頓回路，V1是V的任意非空子集。下面分兩種情況討論：（1）V1中結(jié)點在C中均相鄰，顯然C-V1仍是連通的，但已非回路，因此p(C-V1)=1≤|V1|。（2）V1中結(jié)點在C上存在r(2≤r≤|V1|)個互不相鄰，C-V1是將C分為互不相連的r段，即p(C-V1)=r≤|V1|一般情況下，V1中結(jié)點在C中即有相鄰的，又有不相鄰的，因此總有p(C-V1)≤|V1|。因C是G的生成子圖，從而C-V1是G-V1的生成子圖，故p(G-V1)≤p(C-V1)≤|V1|。推論7.3設(shè)無向圖G=<V,E>中存在哈密頓通路，則對V的任意非空子集V1，都有p(G-V1)≤|V1|+1定理7.7在應(yīng)用中它本身用處不大，但它的逆否命題卻非常有用。我們經(jīng)常利用定理7.7的逆否命題來判斷某些圖不是哈密頓圖，即：若存在V的某個非空子集V1使得p(G-V1)＞|V1|，則G不是哈密頓圖。注意：定理7.7給出的是哈密頓圖的必要條件，而不是充分條件。v3v1v2v4v5v6v7v2v4v1v5v3解題小貼士——判斷不是哈密頓圖在圖中能夠找到V的某個非空子集V1使得p(G－V1)＞|V1|則G不是哈密頓圖；在圖中能夠找到V的某個非空子集V1使得p(G－V1)＞|V1|＋1則G中不存在哈密頓通路。例7.22證明下圖中不存在哈密頓回路。證明

在圖中，刪除結(jié)點子集｛d,e,f｝，得到的圖，有4個連通分支，由定理7.7知，該圖不是哈密頓圖，因而不會存在哈密頓回路。dfeabcgih結(jié)論定理7.8設(shè)G=<V,E>是具有n個結(jié)點的簡單無向圖。如果對任意兩個不相鄰的結(jié)點u,v∈V，均有

deg(u)+deg(v)≥n-1則G中存在哈密頓通路。推論7.4設(shè)G=<V,E>是具有n個結(jié)點的簡單無向圖。如果對任意兩個不相鄰的結(jié)點u,v∈V，均有

deg(u)+deg(v)≥n則G中存在哈密頓回路。推論7.5設(shè)G=<V,E>是具有n（n≥3）個結(jié)點的簡單無向圖。如果對任意v∈V，均有

deg(v)≥n/2，則G是哈密頓圖。注意定理7.8及其推論給出的是哈密頓圖（通路）的充分條件，而不是必要條件。在六邊形圖中，任兩個不相鄰的結(jié)點的度數(shù)之和都是4＜6，但六邊形圖是哈密頓圖。v1v4v6v5v3v2解題小貼士——哈密頓圖的判斷2任意兩個不相鄰的結(jié)點度數(shù)之和≥n－1，則存在哈密頓通路。任意兩個不相鄰的結(jié)點度數(shù)之和≥n，則存在哈密頓回路，該圖為哈密頓圖。例7.23某地有5個風景點，若每個風景點均有2條道路與其他點相通。問游人可否經(jīng)過每個風景點恰好一次而游完這5處？解看成是有5個結(jié)點的無向圖，兩風景點間的道路看成是無向圖的邊，因此每個結(jié)點的度數(shù)均為2，從而任意兩個不相鄰的結(jié)點的度數(shù)之和等于4，正好為總結(jié)點數(shù)減1。故此圖中存在一條哈密頓通路，因此游人可以經(jīng)過每個風景點恰好一次而游完這5處。例7.24判斷是否存在哈密頓回路

方法一：刪除結(jié)點子集{a,b,c,d,e}，得到的圖有7個連通分支，該圖不是哈密頓圖，故不存在哈密頓回路。e541a2b3cdfghijkmnop54123fghijkmnop例7.24判斷是否存在哈密頓回路

方法二：若圖中存在哈密頓回路，則該回路組成的圖中任何結(jié)點的度數(shù)均為2。因而結(jié)點1、2、3、4、5所關(guān)聯(lián)的邊均在回路中，于是在結(jié)點a、b、c、d、e處均應(yīng)將不與1、2、3、4、5關(guān)聯(lián)的邊刪除，而要刪除與結(jié)點a、b、c、d、e關(guān)聯(lián)的其它邊，得到右圖。它不是連通圖，因而圖中不存在哈密頓回路。e541a2b3cdfghijkmnop定理7.9設(shè)G=<V,E>是有n(n≥2)個結(jié)點的一些簡單有向圖。如果忽略G中邊的方向所得的無向圖中含生成子圖Kn，則有向圖G中存在哈密頓通路。在右圖中，它所對應(yīng)的無向圖中含完全圖K5，由定理7.9知，圖中含有哈密頓通路。事實上，通路v3v5v4v2v1為一條哈密頓通路。v2v3v1v4v5內(nèi)容導(dǎo)航CONTENTS歷史人物本章導(dǎo)讀及學(xué)習(xí)要求樹根樹歐拉圖偶圖

7.1

7.2

7.3

7.4作業(yè)

7.5平面圖特殊圖的應(yīng)用哈密頓圖

7.7

7.6

7.87.5.1偶圖的定義定義7.14若無向圖G=<V,E>的結(jié)點集V能夠劃分為兩個子集V1,V2，滿足V1∩V2=

，且V1∪V2=V，使得G中任意一條邊的兩個端點，一個屬于V1，另一個屬于V2，則稱G為偶圖(BipartiteGraph)或二分圖(Bigraph)。V1和V2稱為互補結(jié)點子集，偶圖通常記為G=<V1,E,V2>。定義7.15在偶圖G=<V1,E,V2>中，若V1中的每個結(jié)點與V2中的每個結(jié)點都有且僅有一條邊相關(guān)聯(lián)，則稱偶圖G為完全偶圖(CompleteBipartiteGraph)或完全二分圖(CompleteBigraph)，記為Ki,j，其中，i=|V1|，j=|V2|。偶圖沒有環(huán)。平凡圖和零圖可看成特殊的偶圖。解題小貼士——偶圖的判斷找到結(jié)點集V的兩個互補子集，使得每條邊的兩個端點都各在一個子集中（或者每個子集中的結(jié)點間都無邊相連），則該圖為偶圖。例7.23判斷下圖中的幾個圖，那些是偶圖？那些是完全偶圖？v1v2v3v4v5v6v7(a)v6v1v4v3v5v2(d)(b)v1v2v3v4v5(c)v1v2v3v4v5v6v1v4v2v3(e)偶圖偶圖偶圖偶圖不是偶圖完全偶圖K2,3

完全偶圖K3,3

完全偶圖K3,3

7.5.2偶圖的判定定理7.10無向圖G=<V,E>為偶圖的充分必要條件是G的所有回路的長度均為偶數(shù)。證明

必要性：設(shè)圖G是偶圖G=<V1,E,V2>，令C=v0v1v2…vkv0是G的一條回路，其長度為k+1。不失一般性，假設(shè)v0∈V1，由偶圖的定義知，v1∈V2，v2∈V1。由此可知，v2i∈V1且v2i+1∈V2。又因為v0∈V1，所以vk∈V2，因而k為奇數(shù)，故C的長度為偶數(shù)。充分性：設(shè)G中每條回路的長度均為偶數(shù)，若G是連通圖，任選v0∈V，定義V的兩個子集如下：V1={vi|d(v0,vi)為偶數(shù)}，

V2=V-V1?，F(xiàn)證明V1中任兩結(jié)點間無邊存在。假若存在一條邊(vi,vj)∈E，其中vi,vj∈V1，則由v0到vi間的短程線(長度為偶數(shù))以及邊(vi,vj)，再加上vj到v0間的短程線(長度為偶數(shù))所組成的回路的長度為奇數(shù)，與假設(shè)矛盾。充分性同理可證V2中任兩結(jié)點間無邊存在。故G中每條邊(vi,vj)，必有vi∈V1，vj∈V2或vi∈V2，vj∈V1，因此G是具有互補結(jié)點子集V1和V2的偶圖。若G中每條回路的長度均為偶數(shù)，但G不是連通圖，則可對G的每個連通分支重復(fù)上述論證，并可得到同樣的結(jié)論。定理7.10的用途在實際應(yīng)用中，定理7.10本身使用不多，我們常使用它的逆否命題來判斷一個圖不是偶圖：無向圖G不是偶圖的充分必要條件是G中存在長度為奇數(shù)的回路。例如右圖中存在長度為3的回路v1v2v4v1，所以它不是偶圖。v1v4v2v3解題小貼士——判斷不是偶圖找到一條長度為奇數(shù)的回路，則該圖不是偶圖。7.5.3匹配定義7.16在偶圖G=<V1,E,V2>中，V1={v1,v2,…,vq}，若存在E的子集E’={(v1,v1’)，(v2,v2’)，…，(vq,vq’)，其中v1’,v2’,…,vq’

是V2中的q個不同的結(jié)點}，則稱G的子圖G’=<V1,E’,V2>為從V1到V2的一個完全匹配(CompleteMatching)，簡稱匹配。在偶圖G=<V1,E,V2>中，若存在V1