版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
第十六章
樹主要內(nèi)容無向樹及其性質(zhì)生成樹根樹及其應(yīng)用
116.1無向樹及其性質(zhì)定義16.1
(1)無向樹——連通無回路的無向圖(2)平凡樹——平凡圖(3)森林——至少由兩個連通分支(每個都是樹)組成的無向圖(4)樹葉——1度頂點(5)分支點——度數(shù)2的頂點
2無向樹的等價定義定理16.1設(shè)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設(shè)T是n階非平凡的無向樹,則T中至少有兩片樹葉.無向樹的性質(zhì)證設(shè)T有x片樹葉,由握手定理及定理16.1可知,4例題例1已知無向樹T中有1個3度頂點,2個2度頂點,其余頂點全是樹葉,試求樹葉數(shù).解解本題用樹的性質(zhì)m=n1,握手定理.設(shè)有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個,其余頂點的度數(shù)均為4,求T的階數(shù)n例題解設(shè)T的階數(shù)為n,則邊數(shù)為n1,4度頂點的個數(shù)為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)的導(dǎo)出子圖,記作G[V](5)E(EE且E)的導(dǎo)出子圖,記作G[E]在圖中,設(shè)G為(1)中圖所表示,取V1={a,b,c},則V1的導(dǎo)出子圖G[V1]為(2)中圖所示。取E1={e1,e3},則E1的導(dǎo)出子圖G[E1]為(3)中圖所示。7不一定連通,也不一定不含回路,如圖所示定義16.2設(shè)G為無向圖(1)G的樹——T是G的子圖并且T是樹(2)G的生成樹——T是G的生成子圖并且T是樹(3)生成樹T的樹枝——G的在T中的邊(4)生成樹T的弦——G的不在T中的邊(5)生成樹T的余樹——T的所有弦的導(dǎo)出子圖16.2生成樹8推論2
的邊數(shù)為mn+1.推論3
為G的生成樹T的余樹,C為G中任意一個圈,則C與一定有公共邊.證否則,C中的邊全在T中,這與T為樹矛盾.定理16.3無向圖G具有生成樹當且僅當G連通.生成樹存在條件推論1
G為n階m條邊的無向連通圖,則mn1.證必要性顯然.充分性用破圈法(注意:在圈上刪除任何一條邊,不破壞連通性)由定理16.3和樹的邊數(shù)等于頂點數(shù)減1可立即得到下述推論。9基本回路系統(tǒng)定理16.4設(shè)T為G的生成樹,e為T的任意一條弦,則Te中含一個只有一條弦其余邊均為T的樹枝的圈.不同的弦對應(yīng)的圈也不同.證設(shè)e=(u,v),在T中u到v有惟一路徑,則e為所求的圈.定義16.3設(shè)T是n階m條邊的無向連通圖G的一棵生成樹,設(shè)e1,e2,…,emn+1為T的弦.設(shè)Cr為T添加弦er產(chǎn)生的只含弦er、其余邊均為樹枝的圈.稱Cr為G的對應(yīng)樹T的弦er的基本回路或基本圈,r=1,2,…,mn+1.并稱{C1,C2,…,Cmn+1}為G對應(yīng)T的基本回路系統(tǒng),稱mn+1為G的圈秩,記作
(G).求基本回路的算法:設(shè)弦e=(u,v),先求T中u到v的路徑uv,再并上弦e,即得對應(yīng)e的基本回路.10Ca=aefCb=bdeCc=cdf此圖的圈秩為3,基本回路系統(tǒng)為:{Ca,Cb,Cc}基本回路系統(tǒng)在下圖中,對應(yīng)生成樹的弦a,b,c的基本回路為:11基本割集的存在定理16.5設(shè)T是連通圖G的一棵生成樹,e為T的樹枝,則G中存在只含樹枝e,其余邊都是弦的割集,且不同的樹枝對應(yīng)的割集也不同.證由定理16.1可知,e是T的橋,因而Te有兩個連通分支T1和T2,令
Se={e|eE(G)且e的兩個端點分別屬于V(T1)和V(T2)},由構(gòu)造顯然可知Se為G的割集,eSe且Se中除e外都是弦,所以Se為所求.顯然不同的樹枝對應(yīng)的割集不同.12定義16.4設(shè)T是n階連通圖G的一棵生成樹,e1,e2,…,en1為T的樹枝,Si是G的只含樹枝ei的割集,則稱Si為G的對應(yīng)于生成樹T由樹枝ei生成的基本割集,i=1,2,…,n1.并稱{S1,S2,…,Sn1}為G對應(yīng)T的基本割集系統(tǒng),稱n1為G的割集秩,記作(G).基本割集與基本割集系統(tǒng)求基本割集的算法設(shè)e為生成樹T的樹枝,Te為兩棵小樹T1與T2,令Se={e|eE(G)且e的兩個端點分別屬于T1與T2}則Se為e對應(yīng)的基本割集.13Sa={a,f,g}Sb={b,g,h}Sd={d,h,i}Sc={c,f,h}Se={e,f,i}基本割集系統(tǒng)為:{Sa,Sb,Sc,Sd,Se}割集秩為5.基本割集與基本割集系統(tǒng)在下圖中,對應(yīng)樹枝a,b,c,d,e的基本割集分別為:14解弦e,f,g對應(yīng)的基本回路分別為
Ce=e
b
c,Cf=f
a
b
c,Cg=g
a
b
c
d,C基={Ce,Cf,Cg}.樹枝a,b,c,d對應(yīng)的基本割集分別為Sa={a,f,g},Sb={b,e,f,g},Sc={c,e,f
g},Sd={d,g},S基={Sa,Sb,Sc,Sd}.
例下圖實線邊所示為生成樹,求基本回路系統(tǒng)與基本割集系統(tǒng)實例15最小生成樹定義16.5
T是無向連通帶權(quán)圖G=<V,E,W>的生成樹(1)T的權(quán)W(T)——T的各邊權(quán)之和(2)G的最小生成樹——G的所有生成樹中權(quán)最小的生成樹求最小生成樹的一個算法避圈法(Kruskal)設(shè)G=<V,E,W>,將G中非環(huán)邊按權(quán)從小到大排序:e1,e2,…,em.(1)取e1在T中(2)查e2,若e2與e1不構(gòu)成回路,取e2也在T中,否則棄去e2.(3)再查e3,…,直到得到生成樹為止.16例4求圖的一棵最小生成樹.所求最小生成樹如圖所示,W(T)=38.實例1716.3
根樹及其應(yīng)用定義16.6有向樹T——基圖為無向樹的有向圖。(1)T為根樹——T中一個頂點入度為0,其余頂點入度均為1的有向樹.(2)樹根——入度為0的頂點(3)樹葉——入度為1,出度為0的頂點(4)內(nèi)點——入度為1,出度不為0的頂點(5)分支點——樹根與內(nèi)點的總稱(6)頂點v的層數(shù)——從樹根到任意頂點v的路徑的長度(即路徑中的邊數(shù))(7)樹高——T中所有頂點的最大層數(shù)(8)平凡根樹——平凡圖18根樹的畫法:樹根放上方,省去所有有向邊上的箭頭如右圖所示a是樹根b,e,f,h,i是樹葉c,d,g是內(nèi)點a,c,d,g是分支點a為0層;1層有b,c;2層有d,e,f;3層有g(shù),h;4層有i.樹高為4根樹實例19家族樹與根子樹定義16.7設(shè)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設(shè)v為根樹T中的任意一個頂點,稱v及其后代的導(dǎo)出子圖Tv為T的以v為根的根子樹.常將根樹看成家族樹,家族中成員之間的關(guān)系由下面的定義給出:20根樹的分類(1)T為有序根樹——同層上的頂點都標定次序的根樹(2)根據(jù)根樹T中的每個分支點兒子數(shù)以及是否有序,可以將根樹分為下列各類:①r叉樹——每個分支點至多有r個兒子②r叉有序樹——r叉樹是有序的③r叉正則樹——每個分支點恰有r個兒子④r叉正則有序樹——又若r叉正則樹是有序的⑤r叉完全正則樹——樹葉層數(shù)相同的r叉正則樹⑥r(nóng)叉完全正則有序樹——又若r叉完全正則樹是有序的
2叉正則有序樹的每個分支點的兩個兒子導(dǎo)出的根子樹分別稱為該分支點的左子樹和右子樹。在所有的r叉樹中,最常用的是2叉樹。下面介紹2叉樹的應(yīng)用。21定義16.9
設(shè)2叉樹T有t片樹葉v1,v2,…,vt,權(quán)分別為w1,w2,…,wt,稱為T的權(quán),其中l(wèi)(vi)是vi的層數(shù).在所有有t片樹葉,帶權(quán)w1,w2,…,wt的2叉樹中,權(quán)最小的2叉樹稱為最優(yōu)2叉樹.最優(yōu)二叉樹求最優(yōu)2叉樹的算法——Huffman算法給定實數(shù)w1,w2,…,wt,且w1w2…wt.(1)作t片樹葉,分別以w1,w2,…,wt為權(quán).(2)在所有入度為0的頂點(不一定是樹葉)中選出兩個權(quán)最小的頂點,添加一個新分支點,以這2個頂點為兒子,其權(quán)等于這2個兒子的權(quán)之和.(3)重復(fù)(2),直到只有1個入度為0的頂點為止.W(T)等于所有分支點的權(quán)之和22例5求帶權(quán)為1,1,2,3,4,5的最優(yōu)樹.解題過程由下圖給出,W(T)=38最優(yōu)二叉樹的算法——Huffman算法23最佳前綴碼定義16.10設(shè)12…n-1n是長度為n的符號串(1)前綴——該符號串的子串1,12,…,12…n1
(2)前綴碼——符號串集合A={1,2,…,m}中的任意兩個符號串都互不為前綴(3)二元前綴碼——i(i=1,2,…,m)中只出現(xiàn)兩個符號,如0與1.如何產(chǎn)生二元前綴碼?定理16.6一棵2叉樹產(chǎn)生一個二元前綴碼.推論一棵正則2叉樹產(chǎn)生惟一的一個二元前綴碼(按左子樹標0,右子樹標1)24一棵2元樹產(chǎn)生一個二元前綴碼:對每個分支點,若關(guān)聯(lián)2條邊,則給左邊標0,右邊標1;若只關(guān)聯(lián)1條邊,則可以給它標0(看作左邊),也可以標1(看作右邊).將從樹根到每一片樹葉的通路上標的數(shù)字組成的字符串記在樹葉處,所得的字符串構(gòu)成一個前綴碼,如右圖所示:樹的編碼:最優(yōu)2進制編碼:使信息傳遞的2進制數(shù)最短由最優(yōu)2叉樹產(chǎn)生的前綴碼為最佳前綴碼。用最佳前綴碼傳輸?shù)亩M制位數(shù)最省。最佳前綴碼25圖所示二叉樹產(chǎn)生的前綴碼為{00,10,11,011,0100,0101}二叉樹產(chǎn)生的前綴碼26用Huffman算法產(chǎn)生最佳前綴碼例16.7在通信中,八進制數(shù)字出現(xiàn)的頻率如下:0:25%1:20%2:15%3:10%4:10%5:10%6:5%7:5%求傳輸它們的最佳前綴碼,并求傳輸10n(n2)個按上述比例出現(xiàn)的八進制數(shù)字需要多少個二進制數(shù)字?若用等長的(長為3)的碼字傳輸需要多少個二進制數(shù)字?27解用100個八進制數(shù)字中各數(shù)字出現(xiàn)的個數(shù),即以100乘各頻率為權(quán),并將各權(quán)由小到大排列,得w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25。用Huffman算法求以頻率(乘以100)為權(quán)的最優(yōu)2叉樹。用此權(quán)產(chǎn)生的最優(yōu)2叉樹如下圖所示:求最佳前綴碼傳100個按比例出現(xiàn)的八進制數(shù)字所需二進制數(shù)字的個數(shù)為W(T)=285,傳10n(n2)個按比例出現(xiàn)的八進制數(shù)字需要2.8510n個二進制數(shù)字,用等長碼(長為3)傳輸需310n個二進制數(shù)字.01-----011-----1001-----2100-----3101-----40001-----500000-----600001-----7它產(chǎn)生的最優(yōu)前綴碼28波蘭符號法與逆波蘭符號法行遍或周游根樹T——對根樹T的每個頂點訪問且僅訪問一次.對于2叉有序正則樹有以下三種周游方式:①中序行遍法——訪問的次序為:左子樹、根、右子樹②前序行遍法——訪問的次序為:根、左子樹、右子樹③后序行遍法——訪問的次序為:左子樹、右子樹、根對如右圖所示的根樹T(2叉有序正則樹)按中序、前序、后序行遍的周游結(jié)果分別為:
b
a(f
d
g)c
e,
a
b(c(d
f
g)e),
b((f
g
d)e
c)a29用2叉有序正則樹存放算式存放規(guī)則最高層次運算放在樹根然后依次將運算符放在根子樹的根上數(shù)放在樹葉上規(guī)定:被除數(shù)、被減數(shù)放在左子樹樹葉上
算式((b+(c+d))a)((ef)(g+h)(ij))存放在如上圖所示的2叉有序正則樹上.30波蘭符號法波蘭符號法按前序行遍法訪問存放算式的2叉有序正則樹,其結(jié)果不加括號,規(guī)定從右到左每個運算符對它后面緊鄰的兩個數(shù)進行運算。在這種算法中,由于運算符在它的兩個運算對象之前,所以稱此種算法為前綴符號法或波蘭符號法.對下圖的訪問結(jié)果為
b+c
d
a
e
f
+g
h
i
j
逆波蘭符號法按后序行遍法訪問存放算式的2叉有序正則樹,其結(jié)果不加括號,規(guī)定從左到右每個運算符對它前面緊鄰的兩個數(shù)進行運算。在這種算法中,由于運算符在它的兩個運算對象之后,所以稱此種算法為后綴符號法或逆波蘭符號法.對上圖的訪問結(jié)果為b
c
d++a
e
f
g
h+i
j
31重點主要內(nèi)容無向樹及其性質(zhì)生成樹、最小生成樹、基本回路系統(tǒng)、基本割集系統(tǒng)根樹及其分類、最優(yōu)樹、二叉樹產(chǎn)生的前綴碼、最佳前綴碼、波蘭符號法、逆波蘭符號法基本要求深刻理解無向樹的定義及性質(zhì)熟練地求解無向樹準確地求出給定帶權(quán)連通圖的最小生成樹深刻理解基本回路、基本割集的概念,并會計算理解根樹及其分類等概念熟練掌握求最優(yōu)樹及最佳前綴碼的方法掌握波蘭符號法與逆波蘭符號法32第十六章習(xí)題課主要內(nèi)容無向樹及其性質(zhì)生成樹、最小生成樹、基本回路系統(tǒng)、基本割集系統(tǒng)根樹及其分類、最優(yōu)樹、最佳前綴碼、波蘭符號法、逆波蘭符號法基本要求深刻理解無向樹的定義及性質(zhì)熟練地求解無向樹準確地求出給定帶權(quán)連通圖的最小生成樹深刻理解基本回路、基本割集的概念,并會計算理解根樹及其分類等概念會畫n階(n較?。┓峭瑯?gòu)的無向樹及根樹(1n6)熟練掌握求最優(yōu)樹及最佳前綴碼的方法掌握波蘭符號法與逆波蘭符號法33(2)(3)從而解出練習(xí)11.無向樹T有ni個i度頂點,i=2,3,…,k,其余頂點全是樹葉,求T的樹葉數(shù).解用樹的性質(zhì):邊數(shù)m=n1(n為階數(shù)),及握手定理.(1)342.設(shè)n階非平凡的無向樹T中,(T)
k,k1.證明T至少有k片樹葉.證反證法.否則,T至多有s片樹葉,s<k,下面利用握手定理及樹的性質(zhì)m=n1推出矛盾.由于(T)
k,故存在v0,d(v0)
k.于是,由此解出s
k,這與s<k矛盾.證本題的方法有多種,請用分支點都是割點來證明.練習(xí)2353.設(shè)G為n階無向簡單圖,n5,證明G或中必含圈.本題的方法很多
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 房屋租賃防火合同
- 2024年度綠色建筑節(jié)能改造示范項目土建施工分包合同2篇
- 2024年汽車銷售應(yīng)收賬款質(zhì)押擔(dān)保與市場拓展合作合同3篇
- 2024年大型活動場景設(shè)計制作服務(wù)合同2篇
- 2024事業(yè)單位保密協(xié)議范本與保密工作計劃2篇
- 2024年獼猴桃樹苗直銷協(xié)議
- 2024全新原創(chuàng)油畫作品銷售合作協(xié)議下載2篇
- 2024年物業(yè)施工項目合作合同樣本版B版
- 2024年新型零售業(yè)態(tài)合作協(xié)議范本詳錄3篇
- 2024年更新版:托管班學(xué)生個人隱私保護協(xié)議3篇
- 25公斤級平焊法蘭及螺栓規(guī)格尺寸
- (完整word版)PT100溫度傳感器三根芯線的接法
- SLT-縮短制造周期ppt課件
- 醫(yī)生問診時與患者對話
- 中華護理學(xué)會會員申請表(普通+資深會員)
- 電子政務(wù)教案人民大學(xué)
- 最新國家電網(wǎng)公司電力安全工作規(guī)程
- (完整版)HSE管理體系及措施
- 淺談吉林省中藥材產(chǎn)業(yè)發(fā)展
- 職業(yè)生涯規(guī)劃檔案建立過程
- 小型步進電機控制系統(tǒng)設(shè)計
評論
0/150
提交評論