正文內容

北大離散數學chap(編輯修改稿)

2025-09-01 04:01 本頁面

　

【文章內容簡介】的最小生成樹可能不唯一， G但 G 的不同最小生成樹權的值一樣。第二節根樹及其應用內容：有向樹，根樹，最優二元樹。重點：有向樹及根樹的定義，家族樹，有序樹，元樹的概念， r最優 2元樹的概念及哈夫曼 ()H u ffm a n算法。一、根樹。有向樹：一個有向圖，若略去有向邊的 D方向所得的無向圖為一棵無向樹，則稱 D 為有向樹。根樹：一棵非平凡的有向樹，如果有一個頂點的入度為 0，其余頂點的入度均為 1，則稱此有向樹為根樹。根樹的頂點樹葉 (入度為 1，出度為 0) 分支點樹根 (入度為 0) 內點 (入度為 1，出度大于 0) 例例樹高。的層數 v —— 從樹根到頂點 v 的通路長度，記 ()lv 。樹高 —— 樹中頂點的最大層數，記 ()hT 。如例 1(2)中，家族樹。一棵根樹可以看成一棵家族樹。 (1) 若頂點鄰接到頂點，則稱為 a b b a 的兒子，為 a b 的父親， (2) 若 a,bc 同為的兒子，則稱 ,bc 為兄弟， (3) 若 ad? ，而可達 a ，則稱 d a 為 d 的祖先， d 為 a 的后代。根子樹。樹的根子樹 T —— T 的非樹根的頂點 a 及其后代導出的子圖。 T8v7v6v5v4v3v2v1v例 3v39。T8v7v6v5v4v二、元樹。 r 有序樹 —— 每一層上都規定次序的根樹。元樹 r —— 每個分支點至多有個兒子的根樹。 rr 元正則樹 —— 每個分支點恰有個兒子的根樹。 rr 元有序樹 r 元有序正則樹二、元樹。 rr 元有序完全正則樹注意： 2元有序正則樹是最重要的一種 r 元樹。有序樹 —— 每一層上都規定次序的根樹。 r 元完全正則樹的層數相同 (等于樹高 )。 —— 元正則樹，且所有樹葉 r例 (1 )22111( 2 )2221112元有序樹 2元有序正則樹 (3 )2 22111例 2元有序完全正則樹最優 2元樹。 (1) 的權 T最優 2元樹 —— 權最小的 2元樹。 —— 中每片樹葉所帶權與其層高 T乘積的和。記為 1( ) ( )tiiiW T w L w?? ?例下圖中的都是帶權 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 ? ? ? ? ? ? ? ?例下圖中的都是帶權 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例下圖中的都是帶權 1， 3， 4， 5， 6

點擊復制文檔內容

法律信息相關推薦

北大離散數學chap(編輯修改稿)

智能控制chap-資料下載頁

離散數學第101陳瑜-資料下載頁

離散數學—圖論1216版-資料下載頁

7-3離散數學-資料下載頁

離散數學第7講-資料下載頁

離散數學第2章-資料下載頁

離散數學作業-資料下載頁

離散數學總結-資料下載頁

離散數學—圖論126版-資料下載頁

離散數學第151156陳瑜-資料下載頁

離散數學總結-資料下載頁

離散數學(對偶和范式)-資料下載頁

離散數學之圖論ppt課件-資料下載頁

離散數學自學-資料下載頁

離散數學例題-資料下載頁

北大離散數學chap-免費閱讀

北大離散數學chap(存儲版)

北大離散數學chap-文庫吧在線文庫

北大離散數學chap(完整版)

北大離散數學chap(更新版)