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

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

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

3、性質(zhì)(續(xù)),,,定理2 設T 是 n 階非平凡的無向樹，則T中至少有兩片樹葉. 證 設T有x片樹葉，由握手定理及定理1可知， 由上式解出x?2.,8/60,例1 已知一棵樹有5個4度頂點，3個3度頂點，3個2度頂點，問有幾個一度頂點？,解：設有 x個1度頂點，則依題意有方程：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度頂點各1個, 其余頂點的度數(shù)均為4. 求T的階數(shù)n, 并畫出滿足要求的所有非同構(gòu)的無向樹. 解 設T的階數(shù)為n, 則邊數(shù)為n?1, 4度頂點的個數(shù)為n?7. 由握手定理得 2m=2(n?1)=5?1+2?1+3?1+4(n?7)解出n=8, 4度頂點為1個. T的度數(shù)列為1,1,1,1,1,2,3,4 有3棵非同構(gòu)

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

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

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

8、v3v4v6v3, v4v5v8v7v4, v4v6v7v4, v6v7v8v9v6},17/60,基本割集,設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關于TG的基本割集。 所有的這樣的基本

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

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

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

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

15、,定義1 一個有向圖，若去掉邊的方向，所得無向圖是一棵樹，則稱這個有向圖為有向樹。,29/53,根樹,設T=(V,E)是一棵有向樹，若僅有一個頂點的入度為0，其余的頂點的入度均為1，這樣一棵有向樹我們稱為根樹。入度為0的頂點稱為樹根，出度為0的頂點稱為樹葉，出度不為0的頂點稱為分枝點。,30/53,例 畫出4階所有非同構(gòu)的根樹,樹,根樹,,31/53,家族樹,設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,子樹,設T=(V,E)是一棵根樹。v0?V，v0是 中一個分支點, 所謂以v0為根的子樹是指T的一個子圖T ’，T ’以v0和v0的全部的后代為頂點，以從v0出發(fā)的所有通路經(jīng)過的邊為邊。以v0的一個兒子為根的子樹稱為v0的子樹

17、。,33,根樹的分類,有序樹: 將根樹同層上的頂點規(guī)定次序r元樹:根樹的每個分支點至多有r個兒子r元正則樹: 根樹的每個分支點恰有r個兒子r元有序樹: 有序的r元樹r元正則有序樹: 有序的r元正則樹,34/53,2,3,1,2,3元樹3元有序樹,2元正則樹2元正則有序樹,2元完全正則樹2元完全正則有序樹,35,最優(yōu)2元樹,,定義 設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ù)w1, w2, …, wt, ① 作t片樹葉, 分別以w1, w2, …, wt為權(quán).② 在所有入度為0的頂點(不一定是樹葉)中選出兩個權(quán)最小的頂點, 添加

19、一個新分支點, 以這2個頂點為兒子, 其權(quán)等于這2個兒子的權(quán)之和.③ 重復②, 直到只有1個入度為0 的頂點為止. W(T)等于所有分支點的權(quán)之和,37,實例,例 求帶權(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) 基本割集與基本割