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

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

2、. 第2頁/共30頁3(3)(4). 只需證明G連通. 用反證法. 否則G有s(s2)個連通分支, 它們都是樹. 于是, 有mi=ni1,這與m=n1矛盾. 證明 (2)(3). 若G中有回路，則回路上任意兩點之間的路徑不 惟一. 對n用歸納法證明m=n1. 當n=1時成立. 設nk時成立，證n=k+1時也成立：任取 一條邊e，Ge有且僅有兩個連通分支G1,G2 . nik，由歸 納假設得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)得惟一的一個圈. (6)(1). 只需證明G連通，這是顯然的. 第4頁/共30頁)(2)()1(2xnxvdni 解得 x 2. 定理10.2 設T是n階非平凡的無向樹，則T 中至少有兩片樹葉. 無向樹的性質證 設 T 有 x 片樹葉，由握手定理及定理10.1可知，例1 已知無向樹T中有1個3度頂點，2個2度頂點，其余頂點全是

4、樹葉，試求樹葉數(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度頂點各1個，其余頂 點的度數(shù)均為4，求T的階數(shù)n，并畫出滿足要求的所有非同 構的無向樹. 例題解 設T的階數(shù)為n, 則邊數(shù)為n1，4度頂點的個數(shù)為n7. 由握手定理, 2m = 2(n1) = 51+21+31+4(n7),解出n = 8，4度頂點為1個. 第6頁/共30頁710.2 生成樹定義10.2 如果無向圖G的生成子圖T是樹，則稱T是G的生成樹. 設T

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

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

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

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

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

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

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

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

13、正則樹的周游方式： 中序行遍法. 訪問次序為：左子樹、根、右子樹 前序行遍法. 訪問次序為：根、左子樹、右子樹 后序行遍法. 訪問次序為：左子樹、右子樹、根例 用中序, 前序, 后序行遍法訪問的結果分別為： 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元運算和1元運算的算式: 每個分支點 放一個運算符, 其運算對象是以它的兒子為樹根的子樹所表 示的子算式. 規(guī)定運算對象的排列順序, 如被除數(shù)、被減數(shù)放 在左邊所有的變量和常量都放在樹葉上.例 (b+(c+d)a)(ef)

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

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

16、T至少 有k片樹葉. 證 設T有s片樹葉，由于(T) k，有sksnvdnmnii )1(2)(2221解得s k. 練習2第25頁/共30頁263設G為n 階無向簡單圖，n5，證明G 或 中必含圈.G練習3證一. 反證法. 否則G與 的各連通分支都是樹. 設G與 的連通分支的頂點數(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是森林, 則mn-1, 矛盾.Gnnnm 4)1(練習3第27頁/共30頁284畫出基圖為圖所示無向樹的所有非同構的根樹 練習4解 以a, b, c, d為根的根樹同構, 選a為根, 如(1); 以 e, g 為根的根樹同構，取 g為根，如(2)； 以 f 為根，如(3) . (1) (2) (3) 第28頁/共30頁295設T 是正則2叉樹，T 有t 片樹葉