離散數(shù)學(xué)屈婉玲第十章PPT課件

1、10.1 無向樹及其性質(zhì)定義10.1 連通無回路的無向圖稱為無向樹, 簡稱樹. 每個(gè)連通分支都是樹的無向圖稱為森林. 平凡圖稱為平凡樹. 在無向樹中, 懸掛頂點(diǎn)稱為樹葉, 度數(shù)大于或等于2的頂點(diǎn)稱為分支點(diǎn)例 f f f星形樹第1頁/共30頁2無向樹的性質(zhì) 定理10.1 設(shè)G=是n階m條邊的無向圖，則下面各命題 是等價(jià)的： (1) G 是樹 (2) G 中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑. (3) G 中無回路且 m=n1. (4) G 是連通的且 m=n1. (5) G 是連通的且 G 中任何邊均為橋. (6) G 中沒有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊后所得圖中有惟一的一個(gè)含新邊的圈

2、. 第2頁/共30頁3(3)(4). 只需證明G連通. 用反證法. 否則G有s(s2)個(gè)連通分支, 它們都是樹. 于是, 有mi=ni1,這與m=n1矛盾. 證明 (2)(3). 若G中有回路，則回路上任意兩點(diǎn)之間的路徑不 惟一. 對(duì)n用歸納法證明m=n1. 當(dāng)n=1時(shí)成立. 設(shè)nk時(shí)成立，證n=k+1時(shí)也成立：任取 一條邊e，Ge有且僅有兩個(gè)連通分支G1,G2 . nik，由歸 納假設(shè)得mi=ni1, i=1,2. 于是， m=m1+m2+1=n1+n22+1=n1.)2(11 ssnsnmmsiisii證 (1)(2). 若路徑不惟一, 必有回路. 第3頁/共30頁4 (4)(5). 只需

3、證明G 中每條邊都是橋. 下述命題顯然成立: G 是 n 階 m 條邊的無向連通圖，則 mn1. eE, Ge只有n2條邊，由命題可知Ge不連通，故e為橋. 證明(5)(6). 由(5)易知G為樹. 由(1)(2)知，u,vV（uv）, u到v有惟一路徑，加新邊(u,v)得惟一的一個(gè)圈. (6)(1). 只需證明G連通，這是顯然的. 第4頁/共30頁)(2)()1(2xnxvdni 解得 x 2. 定理10.2 設(shè)T是n階非平凡的無向樹，則T 中至少有兩片樹葉. 無向樹的性質(zhì)證 設(shè) T 有 x 片樹葉，由握手定理及定理10.1可知，例1 已知無向樹T中有1個(gè)3度頂點(diǎn)，2個(gè)2度頂點(diǎn)，其余頂點(diǎn)全是

4、樹葉，試求樹葉數(shù)，并畫出滿足要求的非同構(gòu)的無向樹. 解 設(shè)有x片樹葉，n = 3+x. 2m = 2(n1) = 2(2+x) = 13+22+x解出x = 3，故T有3片樹葉.第5頁/共30頁6 例2 已知無向樹T有5片樹葉，2度與3度頂點(diǎn)各1個(gè)，其余頂 點(diǎn)的度數(shù)均為4，求T的階數(shù)n，并畫出滿足要求的所有非同 構(gòu)的無向樹. 例題解 設(shè)T的階數(shù)為n, 則邊數(shù)為n1，4度頂點(diǎn)的個(gè)數(shù)為n7. 由握手定理, 2m = 2(n1) = 51+21+31+4(n7),解出n = 8，4度頂點(diǎn)為1個(gè). 第6頁/共30頁710.2 生成樹定義10.2 如果無向圖G的生成子圖T是樹，則稱T是G的生成樹. 設(shè)T

5、是G的生成樹，G的在T中的邊稱為T的樹枝，不在T中的邊為T的弦. 稱T的所有弦的導(dǎo)出子圖為T的余樹，記作 . 例T第7頁/共30頁8定理10.3 無向圖G有生成樹當(dāng)且僅當(dāng)G連通.生成樹存在條件推論 G為n階m條邊的無向連通圖，則mn1. 證 必要性顯然. 證充分性若G中無回路，則G為自己的生成樹若G中含圈，任取一圈，隨意地刪除圈上的一條邊; 若仍有圈, 再任取一個(gè)圈并刪去這個(gè)圈上的一條邊，重復(fù)進(jìn)行, 直到最后無圈為止. 最后得到的圖無圈（當(dāng)然無回路）、連通且是G的生成子圖，因而是G的生成樹這個(gè)產(chǎn)生生成樹的方法稱為破圈法第8頁/共30頁9最小生成樹 定義10.3 設(shè)無向連通帶權(quán)圖G=，T是G的一

6、棵生成 樹，T的各邊權(quán)之和稱為T的權(quán)，記作W(T)G的所有生成樹 中權(quán)最小的生成樹稱為G的最小生成樹.避圈法（Kruskal）輸入: 連通圖G=輸出: G的最小生成樹T 1. 將G中非環(huán)邊按權(quán)從小到大排列: W(e1)W(e2) W(em).2. 令Te1, i2.3. 若ei與T中的邊不構(gòu)成回路, 則令TTei.4. 若|T|n-1, 則令ii+1, 轉(zhuǎn)3.第9頁/共30頁10例4 求圖的一棵最小生成樹.W(T)=38實(shí)例第10頁/共30頁1116.3 根樹及其應(yīng)用定義10.4 若有向圖的基圖是無向樹, 則稱這個(gè)有向圖為有向樹. 一個(gè)頂點(diǎn)的入度為0、其余頂點(diǎn)的入度為1的有向樹稱為根樹入度為0

7、的頂點(diǎn)稱為樹根，入度為1出度為0的頂點(diǎn)稱為樹葉，入度為1出度不為0的頂點(diǎn)稱為內(nèi)點(diǎn)，內(nèi)點(diǎn)和樹根統(tǒng)稱為分支點(diǎn)從樹根到頂點(diǎn)v的路徑的長度(即, 路徑中的邊數(shù))稱為v的層數(shù). 所有頂點(diǎn)的最大層數(shù)稱為樹高根樹的畫法樹根放上方，省去所有有向邊上的箭頭例第11頁/共30頁12家族樹與根樹的分類 定義10.5 設(shè)T為一棵非平凡的根樹, vi,vjV(T), 若vi可達(dá)vj， 則稱vi為vj的祖先, vj為vi的后代; 若vi鄰接到vj, 則稱vi為vj的父 親, vj為vi的兒子. 若vj,vk的父親相同, 則稱vj與vk是兄弟 將根樹T中層數(shù)相同的頂點(diǎn)都標(biāo)定次序, 稱T為有序樹 根樹的分類： (1) 若T的

8、每個(gè)分支點(diǎn)至多有r個(gè)兒子，則稱T為r叉樹. (2) 若T的每個(gè)分支點(diǎn)都恰好有r個(gè)兒子, 則稱T為r叉正則樹. (3) 若T是r叉正則樹, 且所有樹葉的層數(shù)相同, 則稱T為r叉完 全正則樹. 有序的r叉樹, r叉正則樹, r叉完全正則樹分別稱作 r叉有序樹, r叉正則有序樹, r叉完全正則有序樹第12頁/共30頁13根子樹與最優(yōu)二叉樹 定義10.6 設(shè)T為一棵根樹, vV(T), 稱v及其后代的導(dǎo)出子圖 Tv為以v為根的根子樹 2叉正則有序樹的每個(gè)分支點(diǎn)的兩個(gè)兒子導(dǎo)出的根子樹分 別稱為該分支點(diǎn)的左子樹和右子樹 定義10.7 設(shè)2叉樹T 有t片樹葉v1, v2, , vt, 權(quán)分別為w1, w2,

9、 wt, 稱 為T 的權(quán), 其中l(wèi)i是vi 的層數(shù). 在所有有t片樹葉, 帶權(quán)w1, w2, , wt 的2叉樹中, 權(quán)最小的2叉樹稱為最優(yōu)2叉樹. niiilw1第13頁/共30頁14Huffman算法Huffman算法輸入: 實(shí)數(shù)w1, w2, , wt輸出: 最優(yōu)二叉樹1. 作t片樹葉, 分別以w1, w2, , wt為權(quán).2. 在所有入度為0的頂點(diǎn)(不一定是樹葉)中選出兩個(gè)權(quán)最小的頂點(diǎn), 添加一個(gè)新分支點(diǎn), 它以這2個(gè)頂點(diǎn)為兒子, 其權(quán)等于這2個(gè)兒子的權(quán)之和.3. 重復(fù)2, 直到只有1個(gè)入度為0的頂點(diǎn)為止. W(T)等于所有分支點(diǎn)的權(quán)之和.第14頁/共30頁15例 5 求權(quán)為2, 2,

10、 3, 3, 5的最優(yōu)樹. 解實(shí)例W(T)=34第15頁/共30頁16前綴碼 定義10.8 設(shè)12n1n是長為n的符號(hào)串, 稱其子串1, 12, , 12n為該符號(hào)串的前綴. 設(shè)A=1,2,m是一個(gè)符 號(hào)串集合, 若A的任意兩個(gè)符號(hào)串都互不為前綴, 則稱A為前 綴碼. 由0-1符號(hào)串構(gòu)成的前綴碼稱作二元前綴碼 例 1, 00, 011, 0101, 01001, 01000為前綴碼 1, 00, 011, 0101, 0100, 01001, 01000不是前綴碼第16頁/共30頁17用2叉樹產(chǎn)生二元前綴碼例一棵正則2叉樹產(chǎn)生惟一的前綴碼（按左枝標(biāo)0，右枝標(biāo)1）前綴碼的產(chǎn)生0110001110

11、11100000100011011000011011000000100011000001111101110000010001110第17頁/共30頁18最佳前綴碼 設(shè)符號(hào)Ai在傳輸中出現(xiàn)的頻率為pi, 二元前綴碼的長為li, 1it, 傳輸m個(gè)符號(hào)需要m 個(gè)二進(jìn)制位. 最小的二 元前綴碼稱作最佳前綴碼.最佳前綴碼可用Huffman算法計(jì)算 以頻率為權(quán)的最優(yōu)二叉樹產(chǎn)生. 例6 設(shè)在通信中, 八進(jìn)制數(shù)字出現(xiàn)的頻率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5% 求傳輸它們的最佳前綴碼, 并求傳輸10n (n2)個(gè)按上述比例 出現(xiàn)的八進(jìn)制數(shù)字需要多少

12、個(gè)二進(jìn)制數(shù)字？若用等長的(長 為3)的碼字傳輸需要多少個(gè)二進(jìn)制數(shù)字？ tiiilp1 tiiilp1第18頁/共30頁19解 傳輸100個(gè)八進(jìn)制數(shù)字中各數(shù)字出現(xiàn)的個(gè)數(shù), 即以100乘各頻率為: 25, 20, 15, 10, 10, 10, 5, 5, 以它們?yōu)闄?quán)構(gòu)造最優(yōu)二叉樹.實(shí)例最佳前綴碼 01-0 11-1 001-2 100-3 101-4 0001-500000-6 00001-7W(T)=285，傳輸10n(n2)個(gè)八進(jìn)制數(shù)字, 用最佳前綴碼需2.8510n位， 用等長碼需310n位. 第19頁/共30頁20有序樹的行遍方式行遍(周游)有序樹對(duì)每個(gè)頂點(diǎn)訪問且僅訪問一次. 對(duì)2叉有序

