離散數(shù)學-樹解讀課件

1第7章樹7.1無向樹及生成樹7.2根樹及其應用1第7章樹7.1無向樹及生成樹27.1無向樹及生成樹

無向樹與森林生成樹與余樹基本回路與基本回路系統(tǒng)基本割集與基本割集系統(tǒng)最小生成樹與避圈法27.1無向樹及生成樹無向樹與森林3無向樹無向樹:無回路的連通無向圖平凡樹:平凡圖森林:每個連通分支都是樹的非連通的無向圖樹葉:樹中度數(shù)為1的頂點分支點:樹中度數(shù)

2的頂點右圖為一棵12階樹.注:本章中所討論的回路均指簡單回路或初級回路3無向樹無向樹:無回路的連通無向圖樹的應用英國數(shù)學家凱萊(ArthurCayley)于19世紀中葉研究飽和碳氫化合物CnH2n+2的同分異構體時提出樹的概念.當n=1,2,3時,都只有一棵非同構的樹;當n=4時,有2棵不同構的樹.4甲烷乙烷丙烷丁烷異丁烷樹的應用英國數(shù)學家凱萊(ArthurCayley)于19世5無向樹的性質定理設G=<V,E>是n階m條邊的無向圖,則下面各命題是等價的：(1)G是樹(連通無回路);(2)G中任意兩個頂點之間存在惟一的路徑;(3)G中無回路且m=n

1;(4)G是連通的且m=n

1;(5)G是連通的且G中任何邊均為橋;(6)G中沒有回路,但在任何兩個不同的頂點之間加一條新邊后所得圖中有惟一的一個含新邊的圈.5無向樹的性質定理設G=<V,E>是n階m條邊的無向圖,6無向樹的性質(續(xù))

定理

設T是n階非平凡的無向樹，則T中至少有兩片樹葉.證設T有x片樹葉,由握手定理及前面的定理，

2(n-1)

x+2(n-x)

解得x

2.6無向樹的性質(續(xù))定理設T是n階非平凡的無向樹，7例題例1已知無向樹T中,有1個3度頂點,2個2度頂點,其余頂點全是樹葉.試求樹葉數(shù),并畫出滿足要求的非同構的無向樹.解用樹的性質m=n

1和握手定理.

設有x片樹葉，于是n=1+2+x=3+x,2m=2

(2+x)=1

3+2

2+x解得x=3，故T有3片樹葉.T的度數(shù)列為1,1,1,2,2,3有2棵非同構的無向樹.7例題例1已知無向樹T中,有1個3度頂點,2個2度頂點8例題例2已知無向樹T有5片樹葉,2度與3度頂點各1個,其余頂點的度數(shù)均為4.求T的階數(shù)n,并畫出滿足要求的所有非同構的無向樹.解設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棵非同構的無向樹8例題例2已知無向樹T有5片樹葉,2度與3度頂點各1個,9生成樹

設G為無向連通圖G的生成樹:G的生成子圖并且是樹生成樹T的樹枝:G在T中的邊生成樹T的弦:G不在T中的邊生成樹T的余樹:所有弦的集合的導出子圖注意：不一定連通,也不一定不含回路.黑邊構成生成樹紅邊構成余樹9生成樹設G為無向連通圖10生成樹的存在性

定理

任何無向連通圖都有生成樹.證用破圈法.若圖中無圈,則圖本身就是自己的生成樹.

否則刪去圈上的任一條邊,這不破壞連通性,重復進行直到無圈為止,剩下的圖是一棵生成樹.推論

設n階無向連通圖有m條邊,則m

n

1.10生成樹的存在性定理任何無向連通圖都有生成樹.11基本回路與基本回路系統(tǒng)

定義設T是連通圖G的一棵生成樹,對每一條弦e,存在惟一的由弦e和T的樹枝構成的初級回路Ce,稱Ce為對應于弦e的基本回路.稱所有基本回路的集合為對應生成樹T的基本回路系統(tǒng).求基本回路的算法:設弦e=(u,v),先求T中u到v的路徑

uv,再加上弦e.例如Ce=e

b

c,Cf=f

a

b

c,Cg=g

a

b

c

d,

C基={Ce,Cf,Cg}.11基本回路與基本回路系統(tǒng)定義設T是連通圖G的一棵生成樹,12基本割集與基本割集系統(tǒng)

定義設T是連通圖G的一棵生成樹,對T的每一條樹枝a,存在惟一的由樹枝a,其余的邊都是弦的割集Sa,稱Sa為對應樹枝a的基本割集，稱所有基本割集的集合為對應生成樹T的基本割集系統(tǒng).求基本割集的算法:設a為生成樹T的樹枝,T

a由兩棵子樹T1與T2組成,則

Sa={e|e

E(G)且e的兩個端點分別屬于T1與T2}.例如Sa={a,f,g},Sb={b,e,f,g},

Sc={c,e,f

g},Sd={d,g},

S基={Sa,Sb,Sc,Sd}.12基本割集與基本割集系統(tǒng)定義設T是連通圖G的一棵生成樹,回路合并合并回路C1和C2(C1

C2):C1

