北大離散數(shù)學(xué)chap(存儲版)
【正文】 n個(gè)頂點(diǎn)的 度數(shù)為 3， 例 設(shè) 為二元正則樹， 為邊數(shù)， 為樹葉數(shù)。 10 .53 .5273 .5136 54922解： ( ) ( 0 . 5 1 ) 5WT ? ? ?2 4 3 . 5 3? ? ? ?( 6 4 5 ) 2? ? ? ?56?結(jié) 束 語 課 程 結(jié) 束 ， 謝 謝 大 家 ！ 。 T m t證明： ，其中 22mt?? 2t? 。 反例： 例 設(shè)連通圖 12,GG如下圖所示，分別求出它 們的所有非同構(gòu)的生成樹。 二、根樹及其應(yīng)用。 基本概念。 為了使編碼在使用中既快速又準(zhǔn)確，可以用求 最優(yōu) 2元樹的 H uffm an 算法解決這個(gè)問題。 例 (1) 求帶權(quán)為 2, 3, 5, 7, 8, 9的最優(yōu) 2元樹 T ， 532105199158734解： ( ) _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _WT ?(2) 5 1 0 1 9 1 5 3 4 8 3? ? ? ? ?例 (1) 求帶權(quán)為 2, 3, 5, 7, 8, 9的最 2優(yōu)元樹 T ， 532105199158734解： (3) ( ) _ _ _ _hT ? 4例 (1) 求帶權(quán)為 2, 3, 5, 7, 8, 9的最 2優(yōu)元樹 T ， 532105199158734解： (4) T 有 ___片樹葉。 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， 。 rr 元有序樹 r 元有序正則樹 二、 元樹。 (1) 若頂點(diǎn) 鄰接到頂點(diǎn) ，則稱 為 a b b a 的兒子， 為 a b 的父親， (2) 若 a,bc 同為 的兒子，則稱 ,bc 為 兄弟 ， (3) 若 ad? ，而 可達(dá) a ，則稱 d a 為 d 的 祖先 ， d 為 a 的 后代 。 一、根樹。 ( 1 )6643 215555fabc de1( 39。 最小生成樹 —— 各邊權(quán)和最小的生成樹。 注意： (1) 生成樹不唯一， (2) 余樹不一定是樹。 解： 所要畫的樹有 6個(gè)頂點(diǎn)，則邊數(shù)為 5，因此 6個(gè)頂點(diǎn)的度數(shù)之和為 10，可以產(chǎn)生以下五種 度數(shù)序列： (3) 1 1 1 1 3 33T例 畫出所有的 6個(gè)頂點(diǎn)的非同構(gòu)的樹。 (6) 是連通的，但刪除任何一條邊后，就不 G連通了。 T???樹葉——度數(shù)為1的頂點(diǎn)樹 的頂點(diǎn)分支點(diǎn)——度數(shù)大于1的頂點(diǎn)例 ( 1 )fceadb( 2 )( 3 )例 (4)樹的六個(gè)等價(jià)定義。第九章 樹 第一節(jié) 無向樹及生成樹 內(nèi)容： 無向樹，生成樹。 森林 —— 連通分支數(shù)大于等于 2，且每個(gè)連通 分支都是樹的無向圖。 (5) 無回路，但在 G 中任兩個(gè)不相鄰的頂點(diǎn) G之間增加一條邊，就形成唯一的一條初級 回路。 解： 所要畫的樹有 6個(gè)頂點(diǎn)，則邊數(shù)為 5，因
法律信息相關(guān)推薦
鄂ICP備17016276號-1