離散數(shù)學(xué)——樹PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1離散數(shù)學(xué)離散數(shù)學(xué)樹樹第1頁/共41頁第2頁/共41頁得圖中得到唯一的一個(gè)含新邊的圈。第3頁/共41頁如果G是樹，則G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑。存在性。 由G的連通性及定理14.5的推論（在n階圖G中，若從頂點(diǎn)vi到vj(vivj)存在通路，則vi到vj 一定存在長度小于等于n-1的初級(jí)通路(路徑)）可知，u,vV，u與v之間存在路徑。唯一性（反證法）。 若路徑不是唯一的，設(shè)1與2都是u到v的路徑，易知必存在由1和2上的邊構(gòu)成的回路，這與G中無回路矛盾。第4頁/共41頁如果G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑，則G中無回路且mn-1。首先證明 G中無回路。若G中存在關(guān)聯(lián)某頂點(diǎn)v的環(huán)

2、，則v到v存在長為0和1的兩條路經(jīng)(注意初級(jí)回路是路徑的特殊情況)，這與已知矛盾。若G中存在長度大于或等于2的圈，則圈上任何兩個(gè)頂點(diǎn)之間都存在兩條不同的路徑，這也與已知矛盾。第5頁/共41頁如果G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑，則G中無回路且mn-1。其次證明 mn-1。（歸納法）n1時(shí)，G為平凡圖，結(jié)論顯然成立。設(shè)nk(k1)時(shí)結(jié)論成立，當(dāng)n=k+1時(shí)，設(shè)e(u,v)為G中的一條邊，由于G中無回路，所以G-e為兩個(gè)連通分支G1、G2。設(shè)ni、mi分別為Gi中的頂點(diǎn)數(shù)和邊數(shù)，則nik ，i1,2，由歸納假設(shè)可知mini-1，于是mm1+m2+1n1-1+n2-1+1n1+n2-1n-1。第6

3、頁/共41頁只需證明G是連通的。（采用反證法）假設(shè)G是不連通的，由s(s2)個(gè)連通分支G1,G2,Gs組成，并且Gi中均無回路，因而Gi全為樹。由(1)(2)(3)可知，mini-1。于是，由于s2，與mn-1矛盾。111(1)sssiiiiiimmnnsns如果G中無回路且mn-1，則G是連通的且mn -1。第7頁/共41頁只需證明G中每條邊均為橋。 eE，均有|E(G-e)|n-1-1n-2，由習(xí)題十四題49（若G是n階m條邊的無向連通圖，則mn-1）可知，G-e已不是連通圖，所以，e為橋。 第8頁/共41頁因?yàn)镚中每條邊均為橋，刪掉任何邊，將使G變成不連通圖，所以，G中沒有回路，也即G中

4、無圈。又由于G連通，所以G為樹，由(1) (2)可知，u,vV，且uv，則u與v之間存在唯一的路徑，則(u,v)（(u,v)為加的新邊）為G中的圈，顯然圈是唯一的。第9頁/共41頁只需證明G是連通的。u,vV，且uv，則新邊(u,v)G產(chǎn)生唯一的圈C，顯然有C -(u,v)為G中u到v的通路，故uv，由u,v的任意性可知，G是連通的。第10頁/共41頁設(shè)T有x片樹葉，由握手定理及定理16.1可知，證明2(1)( )2()ind vxnx由上式解出x2。第11頁/共41頁(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)

5、 1，1，2，2，2，2(4)對(duì)應(yīng)兩棵非同構(gòu)的樹，在一棵樹中兩個(gè)2度頂點(diǎn)相鄰，在另一棵樹中不相鄰，其他情況均能畫出一棵非同構(gòu)的樹。第12頁/共41頁第13頁/共41頁可知d(vj)2，j4,5,6。于是Ti 的度數(shù)列為1，1，1，2，2，2，3由度數(shù)列可知，Ti中有一個(gè)3度頂點(diǎn)vi，vi的鄰域N(vi)中有3個(gè)頂點(diǎn)，這3個(gè)頂點(diǎn)的度數(shù)列只能為以下三種情況之一：1,1,21,2,22,2,2設(shè)它們對(duì)應(yīng)的樹分別為T1，T2，T3。此度數(shù)列只能產(chǎn)生這三棵非同構(gòu)的7階無向樹。第14頁/共41頁第15頁/共41頁13+22+x解出x3，故T有3片樹葉。故T的度數(shù)應(yīng)為1、1、1、2、2、3。第16頁/共41

