北大離散數(shù)學(xué)chap-wenkub.com
2024-08-12 04:01 本頁(yè)面
【正文】 例 求帶權(quán)為 ， 1， 2， ， 4， 5， 6的最優(yōu) 二元樹(shù)，并求 ()WT 。 T m t證明： ，其中 22mt?? 2t? 。 解： 設(shè)有 片樹(shù)葉， 1n依握手定理及樹(shù)的性質(zhì) 1mn?? ， 1 2 31 2 32 3 21kkn n n k n mn n n n m? ? ? ? ??? ? ? ? ? ? ??得 解得： 1 3 42 ( 2 ) 2kn n n k n? ? ? ? ? ?解： 不一定， 反例： 例 一個(gè)有向圖 ，僅有一個(gè)頂點(diǎn)入度為 0， D其余頂點(diǎn)的入度均為 1， 一定是根樹(shù)嗎？ D例 設(shè) 為二元正則樹(shù)， 為邊數(shù)， 為樹(shù)葉數(shù)。這個(gè)命題正確嗎？ 解： 命題不正確。 r 元樹(shù)， r 元正則樹(shù)， r 元有序樹(shù) (2) 利用 算法求最優(yōu)二元樹(shù)。 有向樹(shù)；根樹(shù)；樹(shù)根，內(nèi)點(diǎn)，樹(shù)葉，分支點(diǎn)； 頂點(diǎn)的層數(shù)與樹(shù)高；有序樹(shù)，正則樹(shù)，完全樹(shù)； 最優(yōu)二元樹(shù)。 (3) 根據(jù)握手定理及樹(shù)的某些性質(zhì)，求頂點(diǎn)數(shù)或 某些頂點(diǎn)的度數(shù)。 一、無(wú)向樹(shù)及生成樹(shù)。 無(wú)向樹(shù)；樹(shù)葉，分支點(diǎn)；森林；平凡樹(shù)； 生成樹(shù)，最小生成樹(shù)。 (了解 ) 最優(yōu)元樹(shù)的用途之一是求最佳前綴碼。 (了解 ) 最優(yōu) 2元樹(shù)的用途之一是求最佳前綴碼。 34184116519解： 其實(shí) ()WT 等于 T 的 各分支點(diǎn)的權(quán)之和，即 ( ) 4 8 1 1 1 9WT ? ? ? ?42?最優(yōu)樹(shù)是不唯一的，但 H uffm an 算法得到的樹(shù) 一定是最優(yōu)樹(shù)。 (2) 求最優(yōu) 2元樹(shù)的算法。 記為 1( ) ( )tiiiW T w L w?? ?例 下圖中的 都是帶權(quán) 1， 3， 4， 5， 6 1 2 3,T T T的 2元樹(shù)，求 1()WT， 2()WT 3()WT， 。 r 元完全正則樹(shù) 的層數(shù)相同 (等于樹(shù)高 )。 rr 元正則樹(shù) —— 每個(gè)分支點(diǎn)恰有 個(gè)兒子的根樹(shù)。 T8v7v6v5v4v3v2v1v例 3v39。 一棵根樹(shù)可以看成一棵 家族樹(shù) 。 根樹(shù)的頂點(diǎn) 樹(shù)葉 (入度為 1，出度為 0) 分支點(diǎn) 樹(shù)根 (入度為 0) 內(nèi)點(diǎn) (入度為 1， 出度大于 0) 例 例 樹(shù)高。 重點(diǎn)： 有向樹(shù)及根樹(shù)的定義， 家族樹(shù)，有序樹(shù)， 元樹(shù)的概念， r最優(yōu) 2元樹(shù)的概念及哈夫曼 ()H u ffm a n算法。T例 求以下連通圖的最小生成樹(shù) 及 T()WT。T例 求以下連通圖的最小生成樹(shù) 及 T()WT。 設(shè) 階無(wú)向連通帶權(quán)圖 n,G V E W?中有 m 條 邊 12, , , me e e，它們帶的權(quán)分別為 12, , , ma a a， 不妨設(shè) 12 ma a a? ? ?， (1) 取 1e在 T 中 (非環(huán)，若 1e為環(huán)，則棄 1e)。 對(duì)于有向圖或無(wú)向圖 的每條邊附加一個(gè)實(shí)數(shù) G()we ，則稱 ()we 為邊 e 上的 權(quán) ， G 連同附加在 各邊上的實(shí)數(shù)稱為 帶權(quán)圖 ，記為 ,G V E W?。T 是 T 的余樹(shù)， 則 39。 例 (3 )( 2)( 1 )上圖中， (2)是 (1)的生成樹(shù)， (3)是 (
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1