C2是C1和C2上的邊的對稱差構成的(一條或幾條)回路.13

回路合并合并回路C1和C2(C1C2):C1C2是C1基本回路的性質連通圖中的任一條回路都可以表成對應它所含弦的基本回路的合并.例如,abcf=Cf

aef=Ce

Cf

aedg=Ce

Cg

bcdgfe=Ce

Cf

Cg

14基本回路的性質連通圖中的任一條回路都可以表成對應它所含弦的基基本割集的性質連通圖中的任一割集都可以表成對應它所含樹枝的基本割集的對稱差.例如

{g,d}=Sd

{a,b,e}=Sa

Sb

{a,e,c}=Sa

Sc

{b,e,f,d}=Sb

Sd

15基本割集的性質連通圖中的任一割集都可以表成對應它所含樹枝的基16無向圖與最小生成樹

對無向圖或有向圖的每一條邊e附加一個實數(shù)w(e),稱作邊e的權.圖連同附加在邊上的權稱作帶權圖,記作G=<V,E,W>.設T是G的生成樹,T所有邊的權的和稱作T的權,記作W(T).

最小生成樹:帶權圖權最小的生成樹避圈法(Kruskal)——求最小生成樹的算法設G是n階無向連通帶權圖G.(1)按權從小到大排列邊(環(huán)除外),設W(e1)≤W(e2)≤…≤W(em).(2)令T

,i

1,k

0.(3)若ei與T中的邊不構成回路，則令T

T

{ei},k

k+1.(4)若k<n-1,則令i

i+1,轉(3).16無向圖與最小生成樹對無向圖或有向圖的每一條邊e附加一個17例求圖的一棵最小生成樹

w(T)=38實例17例求圖的一棵最小生成樹w(T)=38實例187.2根樹及其應用有向樹與根樹家族樹與根子樹有序樹根樹與有序樹的分類r叉(有序)樹,r叉正則(有序)樹,r叉完全正則(有序)樹最優(yōu)2叉樹與Huffman算法前綴碼與最佳前綴碼中序行遍法、前序行遍法、后序行遍法波蘭符號法與逆波蘭符號法187.2根樹及其應用有向樹與根樹19有向樹與根樹

有向樹:基圖為無向樹的有向圖根樹:有一個頂點入度為0,其余的入度均為1的非平凡的有向樹樹根:有向樹中入度為0的頂點樹葉:有向樹中入度為1,出度為0的頂點內點:有向樹中入度為1,出度大于0的頂點分支點:樹根與內點的總稱頂點v的層數(shù):從樹根到v的通路長度樹高:有向樹中頂點的最大層數(shù)19有向樹與根樹有向樹:基圖為無向樹的有向圖20根樹(續(xù))根樹的畫法:樹根放上方,省去所有有向邊上的箭頭如右圖所示

a是樹根

b,e,f,h,i是樹葉

c,d,g是內點

a,c,d,g是分支點

a為0層;1層有b,c;2層有d,e,f;3層有g,h;4層有i.

樹高為420根樹(續(xù))根樹的畫法:樹根放上方,省去所有有向邊上的箭頭21家族樹定義把根樹看作一棵家族樹:(1)若頂點a鄰接到頂點b,則稱b是a的兒子,a是

b的父親;(2)若b和c為同一個頂點的兒子,則稱b和c是兄弟;(3)若a

b且a可達b,則稱a是b的祖先,b是a的后代.設v為根樹的一個頂點且不是樹根,稱v及其所有后代的導出子圖為以v為根的根子樹.21家族樹定義把根樹看作一棵家族樹:22根樹的分類有序樹:將根樹同層上的頂點規(guī)定次序r叉樹:根樹的每個分支點至多有r個兒子r叉正則樹:根樹的每個分支點恰有r個兒子r叉完全正則樹:樹葉層數(shù)相同的r元正則樹r叉有序樹:有序的r叉樹r叉正則有序樹:有序的r叉正則樹r叉完全正則有序樹:有序的r叉完全正則樹22根樹的分類有序樹:將根樹同層上的頂點規(guī)定次序23最優(yōu)2叉樹

定義設2叉樹T有t片樹葉v1,v2,…,vt,樹葉的權分別為w1,w2,…,wt,稱為T的權,其中

l(vi)是vi的層數(shù).在所有權為w1,w2,…,wt的t片樹葉的2叉樹中,權最小的2叉樹稱為最優(yōu)2叉樹.例如W(T1)=47W(T2)=54W(T3)=4223最優(yōu)2叉樹定義設2叉樹T有t片樹葉v1,v2,…24求最優(yōu)2叉樹的算法

Huffman算法:給定實數(shù)w1,w2,…,wt,①作t片樹葉,分別以w1,w2,…,wt為權.②在所有入度為0的頂點(不一定是樹葉)中選出兩個權最小的頂點,添加一個新分支點,以這2個頂點為兒子,其權等于這2個兒子的權之和.③重復②,直到只有1個入度為0的頂點為止.

