圖與網(wǎng)絡(luò)分析ppt課件(2)(參考版)
2025-05-09 23:01本頁面
【正文】 問如何安排分檢過程，可使總的運(yùn)算（比較）次數(shù)最小 ? 。 使用計(jì)算機(jī)進(jìn)行圖書分類。令 s?s1，若 s＝ 1停止，否則轉(zhuǎn)（ 1） 例 8 S=6，其權(quán)分別為 4,3,3,2,2,1，求最優(yōu)二叉樹。 算法步驟為： （ 1）將 s個(gè)葉子按權(quán)由小至大排序，不失一般性，設(shè) p1≤p2 ≤ … ≤ p s。令有 s個(gè)葉子的二叉樹 T各葉子的權(quán)分別為 pi，根到各葉子的距離 (層次 )為 li(i＝ 1， … ， s)，這樣二叉樹 T的總權(quán)數(shù) ???siiilpTm1)(滿足總權(quán)最小的二叉樹稱為 最優(yōu)二叉樹 。當(dāng) m=2時(shí)，稱為二叉樹、完全二叉樹。 定義 19 在根樹中，若每個(gè)頂點(diǎn)的出次小于或等于 m，稱這棵樹為 m叉樹 。根樹中出次為 0的點(diǎn)稱為 葉 ，其他頂點(diǎn)稱為 分枝點(diǎn) 。 定義 18 有向樹 T，恰有一個(gè)結(jié)點(diǎn)入次為 0，其余各點(diǎn)入次均為 1，則稱 T為 根樹 （又稱外向樹）。 定理 9 圖 G的生成樹 T為最小樹，當(dāng)且僅當(dāng)對(duì)任一 e來說， e是 T+e中與之對(duì)應(yīng)的圈 ?e中的最大權(quán)邊。以 T2代 T1，重復(fù)（ 2）再檢查剩余的弦，直到全部弦檢查完畢為止。 （ 2）加上一條弦 e1， T1+e1中立即生成一個(gè)圈。否則 ,去掉 . 例：求下圖的一棵最小支撐樹 ( v2,v3),( v4,v5),(v6,v7),(v4,v6),(v5,v7),(v2,v5),(v5,v6),(v2,v4), (v3,v6),(v3,v4),(v1,v3),(v1,v2) v1 v2 v3 v4 v5 v6 v7 8 7 1 4 5 6 5 4 3 2 2 3 其權(quán)為： 19 定理 8 用 Kruskal算法得到的子圖 T*＝(e1,e2,…,e n1)是一棵最小樹。 ?（ 3）重復(fù)（ 2）過程，直到所有的邊試驗(yàn)完畢。具有最小權(quán)的生成樹稱為 最小生成樹 (最小支撐樹 )簡(jiǎn)稱 最小樹 。 三、最小生成樹問題 定義 16 連通圖 G＝ (V， E)、每條邊上有非負(fù)權(quán) L(e)。 ③對(duì)標(biāo)號(hào) i+1的點(diǎn)重復(fù)步驟②，直到全部點(diǎn)得到標(biāo)號(hào)為止。 ②令所有標(biāo)號(hào)為 i的點(diǎn)集為 Vi，檢測(cè)查 [Vi，V＼ Vi]中的邊端點(diǎn)是否均已標(biāo)號(hào)。直到全部點(diǎn)得到標(biāo)號(hào)為止。今 w代 u，重復(fù)② 。 ②若某 u點(diǎn)已得標(biāo)號(hào) i，檢查一端點(diǎn)為 u的各邊，另一端點(diǎn)是否均已標(biāo)號(hào)。 尋找生成樹的方法 （ 1）深探法 步驟如下 （ 用標(biāo)號(hào)法） ①在點(diǎn)集 V中任取 — 點(diǎn) v。圖 G中屬于生成樹的邊稱為 樹枝 ，不在生成樹中的邊際為 弦 。 二、圖的生成樹 定義 15 若圖 G的生成子圖是一棵樹，則稱該樹為 G的 生成樹 (支撐樹 )。 ⑤連枝的集合是原連通圖相應(yīng)的 余樹 ，或稱 補(bǔ)樹 。 ③樹的任意兩個(gè)頂點(diǎn)間添加一條邊（稱為連枝），就構(gòu)成一個(gè)回路。 ②樹中任意兩點(diǎn)之間有且僅有一條鏈連接相通。 （ 6） T中任意兩點(diǎn) ， 有惟一鏈相連 。 （ 4） T無圈 ， 但每加一新邊即得惟一一個(gè)圈 。 （ 2） T無圈 ， 且 m=n
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1