北大離散數(shù)學(xué)chap-全文預(yù)覽
【正文】 。 運用。 (2) 畫頂點數(shù)為 6n? 的所有非同構(gòu)的無向樹。 基本概念。 求最佳前綴碼。 1 4 0求最佳前綴碼。 34184116519解： ( ) ( 1 3 ) 3 (4 5 6 ) 2 4 2WT ? ? ? ? ? ? ? ?其實 ()WT 等于 T 的 各分支點的權(quán)之和，即 ( ) 4 8 1 1 1 9WT ? ? ? ?42?例 求帶權(quán) 1, 3, 4, 5, 6的最優(yōu) 2元樹 及 T ()WT 。 解： 3( ) ( 1 3 ) 3 (6 4 5 ) 2 4 2WT ? ? ? ? ? ? ? ?3T6 54313 1 2( ) ( ) ( )W T W T W T??但不能判定 3T是最優(yōu) 2元樹。 —— 中每片樹葉所帶權(quán)與其層高 T乘積的和。 有序樹 —— 每一層上都規(guī)定次序的根樹。 元樹 r —— 每個分支點至多有 個兒子的根樹。 樹 的 根子樹 T —— T 的非樹根的頂點 a 及其 后代導(dǎo)出的子圖。 如例 1(2)中， 家族樹。 根樹 ： 一棵非平凡的有向樹，如果有一個 頂點的入度為 0，其余頂點的入度均為 1，則 稱此有向樹為 根樹 。 第二節(jié) 根樹及其應(yīng)用 內(nèi)容： 有向樹，根樹，最優(yōu)二元樹。 ( 2 )9877643 21105abcdef123572( ) 1 8WT ?753 21fedcba解： 239。 ( 1 )6643 215555fabc de123541( ) 1 5WT ?54321bc defa解： 139。 求最小生成樹的方法 K ru skal—— 避圈法 。 G最小生成樹。 設(shè) ,G V E?為連通圖， Vn?， Em?， (1) 至少有一棵生成樹， G(2) 1mn?? ， (3) 設(shè) 是 T G 的生成樹， 39。 樹枝 弦 余樹 —— G T在 中的邊， —— G T不在 中的邊， —— T 的所有的弦的集合的導(dǎo)出子圖。 解： 所要畫的樹有 6個頂點，則邊數(shù)為 5，因此 6個頂點的度數(shù)之和為 10，可以產(chǎn)生以下五種 度數(shù)序列： (5) 1 1 2 2 2 26T例 (1) 一棵樹有 7片葉， 3個 3度頂點，其余都 是 4度頂點，求 4度頂點多少個？ 解： 設(shè)有 個 4度頂點，則頂點數(shù) x 73 x?? ， 邊數(shù) 7 3 1x? ? ? ， 由握手定理， 4 3 3 7 2 ( 7 3 1 )xx? ? ? ? ? ? ?， 解得 1x? ， 故這棵樹有 1個 4度頂點。 解： 所要畫的樹有 6個頂點，則邊數(shù)為 5，因此 6個頂點的度數(shù)之和為 10，可以產(chǎn)生以下五種 度數(shù)序列： (1) 1 1 1 1 1 51T例 畫出所有的 6個頂點的非同構(gòu)的樹。 (1) 樹中頂點數(shù)與邊數(shù)的關(guān)系： 1nm?? 。 樹的六個等價定義。 G(2) 的每對頂點間具有唯一的路徑。 T平凡樹 —— 平凡圖。 本章中所談回路均指簡單回路或初級回路。 重點： 無向樹的定義 (包括等價定義 )， 無向樹的性質(zhì)，
法律信息相關(guān)推薦
鄂ICP備17016276號-1