北大離散數(shù)學(xué)chap(編輯修改稿)
2024-09-01 04:01 本頁面
【文章內(nèi)容簡介】 的最小生成樹可能不唯一， G但 G 的不同最小生成樹權(quán)的值一樣。 第二節(jié) 根樹及其應(yīng)用 內(nèi)容： 有向樹，根樹，最優(yōu)二元樹。 重點(diǎn)： 有向樹及根樹的定義， 家族樹，有序樹， 元樹的概念， r最優(yōu) 2元樹的概念及哈夫曼 ()H u ffm a n算法。 一、根樹。 有向樹 ： 一個有向圖 ，若略去有向邊的 D方向所得的無向圖為一棵無向樹，則稱 D 為 有向樹 。 根樹 ： 一棵非平凡的有向樹，如果有一個 頂點(diǎn)的入度為 0，其余頂點(diǎn)的入度均為 1，則 稱此有向樹為 根樹 。 根樹的頂點(diǎn) 樹葉 (入度為 1，出度為 0) 分支點(diǎn) 樹根 (入度為 0) 內(nèi)點(diǎn) (入度為 1， 出度大于 0) 例 例 樹高。 的層數(shù) v —— 從樹根到頂點(diǎn) v 的通路 長度，記 ()lv 。 樹高 —— 樹中頂點(diǎn)的最大層數(shù)，記 ()hT 。 如例 1(2)中， 家族樹。 一棵根樹可以看成一棵 家族樹 。 (1) 若頂點(diǎn) 鄰接到頂點(diǎn) ，則稱 為 a b b a 的兒子， 為 a b 的父親， (2) 若 a,bc 同為 的兒子，則稱 ,bc 為 兄弟 ， (3) 若 ad? ，而 可達(dá) a ，則稱 d a 為 d 的 祖先 ， d 為 a 的 后代 。 根子樹。 樹 的 根子樹 T —— T 的非樹根的頂點(diǎn) a 及其 后代導(dǎo)出的子圖。 T8v7v6v5v4v3v2v1v例 3v39。T8v7v6v5v4v二、 元樹。 r 有序樹 —— 每一層上都規(guī)定次序的根樹。 元樹 r —— 每個分支點(diǎn)至多有 個兒子的根樹。 rr 元正則樹 —— 每個分支點(diǎn)恰有 個兒子的根樹。 rr 元有序樹 r 元有序正則樹 二、 元樹。 rr 元有序完全正則樹 注意： 2元有序正則樹是最重要的一種 r 元樹。 有序樹 —— 每一層上都規(guī)定次序的根樹。 r 元完全正則樹 的層數(shù)相同 (等于樹高 )。 —— 元正則樹，且所有樹葉 r例 (1 )22111( 2 )2221112元有序樹 2元有序正則樹 (3 )2 22111例 2元有序完全正則樹 最優(yōu) 2元樹。 (1) 的 權(quán) T最優(yōu) 2元樹 —— 權(quán)最小的 2元樹。 —— 中每片樹葉所帶權(quán)與其層高 T乘積的和。 記為 1( ) ( )tiiiW T w L w?? ?例 下圖中的 都是帶權(quán) 1， 3， 4， 5， 6 1 2 3,T T T的 2元樹，求 1()WT， 2()WT 3()WT， 。 654311T解： 1( ) (6 3 ) 3 ( 4 5 1 ) 2 4 7WT ? ? ? ? ? ? ? ?例 下圖中的 都是帶權(quán) 1， 3， 4， 5， 6 1 2 3,T T T的 2元樹，求 1()WT， 2()WT 3()WT， 。 解： 2( ) ( 1 6 ) 4 5 3 4 2 3 1 5 4WT ? ? ? ? ? ? ? ? ? ?2T65431例 下圖中的 都是帶權(quán) 1， 3， 4， 5， 6
法律信息相關(guān)推薦
鄂ICP備17016276號-1