離散數(shù)學(xué)——樹(shù)(編輯修改稿)
2024-09-01 10:25 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 T3。此度數(shù)列只能產(chǎn)生這三棵非同構(gòu)的 7階無(wú)向樹(shù)。 例 例題 例題 已知無(wú)向樹(shù) T中 ， 有 1個(gè) 3度頂點(diǎn) ， 2個(gè) 2度頂點(diǎn) ， 其余頂點(diǎn)全是樹(shù)葉 ， 試求樹(shù)葉數(shù) ， 并畫(huà)出滿足要求的非同構(gòu)的無(wú)向樹(shù) 。 解答 設(shè)有 x片樹(shù)葉 ， 于是結(jié)點(diǎn)總數(shù)為 n＝ 1+2+x＝ 3+x 由握手定理和樹(shù)的性質(zhì) m＝ n?1可知 ， 2m＝ 2(n?1)＝ 2 (2+x) ＝ 1 3+2 2+x 解出 x＝ 3， 故 T有 3片樹(shù)葉。 故 T的度數(shù)應(yīng)為 3。 例題 已知無(wú)向樹(shù) T有 5片樹(shù)葉， 2度與 3度頂點(diǎn)各 1個(gè)，其余頂點(diǎn)的度數(shù)均為 4， 求 T的階數(shù) n， 并畫(huà)出滿足要求的所有非同構(gòu)的無(wú)向樹(shù)。 解答 設(shè) T的階數(shù)為 n, 則邊數(shù)為 n?1， 4度頂點(diǎn)的個(gè)數(shù)為 n?7。 由握手定理得 2m = 2(n?1) = 5?1+2?1+3?1+4(n?7) 解出 n = 8， 所以 4度頂點(diǎn)為 1個(gè) 。 故 T的度數(shù)列為 4。 例題 小節(jié)結(jié)束 例題 生成樹(shù) 定義 設(shè) G為無(wú)向圖， （ 1） T為 G的 樹(shù) — T是 G的子圖并且是樹(shù) 。 （ 2） T為 G的 生成樹(shù) — T是 G的生成子圖并且是樹(shù) 。 （ 3） e為 T的 樹(shù)枝 — 設(shè) T是 G的生成樹(shù) ， ?e∈ E(G)， 若 e∈ E(T)。 （ 4） e為 T的 弦 — 設(shè) T是 G的生成樹(shù) ， ?e∈ E(G)， 若 e?E(T)。 （ 5） 生成樹(shù) T的 余樹(shù) — 導(dǎo)出子圖 G[E(G)E(T)] 。 記作 T注意： 不一定連通，也不一定不含回路。 T說(shuō)明 定理 無(wú)向圖 G具有生成樹(shù)當(dāng)且僅當(dāng) G連通 。 證明 必要性 ， 顯然 。 充分性 （ 破圈法 ） 。 若 G中無(wú)回路 ， G為自己的生成樹(shù) 。 若 G中含圈 ， 任取一圈 ， 隨意地刪除圈上的一條邊 ， 若再有圈再刪除圈上的一條邊 ， 直到最后無(wú)圈為止 。 易知所得圖無(wú)圈 (當(dāng)然無(wú)回路 )、 連通且為 G的生成子圖 ， 所以為 G的生成樹(shù) 。 生成樹(shù)的存在條件 最小生成樹(shù) 定義 設(shè) T是無(wú)向連通帶權(quán)圖 G＝ V,E,W的一棵生成樹(shù) ， T的各邊權(quán)之和稱為 T的權(quán) ， 記作 W(T)。 G的所有生成樹(shù)中權(quán)最小的生成樹(shù)稱為 G的 最小生成樹(shù) 。 求最小生成樹(shù)的算法 （ 避圈法 (Kruskal)） (1)設(shè) n階無(wú)向連通帶權(quán)圖 G＝ V,E,W有 m條邊 。 不妨設(shè) G中沒(méi)有環(huán) （ 否則 ， 可以將所有的環(huán)先刪去 ） ， 將 m條邊按權(quán)從小到大排序： e1,e2,… ,em。 (2)取 e1在 T中 。 (3)依次檢查 e2,… ,em ， 若 ej(j≥ 2)與已在 T中的邊不構(gòu)成回路 ，取 ej也在 T中 ， 否則棄去 ej。 (4)算法停止時(shí)得到的 T為 G的最小生成樹(shù)為止。 例 例 求下圖所示兩個(gè)圖中的最小生成樹(shù)。 W(T1)＝ 6 W(T2)＝ 12 例題 例如 求所示圖的一棵最小生成樹(shù) 。 解答 最小生成樹(shù) W(T)=38 小節(jié)結(jié)束 根樹(shù)及其應(yīng)用
外語(yǔ)相關(guān)推薦
鄂ICP備17016276號(hào)-1