6、頁例題 已知無向樹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è)。故T的度數(shù)列為1、1、1、1、1、2、3、4。第17頁/共41頁小節(jié)結(jié)束第18頁/共41頁eeE(G)，若eE(T)。（5）生成樹T的余樹導(dǎo)出子圖GE(G)-E(T) 。記作T第19頁/共41頁T第20頁/共41頁定理16.3 無向圖G具有生成樹當(dāng)且僅當(dāng)G連通。證明必要性，顯然。充分性（破圈法）。 若G中無回路

7、，G為自己的生成樹。 若G中含圈，任取一圈，隨意地刪除圈上的一條邊，若再有圈再刪除圈上的一條邊，直到最后無圈為止。易知所得圖無圈(當(dāng)然無回路)、連通且為G的生成子圖，所以為G的生成樹。第21頁/共41頁有環(huán)（否則，可以將所有的環(huán)先刪去），將m條邊按權(quán)從小到大排序：e1,e2,em。(2)取e1在T中。(3)依次檢查e2,em，若ej(j2)與已在T中的邊不構(gòu)成回路，取ej也在T中，否則棄去ej。(4)算法停止時(shí)得到的T為G的最小生成樹為止。第22頁/共41頁W(T1)6 W(T2)12 第23頁/共41頁解答最小生成樹 W(T)=38小節(jié)結(jié)束第24頁/共41頁第25頁/共41頁(6) 頂點(diǎn)v的

8、層數(shù)從樹根到v的通路長度(7) 樹高T中層數(shù)最大頂點(diǎn)的層數(shù)(8) 根樹平凡樹第26頁/共41頁樹葉8片內(nèi)點(diǎn) 6個(gè)分支點(diǎn) 7個(gè)高度 5第27頁/共41頁。定義16.8 設(shè)v為根樹T中任意一頂點(diǎn)，稱v及其后代的導(dǎo)出子圖為以v為根的根子樹。第28頁/共41頁r叉正則有序樹r叉正則樹是有序的nr叉完全正則樹樹葉層數(shù)均為樹高的r叉正則樹r叉完全正則有序樹r叉完全正則樹是有序的第29頁/共41頁定義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叉樹稱為最

9、優(yōu)2叉樹。1( )( )tiiiW twl v第30頁/共41頁W(T1)=22+22+33+53+32=38W(T2)=34+54+33+22+21=47W(T3)=33+33+52+22+22=36 第31頁/共41頁 重復(fù) ，直到形成t1個(gè)分支點(diǎn)、t片樹葉為止。第32頁/共41頁解答W(T)=38 第33頁/共41頁j互不為前綴，則稱A為前綴碼。若i(i=1,2,m)中只出現(xiàn)0與1兩個(gè)符號(hào)，則稱A為二元前綴碼。(2)如何產(chǎn)生二元前綴碼？定理16.6 由一棵給定的2叉正則樹，可以產(chǎn)生唯一的一個(gè)二元前綴碼。第34頁/共41頁11, 011, 0100, 0101。第35頁/共41頁出現(xiàn)的八進(jìn)

10、制數(shù)字需要多少個(gè)二進(jìn)制數(shù)字？若用等長的（長為3）的碼字傳輸需要多少個(gè)二進(jìn)制數(shù)字？第36頁/共41頁解答 以100乘各頻率為權(quán)，并按小到大排列，得w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25。產(chǎn)生的最優(yōu)樹如下。 0 01 1 11 2 001 3 1004 1015 00016 000007 00001傳100個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字所需二進(jìn)制數(shù)字個(gè)數(shù)W(T)=285 ，所以傳10n(n2)個(gè)所用二進(jìn)制數(shù)字應(yīng)為2.8510n。用等長碼（長為3）應(yīng)該用310n個(gè)數(shù)字。第37頁/共41頁q由于在每一步選擇兩個(gè)最小的權(quán)的選法不唯一。q因?yàn)閮蓚€(gè)權(quán)對(duì)應(yīng)的頂點(diǎn)所放左右位置不同。畫出的最優(yōu)樹可能不同，最佳