第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)讀本章介紹幾種特殊的圖：樹歐拉圖哈密頓圖偶圖平面圖重點(diǎn)1無(wú)向樹的基本概念2無(wú)向樹的性質(zhì)，特別是m＝n－1和至少2個(gè)葉結(jié)點(diǎn)3生成樹與最小生成樹及其求解算法4

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

哈密頓圖及其判定7

偶圖及其判定，匹配8平面圖及其判定，歐拉公式，庫(kù)拉托夫斯基定理難點(diǎn)1

哈密頓圖的判定2

平面圖的判定3

庫(kù)拉托夫斯基定理學(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歲能讀英語(yǔ)，會(huì)算術(shù)；5歲能譯拉丁語(yǔ)、希臘語(yǔ)和希伯來(lái)語(yǔ)，并能背誦荷馬史詩(shī)；9歲便熟悉了波斯語(yǔ)、阿拉伯語(yǔ)和印地語(yǔ)。他自幼喜歡算術(shù)，計(jì)算很快。1818年遇到美國(guó)“計(jì)算神童”Z．科耳本（Colburn）后對(duì)數(shù)學(xué)產(chǎn)生了更深厚的興趣。到1820年已閱讀了牛頓的《自然哲學(xué)的數(shù)學(xué)原理》，并對(duì)天文學(xué)有強(qiáng)烈愛(ài)好，常用自己的望遠(yuǎn)鏡觀測(cè)天體。威廉·哈密頓愛(ài)爾蘭數(shù)學(xué)家、物理學(xué)家、力學(xué)家哈密頓1820年開始讀P．S．拉普拉斯（Laplace）的著作《天體力學(xué)》，1822年指出了此書中的一個(gè)錯(cuò)誤；同年他開始進(jìn)行科學(xué)研究工作，對(duì)曲線和曲面的性質(zhì)進(jìn)行了系列研究，并用于幾何光學(xué)。愛(ài)爾蘭科學(xué)院院士R．J．布林克萊（Brinkley）稱他是“這個(gè)年齡（17歲）的第一數(shù)學(xué)家”。首先建立了光學(xué)的數(shù)學(xué)理論，并把這種理論移植到動(dòng)力學(xué)中去，提出了著名的“哈密頓最小作用原理”，即用一個(gè)變分式推出各種動(dòng)力學(xué)定律。還把廣義坐標(biāo)和廣義動(dòng)量作為典型變量來(lái)建立動(dòng)力學(xué)方程──哈密頓典型方程。威廉·哈密頓愛(ài)爾蘭數(shù)學(xué)家、物理學(xué)家、力學(xué)家哈密頓還建立了與系統(tǒng)的總能量有關(guān)的哈密頓函數(shù)，這些工作推動(dòng)了變分法和微分方程理論的進(jìn)一步研究。哈密頓方程是一個(gè)經(jīng)典力學(xué)方程。哈密頓函數(shù)既是經(jīng)典物理學(xué)中的一個(gè)函數(shù)，也是量子物理學(xué)中的一個(gè)算子。哈密頓圖是圖論中的一個(gè)術(shù)語(yǔ)。他也喜歡文學(xué)，成為數(shù)學(xué)大師后，仍不斷賦詩(shī)填詞，一直認(rèn)為文學(xué)與數(shù)學(xué)是近似的學(xué)科——都是抽象思維的文字與符號(hào)。他曾寫道：“詩(shī)與數(shù)學(xué)是近親?！蓖す茴D愛(ài)爾蘭數(shù)學(xué)家、物理學(xué)家、力學(xué)家哈夫曼他從小聰慧好學(xué)，在俄亥俄州立大學(xué)畢業(yè)時(shí)只有17歲。然后他進(jìn)入麻省理工學(xué)院（MIT）一邊工作，一邊深造，哈夫曼編碼就是他在1952年做博士論文時(shí)發(fā)明的。這是一種根據(jù)字母的使用頻率而設(shè)計(jì)的變長(zhǎng)碼，能大大提高信息的傳輸效率，至今仍有廣泛的應(yīng)用。在MIT一直工作到1967年。之后轉(zhuǎn)入加州大學(xué)的圣克魯茲分校，成為該校計(jì)算機(jī)科學(xué)系的創(chuàng)始人，并于1970年至1973年任系主任，為此系的學(xué)術(shù)研究做出了許多杰出貢獻(xiàn)。1994年哈夫曼退休。戴維·哈夫曼美國(guó)計(jì)算機(jī)科學(xué)家哈夫曼除了哈夫曼編碼外，哈夫曼在其他方面也有不少創(chuàng)造，他設(shè)計(jì)的二叉最優(yōu)搜索樹算法就被認(rèn)為是同類算法中效率最高的，因而被命名為哈夫曼算法，是動(dòng)態(tài)規(guī)劃（DynamicProgramming）的一個(gè)范例。哈夫曼算法也廣泛應(yīng)用于傳真機(jī)、圖像壓縮和計(jì)算機(jī)安全領(lǐng)域。但他卻從未為此算法申請(qǐng)過(guò)專利或其他能夠?yàn)樗麕?lái)經(jīng)濟(jì)利益的東西，而是將全部的精力放在教學(xué)上，用他自己的話來(lái)說(shuō)，“我所要給世界帶來(lái)的就是我的學(xué)生?！贝骶S·哈夫曼美國(guó)計(jì)算機(jī)科學(xué)家哈夫曼1982年獲得美國(guó)電氣與電子工程師學(xué)會(huì)（IEEE）計(jì)算機(jī)先驅(qū)獎(jiǎng)。1973年獲得IEEE的麥克道爾（McDowell）獎(jiǎng)。1998年IEEE下屬的信息論分會(huì)為紀(jì)念信息論創(chuàng)立50周年，授予他金禧（GoldenJubilee）獎(jiǎng)。1999年6月，榮獲了以哈明碼發(fā)明人命名的哈明獎(jiǎng)?wù)拢℉ammingMedal）。戴維·哈夫曼美國(guó)計(jì)算機(jī)科學(xué)家管梅谷1957年畢業(yè)于華東師范大學(xué)數(shù)學(xué)系1957年至1990年在山東師范大學(xué)工作1984年至1990年擔(dān)任山東師范大學(xué)校長(zhǎng)1990年至1995年任復(fù)旦大學(xué)運(yùn)籌學(xué)系主任一直從事運(yùn)籌學(xué)、組合優(yōu)化與圖論方面的研究工作，是國(guó)內(nèi)外知名度很高的學(xué)者。代表性論著有《線性規(guī)劃》《圖論中的幾個(gè)極值問(wèn)題》《奇偶點(diǎn)圖上作業(yè)法》等。1960年在國(guó)際上最先提出的郵遞員問(wèn)題被國(guó)際圖論界命名為“中國(guó)郵路問(wèn)題”，載入經(jīng)典著作。2016年，被中國(guó)運(yùn)籌學(xué)會(huì)授予科學(xué)技術(shù)獎(jiǎng)——終身成就獎(jiǎng)。管梅谷上海市人數(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引言樹是圖論中的一個(gè)非常重要的概念，而在計(jì)算機(jī)科學(xué)中有著非常廣泛的應(yīng)用，例如現(xiàn)代計(jì)算機(jī)操作系統(tǒng)均采用樹形結(jié)構(gòu)來(lái)組織文件和文件夾，本章介紹樹的基本知識(shí)和應(yīng)用。在本章中，所談到的圖都假定是簡(jiǎn)單圖；所談到的回路均指簡(jiǎn)單回路或基本回路。并且同一個(gè)圖形表示的回路(簡(jiǎn)單的或基本的)，可能有不同的交替序列表示方法，但我們規(guī)定它們表示的是同一條回路。7.1.1樹的基本概念及性質(zhì)例7.12018年俄羅斯世界杯8強(qiáng)的比賽結(jié)果圖，最后勝利的隊(duì)捧得大力神杯。英格蘭瑞典俄羅斯克羅地亞巴西比利時(shí)烏拉圭法國(guó)英格蘭克羅地亞比利時(shí)法國(guó)克羅地亞法國(guó)法國(guó)定義7.1連通而不含回路的無(wú)向圖稱為無(wú)向樹(UndirectedTree)，簡(jiǎn)稱樹(Tree)，常用T表示樹。樹中度數(shù)為1的結(jié)點(diǎn)稱為葉(Leaf)；度數(shù)大于1的結(jié)點(diǎn)稱為分支點(diǎn)(BranchPoint)或內(nèi)部結(jié)點(diǎn)(InteriorPoint)。每個(gè)連通分支都是樹的無(wú)向圖稱為森林(Forest)。平凡圖稱為平凡樹(TrivialTree)。不含回路的無(wú)向圖稱為森林樹中沒(méi)有環(huán)和平行邊，因此一定是簡(jiǎn)單圖在任何非平凡樹中，都無(wú)度數(shù)為0的結(jié)點(diǎn)解題小貼士——無(wú)向圖G是樹的判斷（1）圖G是連通的。（2）圖G中不存在回路。例10.2.2判斷下圖中的圖哪些是樹？為什么？(a)(b)(c)(d)樹樹不是樹森林不是樹連通，無(wú)回路連通，無(wú)回路不連通有回路，無(wú)回路不是森林樹的性質(zhì)定理10.2.1設(shè)無(wú)向圖G=<V,E>，|V|=n，|E|=m，下列各命題是等價(jià)的：G連通而不含回路(即G是樹)G中無(wú)回路，且m=n-1G是連通的，且m=n-1G中無(wú)回路，但在G中任二結(jié)點(diǎn)之間增加一條新邊，就得到惟一的一條基本回路G是連通的，但刪除G中任一條邊后，便不連通(n≥2)G中每一對(duì)結(jié)點(diǎn)之間有惟一一條基本通路(n≥2)證明①②：對(duì)n作歸納。n=1時(shí)，m=0，顯然有m=n-1。假設(shè)n=k時(shí)命題成立，現(xiàn)證n=k+1時(shí)也成立。由于G連通而無(wú)回路，所以G中至少有一個(gè)度數(shù)為1的結(jié)點(diǎn)v0，在G中刪去v0及其關(guān)聯(lián)的邊，便得到k個(gè)結(jié)點(diǎn)的連通而無(wú)回路的圖，由歸納假設(shè)知它有k-1條邊。再將結(jié)點(diǎn)v0及其關(guān)聯(lián)的邊加回得到原圖G，所以G中含有k+1個(gè)結(jié)點(diǎn)和k條邊，符合公式m=n-1。所以，G中無(wú)回路，且m=n-1。G連通而不含回路(即G是樹)G中無(wú)回路，且m=n-1；②③：設(shè)G有k個(gè)連通分支G1，G2，…，Gk，其結(jié)點(diǎn)數(shù)分別為n1，n2，…，nk，邊數(shù)分別為m1，m2，…，mk，且，由于G中無(wú)回路，所以每個(gè)Gi(i=1,2,…,k)均為樹，因此mi=ni–1（i=1,2,…,k），于是故k=1，所以G是連通的，且m=n-1。G中無(wú)回路，且m=n-1；G是連通的，且m=n-1；③④：首先證明G中無(wú)回路。對(duì)n作歸納。n=1時(shí)，m=n-1=0，顯然無(wú)回路。假設(shè)結(jié)點(diǎn)數(shù)n=k-1時(shí)無(wú)回路，下面考慮結(jié)點(diǎn)數(shù)n=k的情況。因G連通，故G中每一個(gè)結(jié)點(diǎn)的度數(shù)均大于等于1?？梢宰C明至少有一個(gè)結(jié)點(diǎn)v0，使得deg(v0)=1，因若k個(gè)結(jié)點(diǎn)的度數(shù)都大于等于2，則從而m≥k，即至少有k條邊，但這與m=n-1矛盾。G是連通的，且m=n-1；G中無(wú)回路，但在G中任二結(jié)點(diǎn)之間增加一條新邊，就得到惟一的一條基本回路；③④：在G中刪去v0及其關(guān)聯(lián)的邊，得到新圖G’，根據(jù)歸納假設(shè)知G’無(wú)回路，所以再將結(jié)點(diǎn)v0及其關(guān)聯(lián)的邊加回得到原圖G，則G也無(wú)回路。其次證明在G中任二結(jié)點(diǎn)vi，vj之間增加一條邊(vi,vj)，得到一條且僅一條基本回路。由于G是連通的，從vi到vj有一條通路L，再在L中增加一條邊(vi,vj)，就構(gòu)成一條回路。若此回路不是惟一和基本的，則刪去此新邊，G中必有回路，得出矛盾。由于deg(v0)=1，④⑤：若G不連通，則存在兩結(jié)點(diǎn)vi和vj，在vi和vj之間無(wú)通路，此時(shí)增加邊(vi,vj)，不會(huì)產(chǎn)生回路，但這與題設(shè)矛盾。由于G無(wú)回路，所以刪去任一邊，圖便不連通。G中無(wú)回路，但在G中任二結(jié)點(diǎn)之間增加一條新邊，就得到惟一的一條基本回路；G是連通的，但刪除G中任一條邊后，便不連通；(n≥2)G是連通的，但刪除G中任一條邊后，便不連通；(n≥2)G中每一對(duì)結(jié)點(diǎn)之間有惟一一條基本通路。(n≥2)⑤⑥：由于G是連通的，因此G中任二結(jié)點(diǎn)之間都有通路，于是有一條基本通路。若此基本通路不惟一，則G中含有回路，刪去回路上的一條邊，G仍連通，這與題設(shè)不符。所以此基本通路是惟一的。⑥①：顯然G是連通的。若G中含回路，則回路上任二結(jié)點(diǎn)之間有兩條基本通路，這與題設(shè)矛盾。因此，G連通且不含回路。G中每一對(duì)結(jié)點(diǎn)之間有惟一一條基本通路

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

于是2(n-1)≥2n-k，這說(shuō)明T中至少有兩片葉。平凡樹有多少片葉07..2生成樹及算法定義7.2給定圖G=<V,E>，若G的某個(gè)生成子圖是樹，則稱之為G的生成樹(SpanningTree)，記為TG。生成樹TG中的邊稱為樹枝(Branch)G中不在TG中的邊稱為弦(Chord)TG的所有弦的集合稱為生成樹的補(bǔ)(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è)圖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é)點(diǎn)集。如果G1中無(wú)回路，G1就是生成樹。如果G1仍存在回路C2，可刪除C2中一條邊，如此繼續(xù)，直到得到一個(gè)無(wú)回路的連通圖H為止。因此，H是G的生成樹。如果G中無(wú)回路，G本身就是生成樹。

