第十六章

樹主要內容無向樹及其性質生成樹根樹及其應用

116.1無向樹及其性質定義16.1

(1)無向樹——連通無回路的無向圖(2)平凡樹——平凡圖(3)森林——至少由兩個連通分支（每個都是樹）組成的無向圖(4)樹葉——1度頂點(5)分支點——度數2的頂點

2無向樹的等價定義定理16.1設G=<V,E>是n階m條邊的無向圖，則下面各命題是等價的：(1)G是樹(2)G中任意兩個頂點之間存在惟一的路徑.(3)G中無回路且m=n1.(4)G是連通的且m=n1.(5)G是連通的且G中任何邊均為橋.(6)G中沒有回路，但在任何兩個不同的頂點之間加一條新邊，在所得圖中得到惟一的一個含新邊的圈.3由上式解出x2.

定理16.2設T是n階非平凡的無向樹，則T中至少有兩片樹葉.無向樹的性質證設T有x片樹葉，由握手定理及定理16.1可知，4例題例1已知無向樹T中有1個3度頂點，2個2度頂點，其余頂點全是樹葉，試求樹葉數.解解本題用樹的性質m=n1，握手定理.設有x片樹葉，于是n=1+2+x=3+x,2m=2(n1)=2(2+x)=13+22+x解出x=3，故T有3片樹葉.5例2已知無向樹T有5片樹葉，2度與3度頂點各1個，其余頂點的度數均為4，求T的階數n例題解設T的階數為n,則邊數為n1，4度頂點的個數為n7.由握手定理得2m=2(n1)=51+21+31+4(n7)解出n=8，4度頂點為1個.6子圖定義14.8

G=<V,E>,G=<V,E>(1)GG——G為G的子圖，G為G的母圖(2)若GG且V=V，則稱G為G的生成子圖(3)若VV或EE，稱G為G的真子圖(4)V（VV且V）的導出子圖，記作G[V](5)E（EE且E）的導出子圖，記作G[E]在圖中，設G為(1)中圖所表示，取V1={a，b，c}，則V1的導出子圖G[V1]為(2)中圖所示。取E1={e1，e3}，則E1的導出子圖G[E1]為(3)中圖所示。7不一定連通，也不一定不含回路，如圖所示定義16.2設G為無向圖(1)G的樹——T是G的子圖并且T是樹(2)G的生成樹——T是G的生成子圖并且T是樹(3)生成樹T的樹枝——G的在T中的邊(4)生成樹T的弦——G的不在T中的邊(5)生成樹T的余樹——T的所有弦的導出子圖16.2生成樹8推論2

的邊數為mn+1.推論3

為G的生成樹T的余樹，C為G中任意一個圈，則C與一定有公共邊.證否則，C中的邊全在T中，這與T為樹矛盾.定理16.3無向圖G具有生成樹當且僅當G連通.生成樹存在條件推論1

G為n階m條邊的無向連通圖，則mn1.證必要性顯然.充分性用破圈法（注意：在圈上刪除任何一條邊，不破壞連通性）由定理16.3和樹的邊數等于頂點數減1可立即得到下述推論。9基本回路系統定理16.4設T為G的生成樹，e為T的任意一條弦，則Te中含一個只有一條弦其余邊均為T的樹枝的圈.不同的弦對應的圈也不同.證設e=(u,v)，在T中u到v有惟一路徑，則e為所求的圈.定義16.3設T是n階m條邊的無向連通圖G的一棵生成樹，設e1,e2,…,emn+1為T的弦.設Cr為T添加弦er產生的只含弦er、其余邊均為樹枝的圈.稱Cr為G的對應樹T的弦er的基本回路或基本圈，r=1,2,…,mn+1.并稱{C1,C2,…,Cmn+1}為G對應T的基本回路系統，稱mn+1為G的圈秩，記作

(G).求基本回路的算法：設弦e=(u,v)，先求T中u到v的路徑uv，再并上弦e，即得對應e的基本回路.10Ca=aefCb=bdeCc=cdf此圖的圈秩為3，基本回路系統為：{Ca,Cb,Cc}基本回路系統在下圖中，對應生成樹的弦a，b，c的基本回路為：11基本割集的存在定理16.5設T是連通圖G的一棵生成樹，e為T的樹枝，則G中存在只含樹枝e，其余邊都是弦的割集，且不同的樹枝對應的割集也不同.證由定理16.1可知，e是T的橋，因而Te有兩個連通分支T1和T2，令

Se={e|eE(G)且e的兩個端點分別屬于V(T1)和V(T2)}，由構造顯然可知Se為G的割集，eSe且Se中除e外都是弦，所以Se為所求.顯然不同的樹枝對應的割集不同.12定義16.4設T是n階連通圖G的一棵生成樹，e1,e2,…,en1為T的樹枝，Si是G的只含樹枝ei的割集，則稱Si為G的對應于生成樹T由樹枝ei生成的基本割集，i=1,2,…,n1.并稱{S1,S2,…,Sn1}為G對應T的基本割集系統，稱n1為G的割集秩，記作(G).基本割集與基本割集系統求基本割集的算法設e為生成樹T的樹枝，Te為兩棵小樹T1與T2，令Se={e|eE(G)且e的兩個端點分別屬于T1與T2}則Se為e對應的基本割集.13Sa={a,f,g}Sb={b,g,h}Sd={d,h,i}Sc={c,f,h}Se={e,f,i}基本割集系統為：{Sa,Sb,Sc,Sd,Se}割集秩為5.基本割集與基本割集系統在下圖中，對應樹枝a，b，c，d，e的基本割集分別為：14解弦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,f

