離散數(shù)學(xué)特殊圖課件

樹

§.1無向樹及生成樹定義9.1

連通無回路的無向圖稱為無向樹,簡稱樹,常用T表示樹。

(即樹是不包含回路的連通圖)平凡圖稱為平凡樹。若無向圖G至少有兩個連通分支,則稱G為森林。在無向樹中，懸掛頂點稱為樹葉，度數(shù)大于或等于2的頂點稱為分支點。例9.1判斷下列哪些圖是樹？v1v2v3v4v5v1v2v3v4v5v1v2v4v3v5(a)(b)(c)解:圖(a)是樹,因為它連通又不包含回路。圖(b),(c)不是樹,因為圖(b)雖連通但有回路,圖(c)雖無回路但不連通。在圖(a)中,v1、v4、v5為均為葉，v2、v3均為分支節(jié)點。例9.2連通圖、樹和森林之間的相互轉(zhuǎn)換。定理9.1設(shè)G=<V,E>,則下面各命題是等價的：（1）G連通而不含回路（G是樹）。（2）G中每對頂點之間存在唯一的路徑。（3）G中無回路且n=m+1。（4）G是連通的且n=m+1。

(5)G中沒有回路，但在任何兩個不同的頂點之間加一條新邊，在所得的圖中得到唯一的一個含新邊的圈。(6)G是連通的且G中任何邊均為橋。(7)G是連通的,但刪除任何一條邊后，就不連通了。

其中n為G中頂點數(shù)，m為邊數(shù)。以上兩個定理給出了無向樹的主要性質(zhì)，利用這些性質(zhì)和握手定理，可以畫出階數(shù)n比較小的所有非同構(gòu)的無向樹。定理9.2

設(shè)T是n階非平凡的無向樹，則T中至少有兩片樹葉。證

:因為T是非平凡樹,所以T中每個頂點的度數(shù)都大于等于1,設(shè)T有k片樹葉,則有(n-k)個頂點度數(shù)大于等于2,由握手定理及定理9.1可知2m=∑d(vi)≥k+2(n-k)由定理9.1可知,m=n-1,將此結(jié)果代入上式后解得k≥2.例9.3：畫出5階所有非同構(gòu)的無向樹。解：設(shè)Ti為5階無向樹,則Ti的邊數(shù)為4，Ti的度序列之和為8，△(Ti)≤4,

(Ti)≥1,可能的度序列為：(1)1,1,1,1,4(2)1,1,1,2,3(3)1,1,2,2,2。。。。。。。。。。。。。。。稱只有一個分支點且其度數(shù)為n-1的n階無向樹為星形圖，稱唯一的分支點為星心。解：由握手定理2m=∑d(vi)

及定理9.1n=m+1

設(shè)G有n個頂點,則有下列關(guān)系式5x1+3x2+(n-5-3)x3=2x(n-1)

解得：n=11例9.3：無向樹G有5片樹葉，3個2度分支點，其余分支點均為3度，問G有多少個頂點？解：由握手定理2m=∑d(vi)

及定理9.1n=m+1

設(shè)G有t個1頂點,則有下列關(guān)系式2x2+3+4x3+t=2m=2x(n-1)=2x(2+1+3+t-1)

解得：t=9例9.4：無向樹G有2個2度結(jié)點，1個3度結(jié)點，3個4度結(jié)點，則其1度結(jié)點數(shù)為多少？

解：設(shè)G有t個4度分支點,則有下列關(guān)系式8x1+2x3+tx4=2x(8+2+t-1)

解得：t=2

則G中共有12個頂點，11條邊，度數(shù)序列之和為22，△

(Ti)=4,

(Ti)=1,度序列為：1,1,1,1,1,1,1,1,3,3,4,4其非同構(gòu)的圖形為：n例9.5：無向樹G有8片樹葉，2個3度分支點，其余分支點均為4度，問G有多少個4度分支點？畫出其非同構(gòu)的情況。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。其非同構(gòu)的圖形為：圖中，紅色邊表示生成樹，白色邊組成其余樹。可見，余樹可能不連通，也可能含回路。定義9.2設(shè)T是無向圖G的生成子圖并且為樹，則稱T為G的生成樹。

G在T中的邊稱為T的樹枝，G不在T中的邊稱為T的弦。

T的所有弦的集合的導(dǎo)出子圖稱為T的余樹在下圖中，(2)為(1)的一棵生成樹T，(3)為T的余樹，注意：余樹不一定是樹。一個無向連通圖，如果它本身不是樹，它的生成樹是不唯一的。但所有的連通圖都具有生成樹。事實上，若G是連通圖，又G中無回路，則G本身就是樹。abcdeabcdeabcd(1)(2)(3)定理9.3