13、正則樹的周游方式： 中序行遍法. 訪問次序?yàn)椋鹤笞訕?、根、右子?前序行遍法. 訪問次序?yàn)椋焊?、左子樹、右子?后序行遍法. 訪問次序?yàn)椋鹤笞訕洹⒂易訕?、根?用中序, 前序, 后序行遍法訪問的結(jié)果分別為： b a (f d g) c e， a b (c (d f g) e)， b (f g d) e c) a第20頁/共30頁21用2叉有序樹存放算式 用2叉有序樹表示含有2元運(yùn)算和1元運(yùn)算的算式: 每個(gè)分支點(diǎn) 放一個(gè)運(yùn)算符, 其運(yùn)算對(duì)象是以它的兒子為樹根的子樹所表 示的子算式. 規(guī)定運(yùn)算對(duì)象的排列順序, 如被除數(shù)、被減數(shù)放 在左邊所有的變量和常量都放在樹葉上.例 (b+(c+d)a)(ef)

14、(g+h)(ij)用中序行遍法訪問還原算式第21頁/共30頁22波蘭符號(hào)法 波蘭符號(hào)法(前綴符號(hào)法): 按前序行遍法訪問存放算式的2叉 有序樹, 且不加括號(hào). 運(yùn)算規(guī)則: 從右到左每個(gè)運(yùn)算符號(hào)對(duì)其后面緊鄰的兩個(gè)或一 個(gè)對(duì)象進(jìn)行運(yùn)算. 如對(duì)上頁的算式 b + c d a e f + g h i j 逆波蘭符號(hào)法(后綴符號(hào)法): 按后序行遍法訪問,且不加括號(hào). 運(yùn)算規(guī)則:從左到右每個(gè)運(yùn)算符對(duì)其前面緊鄰的兩個(gè)或一個(gè) 對(duì)象進(jìn)行運(yùn)算. 如對(duì)上頁的算式 b c d + + a e f g h + i j 第22頁/共30頁23第十章 習(xí)題課主要內(nèi)容l 無向樹及其性質(zhì)l 生成樹、最小生成樹l 根樹及其分類、