g},Sd={d,g},S基={Sa,Sb,Sc,Sd}.

例下圖實線邊所示為生成樹，求基本回路系統與基本割集系統實例15最小生成樹定義16.5

T是無向連通帶權圖G=<V,E,W>的生成樹(1)T的權W(T)——T的各邊權之和(2)G的最小生成樹——G的所有生成樹中權最小的生成樹求最小生成樹的一個算法避圈法（Kruskal）設G=<V,E,W>，將G中非環邊按權從小到大排序：e1,e2,…,em.(1)取e1在T中(2)查e2，若e2與e1不構成回路，取e2也在T中，否則棄去e2.(3)再查e3,…,直到得到生成樹為止.16例4求圖的一棵最小生成樹.所求最小生成樹如圖所示，W(T)=38.實例1716.3

根樹及其應用定義16.6有向樹T——基圖為無向樹的有向圖。(1)T為根樹——T中一個頂點入度為0，其余頂點入度均為1的有向樹.(2)樹根——入度為0的頂點(3)樹葉——入度為1，出度為0的頂點(4)內點——入度為1，出度不為0的頂點(5)分支點——樹根與內點的總稱(6)頂點v的層數——從樹根到任意頂點v的路徑的長度（即路徑中的邊數）(7)樹高——T中所有頂點的最大層數(8)平凡根樹——平凡圖18根樹的畫法:樹根放上方,省去所有有向邊上的箭頭如右圖所示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.樹高為4根樹實例19家族樹與根子樹定義16.7設T為一顆非平凡的根樹(1)祖先與后代——vi

，vj

∈V(T)，vi

≠vj，若vi

可達vj

，則稱vi

為vj的祖先

，vj為vi的后代

。(2)父親與兒子——vi

，vj

∈V(T)，vi

≠vj，若vi

鄰接到vj（即<vi

，vj

>∈E(T)）

，則稱vi

為vj的父親

，vj為vi的兒子

。(3)兄弟——vj

，vk∈V(T)，vj

≠vk，若vj

，vk的父親相同

，則稱vj與vk是兄弟

。定義16.8設v為根樹T中的任意一個頂點，稱v及其后代的導出子圖Tv為T的以v為根的根子樹.常將根樹看成家族樹，家族中成員之間的關系由下面的定義給出：20根樹的分類(1)T為有序根樹——同層上的頂點都標定次序的根樹(2)根據根樹T中的每個分支點兒子數以及是否有序，可以將根樹分為下列各類：①r叉樹——每個分支點至多有r個兒子②r叉有序樹——r叉樹是有序的③r叉正則樹——每個分支點恰有r個兒子④r叉正則有序樹——又若r叉正則樹是有序的⑤r叉完全正則樹——樹葉層數相同的r叉正則樹⑥r叉完全正則有序樹——又若r叉完全正則樹是有序的

2叉正則有序樹的每個分支點的兩個兒子導出的根子樹分別稱為該分支點的左子樹和右子樹。在所有的r叉樹中，最常用的是2叉樹。下面介紹2叉樹的應用。21定義16.9

設2叉樹T有t片樹葉v1,v2,…,vt，權分別為w1,w2,…,wt，稱為T的權，其中l(vi)是vi的層數.在所有有t片樹葉，帶權w1,w2,…,wt的2叉樹中，權最小的2叉樹稱為最優2叉樹.最優二叉樹求最優2叉樹的算法——Huffman算法給定實數w1,w2,…,wt，且w1w2…wt.（1）作t片樹葉,分別以w1,w2,…,wt為權.（2）在所有入度為0的頂點(不一定是樹葉)中選出兩個權最小的頂點,添加一個新分支點,以這2個頂點為兒子,其權等于這2個兒子的權之和.（3）重復（2）,直到只有1個入度為0的頂點為止.W(T)等于所有分支點的權之和22例5求帶權為1,1,2,3,4,5的最優樹.解題過程由下圖給出，W(T)=38最優二叉樹的算法——Huffman算法23最佳前綴碼定義16.10設12…n-1n是長度為n的符號串(1)前綴——該符號串的子串1,12,…,12…n1