無向圖G具有生成樹

G是連通圖。推論1設(shè)G是n階m條邊的無向連通圖，則m≥n-1。推論2設(shè)G是n階m條邊的無向連通圖，T為G

的生成樹，則T的余樹T'中含有m-n+1邊(即T'有m-n+1條弦)。定義9.3

設(shè)T是n階m條邊的無向連通圖G的一棵生成樹，設(shè)e1,e2,…,em-n+1為T的弦，設(shè)Cr為T添加弦er產(chǎn)生的G的回路，r=1,2,…,m-n+1。則稱Cr為對應(yīng)于弦er的基本回路，稱{C1,C2,Cm-n+1}為對應(yīng)生成數(shù)T的基本回路系統(tǒng)，abcdef在右圖中,Ca=aed,Cb=dbf,Cc=cef,為對應(yīng)生成樹T的基本回路，{Ca,Cb,Cc}為T的基本回路系統(tǒng)。一個連通圖G對應(yīng)不同的生成樹的基本回路及基本回路系統(tǒng)可能不同，但基本回路的個數(shù)G所固有的參數(shù)(弦)，等于m-n+1定義9.4

設(shè)T是n階連通圖G的一棵生成樹,稱T的n-1個樹枝對應(yīng)的G的n-1個割集（每個割集只含一個樹枝，其余的邊都是弦）S1,S2,

…,Sn-1為對應(yīng)生成樹T的G的基本割集,稱{S1,S2,

…,Sn-1}為對應(yīng)生成樹T的基本割集系統(tǒng)。abcdef在右圖中,T的樹枝d對應(yīng)G的一個割集{d,b,a},e對應(yīng)一個割集{e,a,c},樹枝f對應(yīng)一個割集{f,c,b}。

3個樹枝對應(yīng)的G的割集的特點是：每個割集中只含一個樹枝，其余的邊都是弦。這樣的割集稱為基本割集。

例9.5在右下圖所示的圖G中,實數(shù)邊所構(gòu)成的子圖是G的一棵生成樹T，求T對應(yīng)的基本回路和基本回路系統(tǒng)，基本割集和基本割集系統(tǒng)解:G中頂點數(shù)n=6,邊數(shù)m=9，基本回路個數(shù)為m-n+1=4,即T有4條弦，f,g,h,i。對應(yīng)每條弦有一個基本回路：

Cf=face;Cr=gba;Ch=hdcb;Ci=ied;

基本回路系統(tǒng)為{Cf

,Cr,Ch,Ci

}abcdefghiT有5個樹枝a,b,c,d,e,因而有5個基本割集:Sa={a,g,f};Sb={b,g,h};Sc={c,f,h};Sd={d,i,h};Se={e,f,i}基本割集系統(tǒng)為{Sa,Sb,Sc,Sd,Se}定義9.5

設(shè)無向連通帶權(quán)圖G=<V,E,W>,T是G的一棵生成樹，T的各邊權(quán)之和稱為T的權(quán)，記作W(T)。G的所有生成樹中權(quán)最小的生成樹稱為G的最小生成樹。求最小生成樹的算法很多，我們只介紹避圈法（Kruskal算法）設(shè)n階無向連通帶權(quán)圖G=<V,E,W>有m條邊,不妨設(shè)G中無環(huán)(否則可先刪去)，算法為：將m條邊按權(quán)從小到大順序排列，設(shè)為e1,e2,…,em。(2)取e1在T中，然后依次檢查e2,…,em，若ej

(j=2,3,…,m)與T中的邊不能構(gòu)成回路，則取ej在T中，否則放棄ej，考慮下一條邊，直至j>m。(3)算法停止時得到的T為G的最小生成樹。Kruskal算法—一種求最小生成樹的算法例9.6用避圈法求下圖所示的最小生成樹abcdef5555136642解:W(T)=1+2+3+4+5=15注意：最小生成樹的結(jié)點數(shù)與原圖相等，邊的數(shù)目比原圖少。bacd762fe81443472356321hg避圈法Kruskal(克魯斯卡爾算法)例9.7：鋪設(shè)一個連接各個城市的光纖通信網(wǎng)絡(luò)febacd546036388404820452815383062251210hg例9.8：鋪設(shè)一個連接各個城市的光纖通信網(wǎng)絡(luò)。（單位：萬元）2121343151131。。。。。OK!例9.9：用Kruskal算法求下圖的最小生成樹。。。。。。。。214515545332例9.10：用Kruskal算法求下圖的最小生成樹。。。。。。。。214515545332W(T)=1+1+2+3+2+5=14W(T)=1+1+2+3+2+5=14破圈法上述算法是貪婪地增加不構(gòu)成回路的邊，以求得最小生成樹(最優(yōu)樹)，所以通常稱為“避圈法”；我們還可以從另一個角度來考慮最小成樹(最優(yōu)樹)問題，由G的圈（回路）最優(yōu)條件，我們也可以在原連通權(quán)圖G中逐步刪除構(gòu)成回路中權(quán)最大的邊，最后剩下的無回路的生成子圖為最小成樹(最優(yōu)樹)。我們把這種方法稱為“破圈法”。例9.11在圖(a)中給出了一個連通圖,求此圖的生成樹(a)214356787864例9.12用“破圈法”求其最優(yōu)樹的過程。設(shè)D是有向圖,如果略去有向邊的方向所得無向圖為一棵無向樹,則稱D為有向樹。其中根樹最為重要。定義9.6

