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

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

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

3、性質(zhì)(續(xù)),,,定理2 設(shè)T 是 n 階非平凡的無向樹，則T中至少有兩片樹葉. 證 設(shè)T有x片樹葉，由握手定理及定理1可知， 由上式解出x?2.,8/60,例1 已知一棵樹有5個(gè)4度頂點(diǎn)，3個(gè)3度頂點(diǎn)，3個(gè)2度頂點(diǎ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 已知無向樹T有5片樹葉, 2度與3度頂點(diǎn)各1個(gè), 其余頂點(diǎn)的度數(shù)均為4. 求T的階數(shù)n, 并畫出滿足要求的所有非同構(gòu)的無向樹. 解 設(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、的無向樹,9,10/60,10.2 連通圖的生成樹和帶權(quán)連通圖的最小生成樹,(一) 生成樹(二) 基本圈、基本割集(三) 生成樹與基本圈、基本割集的關(guān)系(四) 最小生成樹(五) 避圈法,11/60,例,假設(shè)有分布在不同建筑物中的5臺計(jì)算機(jī)。計(jì)算機(jī)連接的可能方案如右圖所示。,,這些可能安裝方案都是生成子圖，并具有樹的結(jié)構(gòu)。,12/60,生成樹,定義：設(shè)G=(V,E)是一個(gè)連通圖， G的一個(gè)生成子圖

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

7、0,例1 G若有生成樹，一般不唯一,15/60,生成樹的枝、弦,設(shè)G=(V,E)是一個(gè)圖，TG=(V,D)是G的一棵生成樹。 稱e?D為TG的枝， 稱e?E但e?D為TG的弦。,16/60,基本圈（回路）系統(tǒng),對于生成樹TG的每一個(gè)弦，對應(yīng)于G中的唯一的一個(gè)含且僅含該弦的基本圈。G中由所有弦所分別對應(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)過邊 e的通路}， V2={v?V │v=v0或在 TG中 v與v0之間有不經(jīng)過邊 e的通路}， 則 D’={ {u,v} ?E│u?V1, v?V2}是G的一個(gè)割集。 這樣的割集叫G關(guān)于TG的基本割集。 所有的這樣的基本

9、割集組成了基本割集系統(tǒng)。,18,實(shí)例,例 圖中紅邊為一棵生成樹, 求對應(yīng)它的基本回路系統(tǒng) 與基本割集系統(tǒng)解 弦e,f,g對應(yīng)的基本回路分別為 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基={Ce, Cf, Cg}. 樹枝a,b,c,d對應(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è)有分布在不同建筑物中的5臺計(jì)算機(jī)C1, C2, C3, C4, C5。計(jì)算機(jī)連接的可能方案以及每種連接方式的成本（單位：元）如右圖所示。,左圖是成本最低的安裝方案。,20/60,帶權(quán)圖的最小生成樹,設(shè)G=(V,E, φ)是一個(gè)帶權(quán)連通圖，φ:E→R+，R+ ={x?R│x>0}。 TG

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

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

13、V|-1。若等于|V|-1 ,則終止。否則轉(zhuǎn)向(3)。,24/60,例 求最小生成樹,,,,,,,,,,,25/60,普里姆(Prim)算法,設(shè)置一個(gè)集合T，開始圖上任選一點(diǎn)u0加入T，圖頂點(diǎn)數(shù)為n。重復(fù)以下工作n-1次: 在滿足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,兩種算法的評價(jià),普里姆算法的特點(diǎn)是當(dāng)前形成的集合T始終是一棵樹。它的時(shí)間復(fù)雜度與圖的邊數(shù)無關(guān)，適合于稠密圖。,避圈算法的特點(diǎn)是當(dāng)前形成的集合T除了最后的結(jié)果外，始終不是一個(gè)樹。它的時(shí)間主要取決于邊數(shù)，因此較適合于稀疏圖。,27/53,10.3 有序樹,(一) 有向樹(二) 根樹(三) 有序樹(第i子樹)(四) m-分樹(五) 2-分樹/正則2-分樹,樹根/樹葉/分枝點(diǎn)父親/兒子祖先/后代子樹,28/53,有向樹

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

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

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

18、t, 稱 為T的權(quán), 記作 W(T), 其中l(wèi)(vi)是vi的層數(shù). 在所有有t片樹葉, 帶權(quán) w1, w2, …, wt 的 2元樹中, 權(quán)最小的2元樹稱為最優(yōu) 2元樹.,36,求最優(yōu)樹,Huffman算法:給定實(shí)數(shù)w1, w2, …, wt, ① 作t片樹葉, 分別以w1, w2, …, wt為權(quán).② 在所有入度為0的頂點(diǎn)(不一定是樹葉)中選出兩個(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)樹. 解題過程由下圖給出，W(T)=38,2，2，3，4，5,4，3，4，5,7，4，5,7，9,小結(jié) 樹與有序樹,無向樹及生成樹 （ m=n?1） 基本回路與基本回路系統(tǒng) 基本割集與基本割