《離散數(shù)學(xué)課件》5樹(shù)

1、第10章 樹(shù)與有序樹(shù),9.1 無(wú)向樹(shù)及生成樹(shù)9.2 根樹(shù)及其應(yīng)用,1,2/60,第十章 樹(shù)與有序樹(shù),10.1 樹(shù)的基本概念(一) 樹(shù)的定義(二) 樹(shù)的等價(jià)定義,3/60,例,,4,無(wú)向樹(shù),無(wú)向樹(shù): 連通無(wú)回路的無(wú)向圖平凡樹(shù): 平凡圖森林: 每個(gè)連通分支都是樹(shù)的非連通的無(wú)向圖樹(shù)葉: 樹(shù)中度數(shù)為1的頂點(diǎn)分支點(diǎn): 樹(shù)中度數(shù)?2的頂點(diǎn)右圖為一棵12階樹(shù).聲明:本章中所討論的回路均 指簡(jiǎn)單回路或

2、初級(jí)回路,,5/60,例 是否為樹(shù)?,,,,,,,,例 畫(huà)出所有5個(gè)頂點(diǎn)的樹(shù),6,無(wú)向樹(shù)的性質(zhì),定理1 設(shè)G=是n階m條邊的無(wú)向圖，則下面各命題是等價(jià)的：（1）G是樹(shù)(連通無(wú)回路);（2）G中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑;（3）G中無(wú)回路且m=n?1;（4）G是連通的且m=n?1;（5）G是連通的且G中任何邊均為橋;（6）G中沒(méi)有回路, 但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊后所得圖中有惟一的一個(gè)含新邊的圈.,7,無(wú)向樹(shù)的

3、性質(zhì)(續(xù)),,,定理2 設(shè)T 是 n 階非平凡的無(wú)向樹(shù)，則T中至少有兩片樹(shù)葉. 證 設(shè)T有x片樹(shù)葉，由握手定理及定理1可知， 由上式解出x?2.,8/60,例1 已知一棵樹(shù)有5個(gè)4度頂點(diǎn)，3個(gè)3度頂點(diǎn)，3個(gè)2度頂點(diǎn)，問(wèn)有幾個(gè)一度頂點(diǎn)？,解：設(shè)有 x個(gè)1度頂點(diǎn)，則依題意有方程：5?4+3?3+3?2+1?x = ∑ d(v) =2|E| =2(|V|-1) =2(5+

4、3+3+x-1) ∴ x=15,例2 已知無(wú)向樹(shù)T有5片樹(shù)葉, 2度與3度頂點(diǎn)各1個(gè), 其余頂點(diǎn)的度數(shù)均為4. 求T的階數(shù)n, 并畫(huà)出滿(mǎn)足要求的所有非同構(gòu)的無(wú)向樹(shù). 解 設(shè)T的階數(shù)為n, 則邊數(shù)為n?1, 4度頂點(diǎn)的個(gè)數(shù)為n?7. 由握手定理得 2m=2(n?1)=5?1+2?1+3?1+4(n?7)解出n=8, 4度頂點(diǎn)為1個(gè). T的度數(shù)列為1,1,1,1,1,2,3,4 有3棵非同構(gòu)

5、的無(wú)向樹(shù),9,10/60,10.2 連通圖的生成樹(shù)和帶權(quán)連通圖的最小生成樹(shù),(一) 生成樹(shù)(二) 基本圈、基本割集(三) 生成樹(shù)與基本圈、基本割集的關(guān)系(四) 最小生成樹(shù)(五) 避圈法,11/60,例,假設(shè)有分布在不同建筑物中的5臺(tái)計(jì)算機(jī)。計(jì)算機(jī)連接的可能方案如右圖所示。,,這些可能安裝方案都是生成子圖，并具有樹(shù)的結(jié)構(gòu)。,12/60,生成樹(shù),定義：設(shè)G=(V,E)是一個(gè)連通圖， G的一個(gè)生成子圖

6、若本身是一棵樹(shù)， 稱(chēng)它為G的一棵生成樹(shù)。,13/60,定理1 任何連通圖都有生成樹(shù)。,證明：設(shè)G=(V,E)是一個(gè)簡(jiǎn)單連通圖. 若G中無(wú)圈，則G 本身是G的一棵生成樹(shù)。 若G中有圈，拿去圈中一條邊，原圖仍連通。若再有圈，再拿去圈中一條邊，直到G中無(wú)圈為止。因?yàn)镚中頂點(diǎn)與邊均為有限數(shù)，故上述工作一定可以在有限步內(nèi)結(jié)束。 G的這個(gè)無(wú)圈的連通子圖就是G中一顆生成樹(shù)。,14/6