設(shè)T是n(n≥2)階有向樹，若T中有一個頂點的入度為0，其余的頂點的入度均為1，則稱T為根樹，入度為0的頂點稱為樹根，入度為1出度為0的頂點稱為樹葉，入度為1出度不為0的頂點稱為內(nèi)點，內(nèi)點和樹根統(tǒng)稱為分支點，§9.2根樹及其應(yīng)用(1)(2)v0v1v2v3v4v5v6v7v0v1v2v3v4v5v6v7例9.13下圖(1)為一棵根樹。V0為樹根,v1,v4,v3,v6,v7為樹葉,v2,v5為內(nèi)點,v0,v2,v5為均為分支點,由于在根樹中有向邊的方向均一致,故可省掉其方向,如圖(2)(1)(2)v0v1v2v3v4v5v6v7v0v1v2v3v4v5v6v7從樹根到T的任意頂點v的通路（路徑）長度稱為v的層數(shù)，層數(shù)最大頂點的層數(shù)稱為樹高平凡樹也稱為根樹。例9.14下圖(1)中,v1,v2,v3,在第一層上，v4,v5

在第二層上，v6,v7在第三層上。樹高為3。定義9.7設(shè)T為一棵根樹，a為T中的一個頂點，且a不是樹根，稱a及其后代導(dǎo)出的子圖T'為T的以a為根的子樹，簡稱根子樹。。。。。。。。。。如圖所示，由于各有向邊的方向一致，故常省略，并且樹根在最上方。a定義9.8設(shè)T為根樹，若將T中層數(shù)相同的頂點都標(biāo)定次序，則稱T為有序樹根據(jù)根樹T中每個分支點兒子數(shù)以及是否有序，可以將根樹分成下列各類；定義9.9設(shè)T為一棵根樹①若T的每個分支點至多有r個兒子,則稱T為r元樹(r叉樹)；

②若T的每個分支點都恰好有r個兒子,則稱它為r元正則樹。③若r元樹T是有序的,則稱T為r元有序樹④若r元正則樹T是有序的，則稱T為r元正則有序樹。⑤若T是r元正則樹，且所有樹葉的層數(shù)相同，則稱T為r元完全正則樹⑥若r元完全正則樹T是有序樹，則稱T是

r元有序完全正則樹。。。。。。。。。。。。。。。。。二元(叉)樹二元(叉)正則樹二元(叉)完全正則樹在所有的r元有序正則樹中，2元有序正則樹最重要。例9.15例9.16：求2元樹T的權(quán)。。。。。。。。。。32335解:W(T)=3×2+2×2+3×3+5×3+3×2=40是不是最優(yōu)2元樹呢？？？定義9.9設(shè)2元樹T有t片樹葉，v1,v2,…,vt,權(quán)分別為w1,w2,…,wt，稱

W(t)=

為T的權(quán)，其中L(vi)是vi的層數(shù)，在所有有t片樹葉，帶權(quán)w1,w2,…,wt的2元樹中，權(quán)最小的2元樹稱為最優(yōu)2元樹。例:9.17在下圖所示的三棵樹中,都是帶權(quán)1,3,4,5,6的二元樹,W(T1)=47,W(T2)=54,W(T3)=42,但它們中有無最優(yōu)2元樹

還不知道T1T2T3451633456113645用此算法求上例的最優(yōu)二叉樹。給定實數(shù)w1,w2,…,wt,且w1≤w2≤…≤wt（1）連接權(quán)為w1,w2的兩片樹葉,得一個分支點其權(quán)為w1+w2。（2）在w1+w2,w3,…,wt中選出兩個最小的權(quán),連接它們對應(yīng)的頂點(不一定是樹葉),得新分支點及所帶的權(quán)。（3）重復(fù)(2),直到形成t-1個分支點,t片樹葉為止。Huffman算法——一種求最優(yōu)二叉樹的算法例:9.18求帶權(quán)1,3,4,5,6的最優(yōu)二元樹。4481338431134564411561481119①連接權(quán)為w1,w2的兩片樹葉,得一個分支點其權(quán)為w1+w2

