【文章內容簡介】 l 樹：無圈的連通圖即為樹 最小生成樹問題最小生成樹問題 最小生成樹問題圖 1111v1v2 v3v4v5v6v7v8 v9v1v2 v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a) (b) (c)下列圖中，哪些是樹？Page 44圖 G1={V E1}和圖 G2={V2， E2}，如果有 ，稱 G1是 G2的一個 子圖若有 ，則稱 G1是 G2的一個支撐子圖v3e7e4e8e5e6e1e2 e3v1v2v4 v5v3e4e8e5e6v2v4 v5(a)v3e7e4e8e6e2 e3v1v2v4 v5(b)（ G圖）l 子圖，支撐子圖 最小生成樹問題最小生成樹問題Page 45如果 G2是 G1的支撐圖（生成圖），又是樹圖，則稱 G2是 G1的生成樹（或支撐樹）。v1v2v3v4v5v1v2v3v4v5G1 G2 最小生成樹問題最小生成樹問題l 圖的生成樹（支撐樹）Page 46abcfedhgbfed 最小生成樹問題最小生成樹問題l 圖的生成樹（支撐樹）Page 47abcfedhgbfdg 最小生成樹問題最小生成樹問題l 圖的生成樹（支撐樹）Page 48bcedabcfedhg 最小生成樹問題最小生成樹問題l 圖的生成樹（支撐樹）Page 49abchabcfedhg 最小生成樹問題最小生成樹問題l 圖的生成樹（支撐樹）Page 50afdgabcfedhg 最小生成樹問題最小生成樹問題l 圖的生成樹（支撐樹）Page 51破圈法 最小生成樹問題最小生成樹問題l 求支撐樹的方法：破圈法 和 避圈法Page 52生成樹（支撐樹）l 求支撐樹的方法：破圈法 和 避圈法 最小生成樹問題最小生成樹問題Page 53v1v2v3v4v5v6 v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5l 求支撐樹的方法：破圈法 和 避圈法 最小生成樹問題最小生成樹問題避圈法Page 54最小生成樹問題：在一個賦權的、連通的、無向圖 G 中找出一個生成樹，并使得這個生成樹的所有邊的權數之和為最小 最小生成樹問題最小生成樹問題l 圖的最小生成樹（支撐樹）1. 在給定的賦權的連通圖上任找一個圈2. 在所找的圈中去掉一個權數最大的邊（如果有兩條或兩條以上的邊都是權數最大的邊，則任意去掉其中一條）。如果所余下的圖已不包含圈，則計算結束，所余下的圖即為最小生成樹，否則返回第 1步。求解最小生成樹的破圈算法Page 55v1v2 v4v5v64352 158 78破圈法 ：任取一圈，去掉圈中最長邊，直到無圈。5v1v2v3v4v5v6843752618v3邊數＝ n1=5 最小生成樹問題最小生成樹問題l 圖的最小生成樹（支撐樹）6Page 56v1v2v3v4v5v64352 1Min C(T)=15 最小生成樹問題最小生成樹問題l 圖的最小生成樹（支撐樹）Page 57樹與圖的最小樹樹與圖的最小樹避圈法 :去掉 G中所有邊，得到 n個孤立點；然后加邊。加邊的原則為：從最短邊開始添加，加邊的過程中不能形成圈，直到點點連通 (即 :n1條邊 )。5v1v2v3v4v5v6843752618Page 58樹與圖的最小樹樹與圖的最小樹v1v2v3v4v5v64352 15v1v2v3v4v5v6843752618Min C(T)=15Page 59v1v7v4v3v2v5v6201591625 32817412336練習：練習： 應用破圈法求最小樹應用破圈法求最小樹 最小生成樹問題最小生成樹問題Page 60v1v7v4v3v2v5v6201591625 32817412336 最小生成樹問題最小生成樹問題Page 61v1v7v4v3v2v5v6201591625 328174123 最小生成樹問題最小生成樹問題Page 62v1v7v4v3v2v5v6201591625 328174123 最小生成樹問題最小生成樹問題Page 63v1v7v4v3v2v5v61591625 328174123 最小生成樹問題最小生成樹問題Page 64v1v7v4v3v2v5v61591625 328174123 最小生成樹問題最小生成樹問題Page 65v1v7v4v3v2v5v6 91625 328174123 最小生成樹問題最小生成樹問題Page 66v1v7v4v3v2v5v6 91625 328174123 最小生成樹問題最小生成樹問題Page 67v1v7v4v3v2v5v6 925 328174123 最小生成樹問題最小生成樹問題Page 68v1v7v4v3v2v5v6 925 328174123 最小生成樹問題最小生成樹問題Page 69v1v7v4v3v2v5v6 9328174123 最小生成樹問題最小生成樹問題Page 70v1v7v4v3v2v5v6 9328174123 最小生成樹問題最小生成樹問題Page 71v1v7v4v3v2v5v6 93174123min=1+4+9+3+17+23=57 最小生成樹問題最小生成樹問題Page 72樹與圖的最小樹樹與圖的最小樹練習：練習： 應用避圈法求最小樹應用避圈法求最小樹v1v7v4v3v2v5v6201591625 32817412336Page 73樹與圖的最小樹樹與圖的最小樹v1v7v4v3v2v5v6201591625 32817412336Page 74樹與圖的最小樹樹與圖的最小樹v1v7v4v3v2v5v6201591625 32817412336Page 75樹與圖的最小樹樹與圖的最小樹v1v7v4v3v2v5v6201591625 32817412336Page 76樹與圖的最小樹樹與圖的最小樹v1v7v4v3v2v5v6201591625 32817412336Page 77樹與圖的最小樹樹與圖的最小樹v1v7v4v3v2v5v6201591625 32817412336Page 78樹與圖的最小樹樹與圖的最小樹v1v7v4v3v2v5v6201591625 32817412336min=1+4+9+3+17+23=57Page 79課堂練習：課堂練習：3749346321Min C(T)=12 Min C(T)=15254173314475答案： 最小生成樹問題最小生成樹問題Page 8034122323242 Min C(T)=122136385345 6 74 54321Min C(T)=18 最小生成樹問題最小生成樹問題例 6. 用破圈算法求圖（ a）中的一個最小生成樹 最小生成樹