W(T)等于所有分支點的權之和24求最優(yōu)2叉樹的算法Huffman算法:25實例例求權為1,3,4,5,6的最優(yōu)樹.25實例例求權為1,3,4,5,6的最優(yōu)樹.26實例例(續(xù))

W(T)=42,前面的T3也是最優(yōu)的.26實例例(續(xù))27前綴碼

設

=

1

2…

n-1

n是長度為n的符號串

的前綴:

1

2…

k

,k=1,2,…,n-1,n

前綴碼:{

1,

2,…,

m},其中

1,

2,…,

m為非空字符串,且任何兩個互不為前綴2元前綴碼:只有兩個符號(如0與1)的前綴碼如{0,10,110,1111},{10,01,001,110}是2元前綴碼

{0,10,010,1010}不是前綴碼27前綴碼設=12…n-1n是長度為n的符號串28前綴碼(續(xù))一棵2叉樹產生一個二元前綴碼:對每個分支點,若關聯(lián)2條邊,則給左邊標0,右邊標1;若只關聯(lián)1條邊,則可以給它標0(看作左邊),也可以標1(看作右邊).將從樹根到每一片樹葉的通路上標的數(shù)字組成的字符串記在樹葉處,所得的字符串構成一個前綴碼.例如28前綴碼(續(xù))一棵2叉樹產生一個二元前綴碼:最佳前綴碼設要傳輸?shù)碾娢闹泻衪個字符,字符ai出現(xiàn)的頻率為pi,它的編碼的長度為li,那么100個字符的電文的編碼的期望長度是100.稱編碼期望長度最小的2元前綴碼為最佳2元前綴碼.在用2叉樹產生2元前綴碼時,每個二進制串的長度等于它所在樹葉的深度,因而權為100p1,100p2,

,100pt的最優(yōu)2叉樹產生的2元前綴碼是最佳2元前綴碼.于是,給定字符出現(xiàn)的頻率,可以用Huffman算法產生最佳2元前綴碼.29最佳前綴碼設要傳輸?shù)碾娢闹泻衪個字符,字符ai出現(xiàn)的頻率30實例例在通信中，設八進制數(shù)字出現(xiàn)的頻率如下：

0：25%1：20%2：15%3：10%4：10%5：10%6：5%7：5%采用2元前綴碼,求傳輸數(shù)字最少的2元前綴碼,并求傳輸10n(n

2)個按上述比例出現(xiàn)的八進制數(shù)字需要多少個二進制數(shù)字？若用等長的(長為3)的碼字傳輸需要多少個二進制數(shù)字?解用Huffman算法求以頻率(乘以100)為權的最優(yōu)2叉樹.這里w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.30實例例在通信中，設八進制數(shù)字出現(xiàn)的頻率如下：31例(續(xù))

編碼:0---011---112---0013---1004---1015---00016---000007---00001傳100個按比例出現(xiàn)的八進制數(shù)字所需二進制數(shù)字的個數(shù)為W(T)=285.傳10n(n

2)個所用二進制數(shù)字的個數(shù)為2.85

10n,而用等長碼(長為3)需要用3

10n個數(shù)字.31例(續(xù))32行遍2叉有序樹行遍(周游)根樹T

:對T的每個頂點訪問且僅訪問一次.行遍2叉有序樹的方式：①中序行遍法:左子樹、根、右子樹②前序行遍法:根、左子樹、右子樹③后序行遍法:左子樹、右子樹、根當不是正則樹時,左子樹或右子樹可缺省例如,中序行遍:b

a(f

d

g)c

e

前序行遍:a

b(c(d

f

g)e)后序行遍:b((f

g

d)e

c)a32行遍2叉有序樹行遍(周游)根樹T:對T的每個頂點訪33用2叉有序樹表示算式每一個分支點放一個運算符.二元運算符所在的分支點有2個兒子,運算對象是以這2個兒子為根的根子樹表示的子表達式,并規(guī)定被減數(shù)和被除數(shù)放在左子樹上;一元運算符所在的分支點只有一個兒子,運算對象是以這個兒子為根的根子樹表示的子表達式.數(shù)字和變量放在樹葉上.33用2叉有序樹表示算式每一個分支點放一個運算符.二元運算實例例1表示((b+(c+d))

a)

((e

f)

(g+h)

(i

j))的2叉有序樹中序行遍:((b+(c+d))

a)

((e

f)

(g+h)

(i

j))前序行遍:((b(cd))a)((ef)((gh)(ij)))后序行遍:((b(cd))a)((ef)((gh)(ij)))注:中序行遍的結果是原式34實例例1表示((b+(c+d))a)((ef)(35波蘭符號法波蘭符號法(前綴符號法):按前序行遍法訪問表示算式的2叉有序樹,并舍去所有括號.例1(續(xù))

b+cda

ef

+gh

ij

計算方法:從左到右,每個運算符號對它后面緊鄰的2個(或1個)數(shù)進行運算.例1(續(xù))設a=3,b=1,c=d=2,e=f=3,g=i=1,h=j=2.

1+22333+1212,

14333+1212

5333+1212,

(15)33

+1212

(15)9+1212,

(15)931