說(shuō)明一個(gè)無(wú)向連通圖G，如果G是樹，則它的生成樹是唯一的，就是G本身。如果G不是樹，那么它的生成樹就不唯一了。定理7.3的證明過(guò)程就給出了求連通圖G＝(n,m)的生成樹的一種算法，稱為“破圈法”，算法的關(guān)鍵是判斷G中是否有回路。若有回路，則刪除回路中的一條邊，直到剩下的圖中無(wú)回路為止，由定理7.1知，共刪除m-n+1條邊。由定理7.3和定理7.1，連通圖G＝(n,m)一定存在生成樹，且其有n個(gè)結(jié)點(diǎn)，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)的生成樹使用破圈法：找出一條回路，并刪除該回路中的一條邊，直到圖中沒(méi)有回路為止，刪除的邊的總數(shù)為m-n+1。使用避圈法：選取一條邊，驗(yàn)證該邊與已選取的邊不構(gòu)成回路，選取的邊的總數(shù)為n-1。例7.4用破圈法生成樹由于n=6，m=9，所以m-n+1=4，故要?jiǎng)h除的邊數(shù)為4，因此只需4步即可。123456用避圈法求生成樹由于n=6，所以n-1=5，故要選取5條邊，因此需5步即可。123456123456說(shuō)明由于生成樹的形式不惟一，故上述兩棵生成樹都是所求的。破圈法和避圈法的計(jì)算量較大，主要是需要找出回路或驗(yàn)證不存在回路。算法7.3求連通圖G=<V,E>的生成樹的廣度優(yōu)先搜索算法：任選s∈V，將s標(biāo)記為0，令L={s}，V=V-{s}，k=0；如果V=Φ，則轉(zhuǎn)④，否則令k=k+1；依次對(duì)L中所有標(biāo)記為k-1的結(jié)點(diǎn)v，如果它與V中的結(jié)點(diǎn)w相鄰接，則將w標(biāo)記為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é)點(diǎn)開始，逐步搜索，完成對(duì)所有節(jié)點(diǎn)的標(biāo)記，所有結(jié)點(diǎn)與其前驅(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的每個(gè)樹枝所賦權(quán)值之和稱為T的權(quán)(Weight)，記為w(T)。G中具有最小權(quán)的生成樹稱為G的最小生成樹(MinimalSpanningTree)。

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

解題小貼士——使用Kruskal算法求最小生成樹按照邊的權(quán)值從小到大逐步搜索，選取那些與已選取邊不構(gòu)成回路的邊加入即可，共放入n-1條邊。注：在算法的步驟①和③中，若滿足條件的最小權(quán)邊不止一條，則可從中任選一條，這樣就會(huì)產(chǎn)生不同的最小生成樹。例7.6用Kruskal算法求圖中賦權(quán)圖的最小生成樹。解n=12，按算法要執(zhí)行n-1=11次，w(T)=36。4655761f923adbcimjkehg343446587582451f23adbcimjkehg343452算法7.5Prim算法（1）在G中任意選取一個(gè)結(jié)點(diǎn)v1，置VT={v1},ET=Φ，k=1；（2）在V-VT中選取與某個(gè)vi∈VT鄰接的結(jié)點(diǎn)vj，使得邊(vi,vj)的權(quán)最小，置VT=VT∪{vj},ET=ET∪{(vi,vj)}，k=k+1；（3）重復(fù)步驟(2)，直到k=|V|。要點(diǎn)：從任意結(jié)點(diǎn)開始，每次增加一條最小權(quán)邊構(gòu)成一棵新樹。解題小貼士——使用Prim算法求最小生成樹從平凡樹開始逐步搜索，每次選取與該樹的結(jié)點(diǎn)關(guān)聯(lián)的樹外的最小權(quán)邊構(gòu)成一棵新樹，共執(zhí)行n-1次。注：在算法的步驟(2)中，若滿足條件的最小權(quán)邊不止一條，則可從中任選一條，這樣就會(huì)產(chǎn)生不同的最小生成樹。例7.7用Prim算法求圖中賦權(quán)圖的最小生成樹。解n=7，按算法要執(zhí)行n-1=6次，w(T)=25。5f102dbce7g64582a5f2dbce7g452a由Prim算法可以看出，每一步得到的圖一定是樹，故不需要驗(yàn)證是否有回路，因此它的計(jì)算工作量較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一個(gè)有向圖，若略去所有有向邊的方向所得到的無(wú)向圖是一棵樹，則這個(gè)有向圖稱為有向樹(DirectedTree)。解題小貼士——有向樹的判斷（1）將所有有向邊都略去方向變?yōu)闊o(wú)向邊，得到一個(gè)無(wú)向圖。（2）判斷該無(wú)向圖是否是樹。例7.8判斷下圖中的圖哪些是有向樹？為什么？(a)(c)(e)(d)(b)不是有向樹不是有向樹有向樹有向樹有向樹一棵非平凡的有向樹，如果恰有一個(gè)結(jié)點(diǎn)的入度為0，其余所有結(jié)點(diǎn)的入度均為1，則稱之為根樹(RootTree)或外向樹(OutwardTree)。