(2)前綴碼——符號串集合A={1,2,…,m}中的任意兩個符號串都互不為前綴(3)二元前綴碼——i(i=1,2,…,m)中只出現兩個符號，如0與1.如何產生二元前綴碼？定理16.6一棵2叉樹產生一個二元前綴碼.推論一棵正則2叉樹產生惟一的一個二元前綴碼（按左子樹標0，右子樹標1）24一棵2元樹產生一個二元前綴碼:對每個分支點,若關聯2條邊,則給左邊標0,右邊標1;若只關聯1條邊,則可以給它標0(看作左邊),也可以標1(看作右邊).將從樹根到每一片樹葉的通路上標的數字組成的字符串記在樹葉處,所得的字符串構成一個前綴碼，如右圖所示：樹的編碼：最優2進制編碼：使信息傳遞的2進制數最短由最優2叉樹產生的前綴碼為最佳前綴碼。用最佳前綴碼傳輸的二進制位數最省。最佳前綴碼25圖所示二叉樹產生的前綴碼為{00,10,11,011,0100,0101}二叉樹產生的前綴碼26用Huffman算法產生最佳前綴碼例16.7在通信中，八進制數字出現的頻率如下：0：25%1：20%2：15%3：10%4：10%5：10%6：5%7：5%求傳輸它們的最佳前綴碼，并求傳輸10n（n2）個按上述比例出現的八進制數字需要多少個二進制數字？若用等長的（長為3）的碼字傳輸需要多少個二進制數字？27解用100個八進制數字中各數字出現的個數，即以100乘各頻率為權，并將各權由小到大排列，得w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25。用Huffman算法求以頻率(乘以100)為權的最優2叉樹。用此權產生的最優2叉樹如下圖所示：求最佳前綴碼傳100個按比例出現的八進制數字所需二進制數字的個數為W(T)=285，傳10n(n2)個按比例出現的八進制數字需要2.8510n個二進制數字，用等長碼(長為3)傳輸需310n個二進制數字.01-----011-----1001-----2100-----3101-----40001-----500000-----600001-----7它產生的最優前綴碼28波蘭符號法與逆波蘭符號法行遍或周游根樹T——對根樹T的每個頂點訪問且僅訪問一次.對于2叉有序正則樹有以下三種周游方式：①中序行遍法——訪問的次序為：左子樹、根、右子樹②前序行遍法——訪問的次序為：根、左子樹、右子樹③后序行遍法——訪問的次序為：左子樹、右子樹、根對如右圖所示的根樹T（2叉有序正則樹）按中序、前序、后序行遍的周游結果分別為：

b

a(f

d

g)c

e，

a

b(c(d

f

g)e)，

b((f

g

d)e

c)a29用2叉有序正則樹存放算式存放規則最高層次運算放在樹根然后依次將運算符放在根子樹的根上數放在樹葉上規定：被除數、被減數放在左子樹樹葉上

算式((b+(c+d))a)((ef)(g+h)(ij))存放在如上圖所示的2叉有序正則樹上.30波蘭符號法波蘭符號法按前序行遍法訪問存放算式的2叉有序正則樹，其結果不加括號，規定從右到左每個運算符對它后面緊鄰的兩個數進行運算。在這種算法中，由于運算符在它的兩個運算對象之前，所以稱此種算法為前綴符號法或波蘭符號法.對下圖的訪問結果為

b+c

d

a

e

f

+g

h

i

j

逆波蘭符號法按后序行遍法訪問存放算式的2叉有序正則樹，其結果不加括號，規定從左到右每個運算符對它前面緊鄰的兩個數進行運算。在這種算法中，由于運算符在它的兩個運算對象之后，所以稱此種算法為后綴符號法或逆波蘭符號法.對上圖的訪問結果為b

c

d++a

e

f

g

h+i

j

31重點主要內容無向樹及其性質生成樹、最小生成樹、基本回路系統、基本割集系統根樹及其分類、最優樹、二叉樹產生的前綴碼、最佳前綴碼、波蘭符號法、逆波蘭符號法基本要求深刻理解無向樹的定義及性質熟練地求解無向樹準確地求出給定帶權連通圖的最小生成樹深刻理解基本回路、基本割集的概念，并會計算理解根樹及其分類等概念熟練掌握求最優樹及最佳前綴碼的方法掌握波蘭符號法與逆波蘭符號法32第十六章習題課主要內容無向樹及其性質生成樹、最小生成樹、基本回路系統、基本割集系統根樹及其分類、最優樹、最佳前綴碼、波蘭符號法、逆波蘭符號法基本要求深刻理解無向樹的定義及性質熟練地求解無向樹準確地求出給定帶權連通圖的最小生成樹深刻理解基本回路、基本割集的概念，并會計算理解根樹及其分類等概念會畫n階（n較小）非同構的無向樹及根樹（1n6）熟練掌握求最優樹及最佳前綴碼的方法掌握波蘭符號法與逆波蘭符號法33（2）（3）從而解出練習11.無向樹T有ni個i度頂點，i=2,3,…,k，其余頂點全是樹葉，求T的樹葉數.解用樹的性質：邊數m=n1（n為階數），及握手定理.(1)342．設n階非平凡的無向樹T中，(T)

k，k1.證明T至少有k片樹葉.證反證法.否則，T至多有s片樹葉，s<k，下面利用握手定理及樹的性質m=n1推出矛盾.由于(T)

k，故存在v0，d(v0)

k.于是，由此解出s

k，這與s<k矛盾.證本題的方法有多種，請用分支點都是割點來證明.練習2353．設G為n階無向簡單圖，n5，證明G或中必含圈.本題的方法很多