離散數(shù)學(xué)(7.7樹與生成樹)ppt課件.ppt

《離散數(shù)學(xué)(7.7樹與生成樹)ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、7.5樹與生成樹(TreesandSpanningTrees)7.5.1無向樹(UndirectedTrees)7.5.2無向圖中的生成樹與最小生成樹(SpanningTreesandMinimalSpanningTrees)7.5.1無向樹(UndirectedTrees)樹是圖論中的一個(gè)重要概念。早在1847年克?；舴蚓陀脴涞睦碚搧硌芯侩娋W(wǎng)絡(luò)，1857年凱萊在計(jì)算有機(jī)化學(xué)中Ｃ2H2n+2的同分異構(gòu)物數(shù)目時(shí)也用到了樹的理論。而樹在計(jì)算機(jī)科學(xué)中應(yīng)用更為廣泛。本節(jié)介紹樹的基本知識(shí)，其中談到的圖都假定是簡單圖。定

2、義7.5.1一個(gè)連通無圈無向圖稱為無向樹(簡稱為樹)。記作T。樹中度數(shù)為1的結(jié)點(diǎn)稱為樹葉（或終端結(jié)點(diǎn)），度數(shù)大于１的結(jié)點(diǎn)稱為分枝點(diǎn)（或內(nèi)點(diǎn)，或非終端結(jié)點(diǎn)）。一個(gè)無圈圖稱為森林。顯然若圖G是森林，則G的每個(gè)連通分支是樹。如圖7.5.1(a)所示的是一棵樹；(b)所示的是森林。圖7.5.1樹和森林示意圖【例7.5.1】判斷圖7.5.2中各圖是否為樹.圖7.5.2證：因?yàn)門是一棵n≥２的（n，m）樹，所以由定理7.5.1，有若T中的無樹葉，則T中每個(gè)頂點(diǎn)的度數(shù)≥2,則Σdeg(vi)≥2n,（2）若T中只有一片樹葉

3、，則T中只有一個(gè)結(jié)點(diǎn)度數(shù)為1,其它結(jié)點(diǎn)度數(shù)≥2,所以(1)(3)(2),(3)都與(1)矛盾。所以T中至少有兩片樹葉。證畢。定理7.5.1任一樹T中,至少有兩片樹葉(n≥2時(shí))。定理7.5.2一個(gè)無向圖（n,m）圖T是樹,當(dāng)且僅當(dāng)下列5條之一成立。(或者說,這5條的任一條都可作為樹的定義。)(1)無圈且m=n-1。(2)連通且m=n-1。(3)無圈,但增加任一新邊,得到且僅得到一個(gè)圈。(4)連通但刪去任一邊,圖便不連通(n≥2)。(5)每一對結(jié)點(diǎn)間有唯一的一條通路。(n≥2)。證:(1)證明由樹的定義可知T無

4、圈。下證m=n-1。對n作歸納。n=1時(shí),m=0,顯然m=n-1。假設(shè)n=k時(shí)命題成立,現(xiàn)證明n=k+1時(shí)也成立。由于樹是連通而無圈,所以至少有一個(gè)度數(shù)為1的結(jié)點(diǎn)v,在T中刪去v及其關(guān)聯(lián)邊,便得到k個(gè)結(jié)點(diǎn)的連通無圈圖。由歸納假設(shè)它有k-1條邊。再將頂點(diǎn)v及其關(guān)聯(lián)邊加回得到原圖T,所以T中含有k+1個(gè)頂點(diǎn)和k條邊,符合公式m=n-1。所以樹是無圈且m=n-1的圖。(2)證明由第(1)條可推出第(2)條。用反證法。若圖不連通,設(shè)T有k個(gè)連通分支(k≥2)T1,T2,…,Tk,其結(jié)點(diǎn)數(shù)分別是n1,n2,…,nk,邊

5、數(shù)分別為m1,m2,…,mk,于是得出矛盾。所以T是連通且m=n-1的圖。(3)證明由第(2)條可推出第(3)條。首先證明T無圈。對n作歸納證明。n=1時(shí),m=n-1=0,顯然無圈。假設(shè)結(jié)點(diǎn)數(shù)為n-1時(shí)無圈,今考察結(jié)點(diǎn)數(shù)是n的情況。此時(shí)至少有一個(gè)結(jié)點(diǎn)v其度數(shù)deg(v)=1。我們刪去v及其關(guān)聯(lián)邊得到新圖T′,根據(jù)歸納假設(shè)T′無圈,再加回v及其關(guān)聯(lián)邊又得到圖T,則T也無圈。其次,若在連通圖T中增加一條新邊(vi,vj),則由于T中由vi到vj存在一條通路,故必有一個(gè)圈通過vi,vj。若這樣的圈有兩個(gè)，則去掉(v

6、i,vj),T中必存在通過vi,vj的圈，與T無圈矛盾。故加上邊(vi,vj)得到一個(gè)切僅一個(gè)圈。(4)證明由第(3)條可推出第(4)條。若圖不連通,則存在兩個(gè)結(jié)點(diǎn)vi和vj,在vi和vj之間沒有路,若加邊(vi,vj)不會(huì)產(chǎn)生簡單回路（圈）,但這與假設(shè)矛盾。由于T無圈,所以刪去任一邊,圖便不連通。(5)證明由第(4)條可推出第(5)條。由連通性知,任兩點(diǎn)間有一條路徑,于是有一條通路。若此通路不唯一,則T中含有簡單回路,刪去此回路上任一邊,圖仍連通,這與假設(shè)不符,所以通路是唯一的。(6)證明由第(5)條可推出

7、樹的定義。顯然連通。若有圈,則圈上任意兩點(diǎn)間有兩條通路,此與通路的唯一性矛盾。證畢。由定理7.5.2所刻畫的樹的特征可見：在結(jié)點(diǎn)數(shù)給定的所有圖中，樹是邊數(shù)最少的連通圖，也是邊數(shù)最多的無圈圖。由此可知，在一個(gè)（n，m）圖G中，若m＜n－1，則G是不連通的；若m＞n－1，則G必定有圈?！纠?.5.2】T是一棵樹,有兩個(gè)2度結(jié)點(diǎn)，一個(gè)3度結(jié)點(diǎn)，三個(gè)4度結(jié)點(diǎn)，T有幾片樹葉？解：設(shè)樹T有x片樹葉，則T的結(jié)點(diǎn)數(shù)n=2+1+3+xT的邊數(shù)m=n-1=5+x又由得2·（5+x）=2·2+3·1+4·3+x所以x=9，即樹T有

8、9片樹葉。7.5.2無向圖中的生成樹與最小生成樹(SpanningTreesandMinimalSpanningTrees)定義7.5.2若無向(連通圖)G的生成子圖是一棵樹，則稱該樹是G的生成樹，記為TG。生成樹TG中的邊稱為樹枝。圖G中其它邊稱為TG的弦。所有這些弦的集合稱為TG的補(bǔ)。如圖7.5.3中(b)、(c)所示的樹T1、T2是(a)圖的生成樹，而(d)所示的樹T3不是(a)圖的生成樹。一