7、0,例1 G若有生成樹(shù)，一般不唯一,15/60,生成樹(shù)的枝、弦,設(shè)G=(V,E)是一個(gè)圖，TG=(V,D)是G的一棵生成樹(shù)。 稱(chēng)e?D為T(mén)G的枝， 稱(chēng)e?E但e?D為T(mén)G的弦。,16/60,基本圈（回路）系統(tǒng),對(duì)于生成樹(shù)TG的每一個(gè)弦，對(duì)應(yīng)于G中的唯一的一個(gè)含且僅含該弦的基本圈。G中由所有弦所分別對(duì)應(yīng)的基本圈組成了G關(guān)于TG的基本圈系統(tǒng)。,{ v0v1v2v1, v1v3v4v2v1, v1v4v2v1, v2v4v5v2,

8、v3v4v6v3, v4v5v8v7v4, v4v6v7v4, v6v7v8v9v6},17/60,基本割集,設(shè)e={u0,v0} ?D是TG的枝。令V1={v?V │v=u0或在 TG中 v與u0之間有不經(jīng)過(guò)邊 e的通路}， V2={v?V │v=v0或在 TG中 v與v0之間有不經(jīng)過(guò)邊 e的通路}， 則 D’={ {u,v} ?E│u?V1, v?V2}是G的一個(gè)割集。 這樣的割集叫G關(guān)于TG的基本割集。 所有的這樣的基本

9、割集組成了基本割集系統(tǒng)。,18,實(shí)例,例 圖中紅邊為一棵生成樹(shù), 求對(duì)應(yīng)它的基本回路系統(tǒng) 與基本割集系統(tǒng)解 弦e,f,g對(duì)應(yīng)的基本回路分別為 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基={Ce, Cf, Cg}. 樹(shù)枝a,b,c,d對(duì)應(yīng)的基本割集分別為 Sa={a, f, g}, Sb={b, e, f, g}, Sc={c, e,

10、f g}, Sd={d, g}, S基={Sa, Sb, Sc, Sd}.,,19/60,帶權(quán)圖的最小生成樹(shù),例 假設(shè)有分布在不同建筑物中的5臺(tái)計(jì)算機(jī)C1, C2, C3, C4, C5。計(jì)算機(jī)連接的可能方案以及每種連接方式的成本（單位：元）如右圖所示。,左圖是成本最低的安裝方案。,20/60,帶權(quán)圖的最小生成樹(shù),設(shè)G=(V,E, φ)是一個(gè)帶權(quán)連通圖，φ:E→R+，R+ ={x?R│x>0}。 TG

11、=(V,D)是G中一棵生成樹(shù)，可定義TG的權(quán)值如下： φ(TG) = ∑ φ(e),e?D,如何在一個(gè)給定的帶權(quán)圖中求出權(quán)值最小的生成樹(shù)？,21/60,帶權(quán)圖的最小生成樹(shù),避圈算法(Kruskal)普里姆(Prim)算法,避圈算法的指導(dǎo)思想,G中任何一個(gè)圈中權(quán)值最大的邊不是最小生成樹(shù)的枝。,如果圈中權(quán)值最大的邊e是最小生成樹(shù)的枝，由e可以得到一個(gè)割集，該圈與該割集必有另一條公共邊e’，其權(quán)值小一些。將e’替換e即

12、可以得到更小的生成樹(shù)。,23/60,避圈算法步驟,(1) 把G中的邊按權(quán)值大小排序。設(shè)有m條邊e1,e2,…,em，它們的權(quán)值分別為a1,a2,…,am，不妨設(shè)a1≤a2≤??≤am。(2) 按邊的權(quán)值大小次序，從最小邊開(kāi)始，畫(huà)上權(quán)值最小的邊（即取e1）為生成樹(shù)的枝。(3) 設(shè)e是未被考察的邊中權(quán)值最小的邊，若把e畫(huà)上作為生成樹(shù)的枝，所得子圖不產(chǎn)生圈，則選e為生成樹(shù)的枝，否則不把e畫(huà)上。(4) 看選上作為生成樹(shù)的邊的條數(shù)是否等于|

13、V|-1。若等于|V|-1 ,則終止。否則轉(zhuǎn)向(3)。,24/60,例 求最小生成樹(shù),,,,,,,,,,,25/60,普里姆(Prim)算法,設(shè)置一個(gè)集合T，開(kāi)始圖上任選一點(diǎn)u0加入T，圖頂點(diǎn)數(shù)為n。重復(fù)以下工作n-1次: 在滿(mǎn)足u?T,v?T的所有邊中選邊權(quán)w最小的 將v加入集合T中 輸出邊u ,v及邊上的權(quán) w,A,B,,D,C,E,F,,,,,1,5,3,4,2,B,3,,E,5,,C,1,,A,4,,F,2,,D,26/6