入度為0的結(jié)點(diǎn)稱為根(Root)；出度為0的結(jié)點(diǎn)稱為葉(Leaf)；入度為1，出度大于0的結(jié)點(diǎn)稱為內(nèi)點(diǎn)(InteriorPoint)；又將內(nèi)點(diǎn)和根統(tǒng)稱為分支點(diǎn)(BranchPoint)。在根樹中，從根到任一結(jié)點(diǎn)v的通路長(zhǎng)度，稱為該結(jié)點(diǎn)的層數(shù)(LayerNumber)；稱層數(shù)相同的結(jié)點(diǎn)在同一層上；所有結(jié)點(diǎn)的層數(shù)中最大的稱為根樹的高(Height)。定義7.5解題小貼士——根樹的判斷（1）判斷是否為有向樹。（2）計(jì)算所有結(jié)點(diǎn)的度數(shù)，看是否恰有一個(gè)結(jié)點(diǎn)的入度為0，其余所有結(jié)點(diǎn)的入度均為1。例7.9判斷下圖所示的圖是否是根樹？若是根樹，給出其根、葉和內(nèi)點(diǎn)，計(jì)算所有結(jié)點(diǎn)所在的層數(shù)和高。是根樹根：v1葉：v5,v6,v8,v9,v10,v12,v13內(nèi)點(diǎn)：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é)點(diǎn)vi到vj可達(dá)，則稱vi是vj的祖先(Ancestor)，vj是vi的后代(Descendant)；若<vi,vj>是根樹中的有向邊，則稱vi是vj的父親(Father)，vj是vi的兒子(Son)；如果兩個(gè)結(jié)點(diǎn)是同一個(gè)結(jié)點(diǎn)的兒子，則稱這兩個(gè)結(jié)點(diǎn)是兄弟(Brother)。定義7.7如果在根樹中規(guī)定了每一層上結(jié)點(diǎn)的次序，這樣的根樹稱為有序樹(OrderedTree)。一般地，在有序樹中同一層中結(jié)點(diǎn)的次序?yàn)閺淖笾劣?。有時(shí)也可以用邊的次序來(lái)代替結(jié)點(diǎn)的次序。k元樹定義7.8設(shè)T為根樹。（1）若T的每個(gè)分支點(diǎn)至多有k個(gè)兒子，則稱T為k元樹（或k叉樹）（k-aryTree）；（2）若T的每個(gè)分支點(diǎn)都恰有k個(gè)兒子，則稱T為完全k元樹（Completek-aryTree）；（3）若T是k元完全樹且每個(gè)葉結(jié)點(diǎn)的層數(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元樹至少要有一個(gè)分支點(diǎn)有k個(gè)兒子。注：有些書中k叉樹專指k元有序樹完全k元樹又稱為k元完全樹，k叉正則樹滿k元樹又稱為k叉完全正則樹子樹在根樹T中，任一結(jié)點(diǎn)v及其所有后代導(dǎo)出的子圖T’稱為T的以v為根的子樹(Subtree)。當(dāng)然，T’也可以有自己的子樹。有序2元樹的每個(gè)結(jié)點(diǎn)v至多有兩個(gè)兒子，分別稱為v的左兒子(LeftSon)和右兒子(RightSon)。有序2元樹的每個(gè)結(jié)點(diǎn)v至多有兩棵子樹，分別稱為v的左子樹(LeftSubtree)和右子樹(RightSubtree)。注意區(qū)分以v為根的子樹和v的左(右)子樹，v為根的子樹包含v，而v的左(右)子樹不包含v。解題小貼士——k元樹的判斷必須是根樹計(jì)算所有分支點(diǎn)的兒子數(shù)每個(gè)分支點(diǎn)至多有k（包含k）個(gè)兒子即為k元樹每個(gè)分支點(diǎn)都恰有k個(gè)兒子即為完全k元樹每個(gè)分支點(diǎn)都恰有k個(gè)兒子且每個(gè)葉結(jié)點(diǎn)的層數(shù)均相同即為滿k元樹例7.10判斷下圖所示的幾棵根樹是什么樹？2元完全樹

3元樹

3元完全樹

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

m＝2t－2

＝

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

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

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

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

的最優(yōu)二元樹T。（2）在T上求一個(gè)前綴碼。0100110100000010101510102025301525455510010110001CFDBAE1051020253015254555100（3）傳輸100個(gè)這樣的字母所用的二進(jìn)制位為：4×(5+10)+3×10+2×(20+25+30)=240（3）設(shè)樹葉vi帶權(quán)為w％×100=w，則vi處的符號(hào)串表示出現(xiàn)頻率為w％的字母。{01，10，11，001，0001，0000}為一前綴碼，其中 0000表示F， 0001表示E， 001表示D， 01表示C， 10表示B， 11表示A。傳輸100個(gè)這樣的字母所用的二進(jìn)制位為：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)七橋問(wèn)題BCADb6b2b5b7b4b1b3ABCDb5b2b1b3b7b4b6歐拉圖定義11.2.1設(shè)G是無(wú)孤立結(jié)點(diǎn)的圖，若存在一條通路(回路)，經(jīng)過(guò)圖中每邊一次且僅一次，則稱此通路(回路)為該圖的一條歐拉通路(回路)(EulerianEntry/Circuit)。具有歐拉回路的圖稱為歐拉圖(EulerianGraph)。規(guī)定：平凡圖為歐拉圖。以上定義既適合無(wú)向圖，又適合有向圖。歐拉通路和歐拉回路的特征歐拉通路是經(jīng)過(guò)圖中所有邊的通路中長(zhǎng)度最短的通路，即為通過(guò)圖中所有邊的簡(jiǎn)單通路；歐拉回路是經(jīng)過(guò)圖中所有邊的回路中長(zhǎng)度最短的回路，即為通過(guò)圖中所有邊的簡(jiǎn)單回路。如果僅用邊來(lái)描述，歐拉通路和歐拉回路就是圖中所有邊的一種全排列。解題小貼士——?dú)W拉圖的判斷1找到一條經(jīng)過(guò)圖中每邊一次且僅一次的通路（回路），則該圖存在歐拉通路（回路）。有歐拉回路的圖為歐拉圖。例7.19判斷下面的圖中，是否是歐拉圖？是否存在歐拉通路？歐拉圖

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