②在w1+w2,w3,…,wt中選出兩個最小的權(quán),連接它們對應(yīng)的頂點(不一定是樹葉),得分支點及所帶的權(quán)③重復(fù)②,直到形成t-1個分支點,t片樹葉為止(若得到的權(quán)比后續(xù)的兩個權(quán)大,則另開分支)。。。437(1)(2)(3)(4)例:9.19求帶權(quán)3,4,5,6,12的最優(yōu)二元樹。解：共分為四個步驟：34756116543711183456711181230例:9.20求帶權(quán)2,4,7,8,10,12的最優(yōu)二元樹。這棵最優(yōu)樹的權(quán)為:2*4+4*4+7*3+12*2+8*2+10*2=105一般來說,帶權(quán)w1,w2,,wn的最優(yōu)樹不一定是唯一的最優(yōu)二叉樹在通信編碼中的應(yīng)用定義9.11

設(shè)=12…

n-1n為長為n的符號串,稱其子串1,

12,…,12…

n-1

分別為該符號串的長度為1,2,…

n-1的前綴,

設(shè)B={β1,β2,…,βm}

為一個符號串集合,若對于任意的βi,

βj∈B,i≠j,βi,

βj

互不為前綴,則稱B為前綴碼,

若符號串中βi(i=1,2,…,m)只出現(xiàn)0,1兩個符號,則稱B為二元前綴碼。那么：{00,01,100,1010,1011,11111}{abc,cba,bca,bac,acb,cab}{1,00,011,01001,01000}是(二元)前綴碼嗎？如何產(chǎn)生二元前綴碼呢？如：{0,10,110,1111}{1,01,001,0001}等是(二元)前綴碼而{1,11,101,001,0011}

不是(二元)前綴碼給定一棵2叉樹T，設(shè)它有t片樹葉。設(shè)v為T的一個分支點，則v至少有一個兒子，最多有兩個兒子。若v有兩個兒子，在由v引出的兩條邊上，左邊的標(biāo)上0，右邊的標(biāo)上1；若v有一個兒子，在由v引出的邊上可標(biāo)上0，也可標(biāo)上1。設(shè)vi為T的任一片樹葉，從樹根到vi的通路上各邊的標(biāo)號組成的0，1串組成的符號串放在vi處，t片樹葉處的t個符號串組成的集合為一個二元前綴碼。用二叉樹產(chǎn)生二元前綴碼之做法由上面做法知，vi處的符號串的前綴均在vi所在的通路上除vi外的頂點處達(dá)到，因而所得符號串集合為二元前綴碼。若T存在單子分支點，則由T產(chǎn)生的前綴碼可能不唯一。若T為正則2叉樹,則由T產(chǎn)生的前綴碼唯一010110101000100010101111例9.21

右圖所示的二元樹產(chǎn)生的前綴嗎為{11,00,011,0100,0101}由一棵給定的2叉正則樹，可以產(chǎn)生唯一的一個二元前綴碼。。。。。。。。。。01000111

例9.22

右圖所示的是一棵2叉正則樹,它產(chǎn)生唯一的一個二元前綴碼是{000,001,01,10,11}。〖提示〗把各字符看作為樹葉,各字符出現(xiàn)的頻率(或n倍的頻率)作為其相應(yīng)的權(quán),利用Huffman算法求出最優(yōu)2叉樹,由此產(chǎn)生的前綴碼即為最佳前綴碼。

利用Huffman算法求出的最優(yōu)2叉樹產(chǎn)生的前綴碼稱為最佳前綴碼。例9.23在通信中,0,1,2,3,4,5,6,7出現(xiàn)的頻率如下0：30％,1：20％,2：15％3：10％,4：10％,5：5％6：5％,7：5％求傳輸它們的最佳前綴碼

例9.24在通信中,0,1,2,3,4,5,6,7出現(xiàn)的頻率如下0：30％,1：20％,2：15％3：10％,4：10％,5：5％6：5％,7：5％求傳輸它們的最佳前綴碼100604030302020151510555010101010101101001000000000100010011001011101解:將各字符出現(xiàn)的頻率作為其相應(yīng)的權(quán)1=5,2=5,3=5,4=10,5=10,6=15,7=20,8=30為8個權(quán),利用Huffman算法求出的最優(yōu)2叉樹如圖所示(碼長取3,如101傳5)

例9.24在通信中,0,1,2,3,4,5,6,7出現(xiàn)的頻率如下0:30％,1:20％,2:15％,3:10％,4:10％5:5％,6:5％,7:5％求傳輸它們的最佳前綴碼1006040303020201515105550101010101011010010000000001000100110