15、最優(yōu)二叉樹、最佳前綴碼、波蘭符號(hào)法、逆波蘭符號(hào)法 基本要求l 深刻理解無向樹的定義及性質(zhì)l 熟練地求解無向樹l 準(zhǔn)確地求出給定帶權(quán)連通圖的最小生成樹l 理解根樹及其分類等概念l 熟練掌握求最優(yōu)二叉樹及最佳前綴碼的方法l 掌握波蘭符號(hào)法與逆波蘭符號(hào)法第23頁/共30頁24練習(xí)11. 無向樹 T 有ni個(gè)i 度頂點(diǎn)，i=2, 3, ,k，其余頂點(diǎn)全是樹葉，求T 的樹葉數(shù). tnivdtnmkiiniikii 212)(2222)2(3 kiinit解得解 用樹的性質(zhì)：邊數(shù) m=n1（n為階數(shù)），及握手定理.設(shè)有t片樹葉, 第24頁/共30頁252設(shè)n階非平凡的無向樹T中，(T) k，k 1. 證明

16、T至少 有k片樹葉. 證 設(shè)T有s片樹葉，由于(T) k，有sksnvdnmnii )1(2)(2221解得s k. 練習(xí)2第25頁/共30頁263設(shè)G為n 階無向簡單圖，n5，證明G 或 中必含圈.G練習(xí)3證一. 反證法. 否則G與 的各連通分支都是樹. 設(shè)G與 的連通分支的頂點(diǎn)數(shù)和邊數(shù)分別為ni, mi(1is)與 (1jt). 于是GG22)(2) 1() 1(2) 1(1111 ntsnnnmmnntjjsiitjjsii整理得 n25n+4 0 解得 1 n 4與n 5矛盾 jjmn ,第26頁/共30頁27證二. 在G與 中有一個(gè)(不妨設(shè)為G)邊數(shù)若G是森林, 則mn-1, 矛盾.Gnnnm 4)1(練習(xí)3第27頁/共30頁284畫出基圖為圖所示無向樹的所有非同構(gòu)的根樹 練習(xí)4解 以a, b, c, d為根的根樹同構(gòu), 選a為根, 如(1); 以 e, g 為根的根樹同構(gòu)，取 g為根，如(2)； 以 f 為根，如(3) . (1) (2) (3) 第28頁/共30頁295設(shè)T 是正則2叉樹，T 有t 片樹葉