第7章樹及其應用1第7章樹及其應用7.1無向樹7.2根樹及其應用27.1無向樹7.1.1無向樹的定義及其性質7.1.2生成樹與基本回路和基本割集7.1.3最小生成樹3無向樹的定義無向樹:連通無回路的無向圖平凡樹:平凡圖森林:每個連通分支都是樹的非連通的無向圖樹葉:樹中度數為1的頂點分支點:樹中度數

2的頂點例如(a)(b)4無向樹的性質定理7.1設G=<V,E>是n階m條邊的無向圖,下面各命題是等價的：(1)G是樹(連通無回路);(2)G中任意兩個頂點之間存在惟一的路徑;(3)G是連通的且m=n

1;(4)G中無回路且m=n

1;(5)G中無回路,但在任何兩個不相鄰的頂點之間加一條邊所得圖中有惟一的一條初級回路.(6)G是連通的且G中任意一條邊均為橋.5定理7.1的證明(1)(2)由連通性,任意2個頂點之間有一條路徑.又,假設某2個頂點之間有2條路徑,則這2條路徑可組合成一條回路,與樹的定義矛盾.(2)(3)顯然連通,要證m=n

1.對n作歸納證明.當n=1時,顯然m=0,結論成立.假設當n

k(k1)時結論成立,考慮n=k+1.任取一條邊e=(u,v),它是u,v之間惟一的通路,刪去e,G被分成2個連通分支,設它們分別有n1,n2個頂點和m1,m2條邊,n1

k,

n2

k.由歸納假設,m1=n1-1,m2=n2-1,得m=m1+m2+1=n-1.6定理7.1的證明(續)(3)(4)假設有回路,任取一個回路,刪去回路中的一條邊,所得圖仍是連通的.重復這個做法,直到沒有回路為止,得到一棵樹,它有n個頂點m-r條邊,r>0.由(1)(2)(3),得m-r=n-1,矛盾.(4)(1)只需證G連通.假設G不連通,有p(p>1)個連通分支.設第k個連通分支有nk個頂點和mk條邊,由(1)(2)(3),mk=nk-1.得到m=n-p,矛盾.7定理7.1的證明(續)(1)(5)由(1)(2),任意2個不相鄰的頂點之間有一條惟一的路徑,故在這2個頂點之間添加一條新邊,必得到一條惟一的初級回路.(5)(6)首先,任意2個不相鄰的頂點之間都有一條通路,否則在它們之間添加一條新邊不可能構成回路,故G連通.其次,若刪去一條邊G仍是連通的,這條邊必在一條回路上,與G中無回路矛盾.(6)(1)G中無回路,否則刪去回路上任意條邊,G仍連通.8無向樹的性質(續)定理7.2

非平凡的無向樹至少有兩片樹葉證設有n(n>1)個頂點,x片樹葉,由握手定理和定理7.1,有

解得x

2.9實例例1已知無向樹T中,有1個3度頂點,2個2度頂點,其余頂點全是樹葉.試求樹葉數,并畫出滿足要求的非同構的無向樹.解設有x片樹葉,2

(2+x)=1

3+2

2+x解得x=3，故T有3片樹葉.T的度數列為1,1,1,2,2,310實例例2畫出所有6階非同構的無向樹解5條邊,總度數等于10可能的度數列:(1)1,1,1,1,1,5(2)1,1,1,1,2,4(3)1,1,1,1,3,3(4)1,1,1,2,2,3(5)1,1,2,2,2,2(1)(2)(3)(4a)(4b)(5)11生成樹定義7.2

設G是無向連通圖,若G的生成子圖T是一棵樹,則稱T是G的生成樹.G在T中的邊稱作T的樹枝,不在T中的邊稱作T的弦.T的所有弦的集合的導出子圖稱作T的余樹例如圖中黑邊構成生成樹紅邊構成余樹注意:余樹一般不是樹12生成樹的存在性定理7.3

任何無向連通圖都有生成樹.證用破圈法.若圖中無圈,則圖本身就是自己的生成樹.否則刪去圈上的任一條邊,不破壞連通性,重復進行直到無圈為止,得到圖的一棵生成樹.推論1

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

n

1.推論2

設n階無向連通圖有m條邊,則它的生成樹的余樹有m

n+1條邊.13基本回路與基本回路系統定義7.3設G是n階m條邊的無向連通圖,T是G的一棵生成樹,e1,

e2,…,em

n+1為T的弦.G中僅含T的一條弦er的圈Cr稱作對應弦er的基本回路.稱{C1,C2,…,Cm

n+1}為對應T的基本回路系統例3

圖中紅邊為一棵生成樹,對應它的基本回路系統為{bce,fae,gaed}14基本割集與基本割集系統定義7.4設T是n階連通圖G的一棵生成樹,e1,

e2,…,e

n

1為T的樹枝，Si是G的只含樹枝ei,其他邊都是弦的割集,稱Si為對應樹枝ei

的基本割集.稱{S1,S2,…,Sn

1}為對應T的基本割集系統例4

