第五章圖論樹(shù).ppt

第五章圖論樹(shù) 主要內(nèi)容 樹(shù)重點(diǎn) 生成樹(shù) 最優(yōu)樹(shù) 最小生成樹(shù)難點(diǎn) 最小生成樹(shù) 樹(shù) 一 樹(shù)的定義1 連通且無(wú)回路的無(wú)向圖稱(chēng)為樹(shù) 用T表示 T中的1度結(jié)點(diǎn)稱(chēng)為樹(shù)葉 大于1度的結(jié)點(diǎn)稱(chēng)為分支點(diǎn) 孤點(diǎn)稱(chēng)為平凡樹(shù) 僅由樹(shù)組成的無(wú)向圖稱(chēng)為森林 2 樹(shù)的性質(zhì) 連通且無(wú)回路 E V 1 增加任意一條邊必出現(xiàn)回路 刪除任意一條邊必不連通 每對(duì)結(jié)點(diǎn)間僅有一條通路 3 任何非平凡樹(shù)中至少有2片樹(shù)葉 二 生成樹(shù)1 生成樹(shù)若圖G的生成子圖是一棵樹(shù) 則稱(chēng)此樹(shù)是G的生成樹(shù) 2 樹(shù)的補(bǔ)圖G中不屬于生成樹(shù)T的邊的集合稱(chēng)為樹(shù)T的補(bǔ) 3 生成樹(shù)的求法一般可用破圈法做 即把圖G中的回路去掉一條邊 使它不再是回路 如此做下去 直到恰好把所有的回路都破壞掉 就得到了生成樹(shù) 用破圈法一共要去掉條邊 例題 設(shè)G 是有p個(gè)結(jié)點(diǎn) s條邊的連通圖 則從G中刪去條邊 才能確定G的一棵生成樹(shù) 解 設(shè)要?jiǎng)h去k條邊 例題 設(shè)G是有6個(gè)結(jié)點(diǎn)的完全圖 從G中刪去條邊則能得到樹(shù) A 6B 9C 10D 15解 G是有6個(gè)結(jié)點(diǎn)的完全圖 G中共有6 5 2 15條邊 要使G成為樹(shù) G中只應(yīng)留下5條邊 故應(yīng)刪去10條邊 選C C 4 最小生成樹(shù)在帶權(quán)圖G中所生成的總權(quán)數(shù)最小的生成樹(shù)稱(chēng)為最小生成樹(shù) 5 最小生成樹(shù)的求法選取權(quán)數(shù)最大的邊所在的回路 去掉其中權(quán)數(shù)最大的邊 如此做下去 直到求出生成樹(shù)為止 這樣求出的生成樹(shù)一定是最小生成樹(shù) 還有一種方法稱(chēng)為克魯斯特爾算法 先去掉所有的邊 然后從權(quán)數(shù)最小的邊的開(kāi)始 從小到大逐步選取 如果所選取的邊和已選取的邊構(gòu)成了回路 則不選取這條邊重新選取 直到連接完所有的結(jié)點(diǎn) 這樣求出的樹(shù)就是最小生成樹(shù) 例題 帶權(quán)圖如右 求圖的最小生成樹(shù)解 選取含最大邊 c d 的回路cdec 刪去其中權(quán)數(shù)最大的邊 c d 然后再選取含最大邊 a b 的回路abea 刪去其中權(quán)數(shù)最大的邊 a b 再選取含最大邊 c e 的回路bceb 刪去其中權(quán)數(shù)最大的邊 c e 再選取含最大邊 a d 的回路adea 刪去其中權(quán)數(shù)最大的邊 a d 即得最小生成樹(shù) T 例題 求圖G的一棵最小生成樹(shù) 解 解法二 用克魯斯特爾算法做 先去掉所有的邊 從最小邊 d e 開(kāi)始選取 再選取 d a 再選取 e a 和 b