北大離散數(shù)學(xué)chap-文庫(kù)吧資料
2024-08-18 04:01本頁(yè)面
【正文】 tw w w w?從 中選兩個(gè)最小的，連接 得一分支點(diǎn)， ()c 重復(fù) ()b 。 解： 3( ) ( 1 3 ) 3 (6 4 5 ) 2 4 2WT ? ? ? ? ? ? ? ?3T6 54313 1 2( ) ( ) ( )W T W T W T??但不能判定 3T是最優(yōu) 2元樹(shù)。 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元樹(shù)，求 1()WT， 2()WT 3()WT， 。 —— 中每片樹(shù)葉所帶權(quán)與其層高 T乘積的和。 —— 元正則樹(shù)，且所有樹(shù)葉 r例 (1 )22111( 2 )2221112元有序樹(shù) 2元有序正則樹(shù) (3 )2 22111例 2元有序完全正則樹(shù) 最優(yōu) 2元樹(shù)。 有序樹(shù) —— 每一層上都規(guī)定次序的根樹(shù)。 rr 元有序樹(shù) r 元有序正則樹(shù) 二、 元樹(shù)。 元樹(shù) r —— 每個(gè)分支點(diǎn)至多有 個(gè)兒子的根樹(shù)。T8v7v6v5v4v二、 元樹(shù)。 樹(shù) 的 根子樹(shù) T —— T 的非樹(shù)根的頂點(diǎn) a 及其 后代導(dǎo)出的子圖。 (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(2)中， 家族樹(shù)。 的層數(shù) v —— 從樹(shù)根到頂點(diǎn) v 的通路 長(zhǎng)度，記 ()lv 。 根樹(shù) ： 一棵非平凡的有向樹(shù)，如果有一個(gè) 頂點(diǎn)的入度為 0，其余頂點(diǎn)的入度均為 1，則 稱此有向樹(shù)為 根樹(shù) 。 一、根樹(shù)。 第二節(jié) 根樹(shù)及其應(yīng)用 內(nèi)容： 有向樹(shù)，根樹(shù)，最優(yōu)二元樹(shù)。 ( 2 )9877643 21105abcdef2( 39。 ( 2 )9877643 21105abcdef123572( ) 1 8WT ?753 21fedcba解： 239。 ( 1 )6643 215555fabc de1( 39。 ( 1 )6643 215555fabc de123541( ) 1 5WT ?54321bc defa解： 139。 (2) 若 不與 2e 1e構(gòu)成回路，取 2e在 T 中，否則棄 2e，再查 3e，繼續(xù)這一過(guò)程，直到形成樹(shù)為止。 求最小生成樹(shù)的方法 K ru skal—— 避圈法 。 最小生成樹(shù) —— 各邊權(quán)和最小的生成樹(shù)。 G最小生成樹(shù)。T 中有 1mn?? 條邊。 設(shè) ,G V E?為連通圖， Vn?， Em?， (1) 至少有一棵生成樹(shù)， G(2) 1mn?? ， (3) 設(shè) 是 T G 的生成
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1