不存在歐拉通路

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

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

不存在歐拉通路

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

若連通的無(wú)向圖有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是G中每條歐拉通路的端點(diǎn)。結(jié)論推論7.1無(wú)向圖G=<V,E>具有歐拉回路，當(dāng)且僅當(dāng)G是連通的，并且所有結(jié)點(diǎn)的度數(shù)均為偶數(shù)。定理7.6有向圖G具有歐拉通路，當(dāng)且僅當(dāng)G是連通的，且除了兩個(gè)結(jié)點(diǎn)以外，其余結(jié)點(diǎn)的入度等于出度，而這兩個(gè)例外的結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大1，另一個(gè)結(jié)點(diǎn)的出度比入度大1。推論7.2有向圖G具有歐拉回路，當(dāng)且僅當(dāng)G是連通的，且所有結(jié)點(diǎn)的入度等于出度。歐拉通路與歐拉回路判別準(zhǔn)則對(duì)任意給定的無(wú)向連通圖，只需通過(guò)對(duì)圖中各結(jié)點(diǎn)度數(shù)的計(jì)算，就可知它是否存在歐拉通路及歐拉回路，從而知道它是否為歐拉圖；對(duì)任意給定的有向連通圖，只需通過(guò)對(duì)圖中各結(jié)點(diǎn)出度與入度的計(jì)算，就可知它是否存在歐拉通路及歐拉回路，從而知道它是否為歐拉圖。利用這項(xiàng)準(zhǔn)則，很容易判斷出哥尼斯堡七橋問(wèn)題是無(wú)解的，因?yàn)樗鶎?duì)應(yīng)的圖中所有4個(gè)結(jié)點(diǎn)的度數(shù)均為奇數(shù)；也很容易得到例7.19的結(jié)論。解題小貼士——?dú)W拉圖的判斷2連通圖的無(wú)向圖（1）計(jì)算所有結(jié)點(diǎn)的度數(shù)。（2）存在0個(gè)奇度數(shù)結(jié)點(diǎn)則有歐拉回路，是歐拉圖；存在2個(gè)奇度數(shù)結(jié)點(diǎn)則有歐拉通路。連通圖的有向圖（1）計(jì)算所有結(jié)點(diǎn)的出度和入度。（2）所有結(jié)點(diǎn)的入度等于出度則有歐拉回路，是歐拉圖；兩個(gè)結(jié)點(diǎn)以外，其余結(jié)點(diǎn)的入度等于出度，而這兩個(gè)例外的結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大1，另一個(gè)結(jié)點(diǎn)的出度比入度大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)；②