圖中紅邊為一棵生成樹,對應它的基本割集系統為{{a,f,g},}{e,b,f,g},{c,b},{d,g}15最小生成樹圖G的每一條邊e附加一個實數w(e),稱作邊e的權.圖G連同附加在邊上的權稱作帶權圖,記作G=<V,E,W>.設H是G的子圖,H所有邊的權的和稱作H的權,記作W(H).

最小生成樹:帶權圖權最小的生成樹避圈法(Kruskal)(1)將所有非環邊按權從小到大排列,

設為e1,e2,…,em(2)令T

=

(3)Fork=1tomDo若ek與T中的邊不構成回路,則將ek加入T中16實例例5

求圖的一棵最小生成樹W(T)=38177.2

根樹及其應用7.2.1根樹及其分類7.2.2最優樹與哈夫曼算法7.2.3最佳前綴碼7.2.4根樹的周游及其應用中序行遍法、前序行遍法和后序行遍法波蘭符號法與逆波蘭符號法18根樹的定義有向樹:略去方向后為無向樹的有向圖根樹:有一個頂點入度為0,其余的入度均為1的非平凡的有向樹樹根:有向樹中入度為0的頂點樹葉:有向樹中入度為1,出度為0的頂點內點:有向樹中入度為1,出度大于0的頂點分支點:樹根與內點的總稱頂點v的層數:從樹根到v的通路長度樹高:有向樹中頂點的最大層數19實例根樹的畫法:樹根放最上方,省去所有有向邊上的箭頭右圖中

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家族樹把根樹看作一棵家族樹:若頂點a鄰接到頂點b,則稱b是a的兒子,a是b的父親若b和c為同一個頂點的兒子,則稱b和c是兄弟若a

b且a可達b,則稱a是b的祖先,b是a的后代設v為根樹的一個頂點且不是樹根,稱v及其所有后代的導出子圖為以v為根的根子樹將根樹每一層上的頂點規定次序后稱作有序樹21根樹的分類r元樹:根樹的每個分支點至多有r個兒子r元正則樹:根樹的每個分支點恰有r個兒子r元完全正則樹:所有樹葉層數相同的r元正則樹r元有序樹:有序的r元樹r元正則有序樹:有序的r元正則樹r元完全正則有序樹:有序的r元完全正則樹22最優2元樹定義7.10設2元樹T有t片樹葉v1,v2,…,vt,樹葉的權分別為w1,w2,…,wt,稱為T的權,記作W(T),其中l(vi)是vi的層數.在所有有t片樹葉,帶權w1,w2,…,wt的2元樹中,權最小的2元樹稱為最優2元樹例如134561345613456W(T1)=47W(T2)=54W(T3)=4323求最優2元樹的算法哈夫曼(Huffman)算法給定實數w1,w2,…,wt

①作t片樹葉,分別以w1,w2,…,wt為權②在所有入度為0的頂點(不一定是樹葉)中選出兩個權最小的頂點,添加一個新分支點,以這2個頂點為兒子,其權等于這2個兒子的權之和③重復②,直到只有1個入度為0的頂點為止W(T)等于所有分支點的權之和24實例例1求以1,3,4,5,6為權的最優2元樹,并計算它的權解134(a)13448(b)134456811(cd)W(T)=4+8+11+19=4225最佳前綴碼定義7.11設

=

1

2…

n-1

n是長度為n的符號串,

1

2…

k稱作

的長度為k的前綴,k=1,2,…,n-1.

若非空字符串

1,

2,…,

m中任何兩個互不為前綴,則稱{

1,

2,…,

m}為前綴碼只出現兩個符號(如0與1)的前綴碼稱作2元前綴碼例如

{0,10,110,1111},{10,01,001,110}是2元前綴碼{0,10,010,1010}不是前綴碼26用2元樹產生2元前綴碼的方法對每個分支點,若關聯2條邊,則給左邊標0,右邊標1;若只關聯1條邊,則可以給它標0(看作左邊),也可以標1(看作右邊).將從樹根到每一片樹葉的通路上標的數字組成的字符串記在樹葉處,所得的字符串構成一個前綴碼.例如前綴碼{00,11,011,0100}27實例例2在通信中,設八進制數字出現的頻率(%)如下:0:25,1:20,2:15,3:10,4:10,5:10,6:5,7:5采用2元前綴碼,求傳輸數字最少的2元前綴碼(稱作最佳前綴碼),并求傳輸100個按上述比例出現的八進制數字需要多少個二進制數字？若用等長的(長為3)的碼字傳輸需要多少個二進制數字?解用Huffman算法求以頻率(乘以100)為權的最優2元樹.這里w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.28實例(續)編碼:0---011---112---0013---1004---1015---00016---000007---00001傳100個按比例出現的八進制數字需W(T)=285個二進制數字,用等長碼(長為3)需要用300個數字.29根樹的周游及其應用對一棵根樹的每個頂點訪問一次且僅訪問一次稱作對根樹的行遍或周游

行遍2元有序正則樹的方式：①中序行遍法:左子樹、樹根、右子樹②前序行遍法:樹根、左子樹、右子樹③后序行遍法:左子樹、右子樹、樹根30實例例3中序行遍:前序行