14、0,兩種算法的評(píng)價(jià),普里姆算法的特點(diǎn)是當(dāng)前形成的集合T始終是一棵樹(shù)。它的時(shí)間復(fù)雜度與圖的邊數(shù)無(wú)關(guān)，適合于稠密圖。,避圈算法的特點(diǎn)是當(dāng)前形成的集合T除了最后的結(jié)果外，始終不是一個(gè)樹(shù)。它的時(shí)間主要取決于邊數(shù)，因此較適合于稀疏圖。,27/53,10.3 有序樹(shù),(一) 有向樹(shù)(二) 根樹(shù)(三) 有序樹(shù)(第i子樹(shù))(四) m-分樹(shù)(五) 2-分樹(shù)/正則2-分樹(shù),樹(shù)根/樹(shù)葉/分枝點(diǎn)父親/兒子祖先/后代子樹(shù),28/53,有向樹(shù)

15、,定義1 一個(gè)有向圖，若去掉邊的方向，所得無(wú)向圖是一棵樹(shù)，則稱(chēng)這個(gè)有向圖為有向樹(shù)。,29/53,根樹(shù),設(shè)T=(V,E)是一棵有向樹(shù)，若僅有一個(gè)頂點(diǎn)的入度為0，其余的頂點(diǎn)的入度均為1，這樣一棵有向樹(shù)我們稱(chēng)為根樹(shù)。入度為0的頂點(diǎn)稱(chēng)為樹(shù)根，出度為0的頂點(diǎn)稱(chēng)為樹(shù)葉，出度不為0的頂點(diǎn)稱(chēng)為分枝點(diǎn)。,30/53,例 畫(huà)出4階所有非同構(gòu)的根樹(shù),樹(shù),根樹(shù),,31/53,家族樹(shù),設(shè)T=(V,E)是一棵根樹(shù)，將其看做看做家族樹(shù)如果e=(v,u)

16、 ?E，稱(chēng)v是u的父親， u是v的兒子。對(duì)v1,v2?V，若存在一條從v1到v2的通路，則稱(chēng)v1是 v2的祖先，v2是v1的后代。若(v0，v1)，(v0，v2) ?E ，說(shuō)v1與v2是兄弟。,32/53,子樹(shù),設(shè)T=(V,E)是一棵根樹(shù)。v0?V，v0是 中一個(gè)分支點(diǎn), 所謂以v0為根的子樹(shù)是指T的一個(gè)子圖T ’，T ’以v0和v0的全部的后代為頂點(diǎn)，以從v0出發(fā)的所有通路經(jīng)過(guò)的邊為邊。以v0的一個(gè)兒子為根的子樹(shù)稱(chēng)為v0的子樹(shù)

17、。,33,根樹(shù)的分類(lèi),有序樹(shù): 將根樹(shù)同層上的頂點(diǎn)規(guī)定次序r元樹(shù):根樹(shù)的每個(gè)分支點(diǎn)至多有r個(gè)兒子r元正則樹(shù): 根樹(shù)的每個(gè)分支點(diǎn)恰有r個(gè)兒子r元有序樹(shù): 有序的r元樹(shù)r元正則有序樹(shù): 有序的r元正則樹(shù),34/53,2,3,1,2,3元樹(shù)3元有序樹(shù),2元正則樹(shù)2元正則有序樹(shù),2元完全正則樹(shù)2元完全正則有序樹(shù),35,最優(yōu)2元樹(shù),,定義 設(shè)2元樹(shù)T有t片樹(shù)葉v1, v2, …, vt, 樹(shù)葉的權(quán)分別 為w1, w2, …, w

18、t, 稱(chēng) 為T(mén)的權(quán), 記作 W(T), 其中l(wèi)(vi)是vi的層數(shù). 在所有有t片樹(shù)葉, 帶權(quán) w1, w2, …, wt 的 2元樹(shù)中, 權(quán)最小的2元樹(shù)稱(chēng)為最優(yōu) 2元樹(shù).,36,求最優(yōu)樹(shù),Huffman算法:給定實(shí)數(shù)w1, w2, …, wt, ① 作t片樹(shù)葉, 分別以w1, w2, …, wt為權(quán).② 在所有入度為0的頂點(diǎn)(不一定是樹(shù)葉)中選出兩個(gè)權(quán)最小的頂點(diǎn), 添加

19、一個(gè)新分支點(diǎn), 以這2個(gè)頂點(diǎn)為兒子, 其權(quán)等于這2個(gè)兒子的權(quán)之和.③ 重復(fù)②, 直到只有1個(gè)入度為0 的頂點(diǎn)為止. W(T)等于所有分支點(diǎn)的權(quán)之和,37,實(shí)例,例 求帶權(quán)為1, 1, 2, 3, 4, 5的最優(yōu)樹(shù). 解題過(guò)程由下圖給出，W(T)=38,2，2，3，4，5,4，3，4，5,7，4，5,7，9,小結(jié) 樹(shù)與有序樹(shù),無(wú)向樹(shù)及生成樹(shù) （ m=n?1） 基本回路與基本回路系統(tǒng) 基本割集與基本割