除非無(wú)別的邊可選取，否則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）。要點(diǎn)：

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

不存在哈密頓通路

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

哈密頓圖

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

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

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

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

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

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

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

方法二：若圖中存在哈密頓回路，則該回路組成的圖中任何結(jié)點(diǎn)的度數(shù)均為2。因而結(jié)點(diǎn)1、2、3、4、5所關(guān)聯(lián)的邊均在回路中，于是在結(jié)點(diǎn)a、b、c、d、e處均應(yīng)將不與1、2、3、4、5關(guān)聯(lián)的邊刪除，而要?jiǎng)h除與結(jié)點(diǎn)a、b、c、d、e關(guān)聯(lián)的其它邊，得到右圖。它不是連通圖，因而圖中不存在哈密頓回路。e541a2b3cdfghijkmnop定理7.9設(shè)G=<V,E>是有n(n≥2)個(gè)結(jié)點(diǎn)的一些簡(jiǎn)單有向圖。如果忽略G中邊的方向所得的無(wú)向圖中含生成子圖Kn，則有向圖G中存在哈密頓通路。在右圖中，它所對(duì)應(yīng)的無(wú)向圖中含完全圖K5，由定理7.9知，圖中含有哈密頓通路。事實(shí)上，通路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若無(wú)向圖G=<V,E>的結(jié)點(diǎn)集V能夠劃分為兩個(gè)子集V1,V2，滿足V1∩V2=

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

完全偶圖K3,3

完全偶圖K3,3

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

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

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