1、第九章樹樹是圖論中的一個非常重要的概念，而 在計算機科學中有著非常廣泛的應用，例如 現(xiàn)代計算機操作系統(tǒng)均采用樹形結(jié)構(gòu)來組織 文件和文件夾，本章介紹樹的基本知識和應 用。定義1§9.1 樹無向樹：連通而不含回路的無向圖稱為無向樹，簡稱樹，常用T表示樹。葉：樹中度數(shù)為1的結(jié)點； 分支點或內(nèi)部結(jié)點：度數(shù)大于1的結(jié)點；森林：每個連通分支都是樹的無向圖。注：樹中沒有環(huán)和平行邊，因此一定是簡單圖例1判斷下圖中的圖哪些是樹？為什么？(a)(b)(c)(d) 分析判斷無向圖是否是樹，根據(jù)定義1，首先看它 是否連通，然后看它是否有回路。定理1 設無向圖G = <V,E>，|V| = n，|

2、E| = m，下列各命題是等價的： G連通而不含回路(即G是樹)； G中無回路，且m=n-1； G是連通的，且m=n-1； G中無回路，但在G中任二結(jié)點之間增加一條 新邊，就得到惟一的一條基本回路； G是連通的，但刪除G中任一條邊后，便不連 通；(n2) G中每對結(jié)點間有惟一一條基本通路。(n2)例2：無向樹G有5片樹葉，3個2度分支點，其余分支點均為3度，問G有多少個結(jié)點？解：由握手定理2m=d(vi) 及定理1n= m+1 設G有n個頂點,則有下列關系式5 ×1+3 ×2+(n-5-3) ×3=2 ×(n-1)解得：n=11例3：無向樹G有2個2度結(jié)

3、點，1個3度結(jié)點，3個4度結(jié)點，則其1度結(jié)點數(shù)為多少？解：由握手定理2m=d(vi)及定理1n=m+1設G有t個1頂點, 則有下列關系式2×2+3+4×3+t =2m=2×(n-1)=2×(2+1+3+t-1)解得：t = 9定理2任意非平凡樹T = (n, m) 都至少有兩片葉。分證析明利因用樹握T手是定連理通和的m，=從n而-1T即中可各。結(jié)點的度數(shù)均大于等于1。設T中有k個度數(shù)為1的結(jié)點(即k片葉)， 其余的結(jié)點度數(shù)均大于等于2。于是由握手定理2m=åvVdeg(v) k + 2(n - k) = 2n - k由于樹中有m=n-1，于是2

4、(n-1)2n-k，因此可得k2，這說明T中至少有兩片葉。§9.2 有向樹定義1 一個有向圖，若略去所有有向邊的方 向所得到的無向圖是一棵樹，則這個有向圖 稱為有向樹。例1判斷下圖中的圖哪些是樹？為什么？(a)(b)(c)(d)(e)外向樹的定義與分類定義2外向樹:一棵非平凡的有向樹，如果恰有一個結(jié)點 的入度為0，其余所有結(jié)點的入度均為1。根:入度為0的結(jié)點； 葉:出度為0的結(jié)點；分支點:非根非葉結(jié)點稱為分支點。 層數(shù)：從根到任一結(jié)點v的通路長度，稱為該結(jié)點的層數(shù)；高：所有結(jié)點中的最大層數(shù)。例2判斷下圖所示的圖是否是外向樹？若是外向樹，給出其根、葉和分支點，計算所有結(jié)點所在的層數(shù)和

5、高。解是 一 棵 外 向 樹 ， 其 中 v1 為v1根，v ,v,v ,v ,v,v,v為葉，5689101213v2v3v4v5v6v7v8v9 v10v11v12v2,v3,v4,v7,v11 為 內(nèi)點 。 v1 處在第零層，層數(shù)為0； v2,v3,v4 同處在第 一 層 ， 層 數(shù) 為 1 ； v5,v6,v7,v8,v9 同處在第二層，層數(shù)為2；v10,v11,v12同處在第三層，層數(shù)為3；處在第四層，層數(shù)為4；這棵樹v13v13的高為4。家族關系定義3 在外向樹中，若從 結(jié)點vi 到 vj 可達，則 稱vi是vj的祖先，vj是vi 的后代；又若<vi, vj>是 根樹中

6、的有向邊，則稱v1v2v3v4v5v6v7v8v9vi是vj的父親，vj是vi的兒子；如果兩個結(jié)點是同一個結(jié)點的兒子，則 稱這兩個結(jié)點是兄弟。v10v11v13v12內(nèi)向樹:一棵非平凡的有向樹，如果恰有一個結(jié)點的出度為0，其余所有結(jié)點的出度均為1。根:出度為0的結(jié)點；葉:入度為0的結(jié)點；分支點:非根非葉結(jié)點稱為分支點。層數(shù)：從根到任一結(jié)點v的通路長度，稱為該結(jié)點的層數(shù)；高：所有結(jié)點中的最大層數(shù)。v1v2v3v4v5v6v7v8v9 v10v11v12v13定義4在外向樹T中， m元樹：若每個結(jié)點的出度不超過正數(shù)m； m元完全樹：若每個結(jié)點（不含葉）的出度都等于正數(shù)m 。例3判斷下圖所示的幾棵外

7、向樹是什么樹？(a)(b)(c)2元 完全樹3元樹3元完全樹二元樹比較重要，許多實際問題都可用二元樹表示生成樹§9.3生成樹定義1 給定圖G = <V, E>，若G的某個生成子圖是樹，則稱之為G的生成樹，記為TG。 生成樹TG中的邊稱為樹枝；G中不在TG中的 邊稱為弦；TG的所有弦的集合稱為生成樹的 補。例1判斷下圖中的圖(b)、(c)、(d)、(e)是否是圖(a)的生成樹。afeafeafeafefebcd (a)bcd (b)bcd (c)bcd (d)bcd (e)(b)解分析圖判(b斷)、是(d否)和是(生e)不成是樹圖，(根a)據(jù)的定生義成1樹，首圖先(看c)是

8、它圖是 否是樹，然后再看它是否是生成子圖。由于圖(a)的生成樹，其中邊(a,c)、(a,d)、(b,f)、(c,f)、和(d)不是樹，圖(e)不是生成子圖，因此它們都不 (c, e)是樹枝，而(a, b)、(b, c)、(c, d)、(d, e)、(e, f) 是 圖 (a) 的 生 成 樹 ， 而 圖 (c) 既 是 樹 ， 又 是 生 成 子是圖弦，。因此是生成樹。破圈法與避圈法算法1求連通圖G = <V, E>的生成樹的破圈法： 每次刪除回路中的一條邊，其刪除的邊的總數(shù) 為m-n+1。算法2求連通圖G = <V, E>的生成樹的避圈法： 每次選取G中一條與已選取的

9、邊不構(gòu)成回路的 邊，選取的邊的總數(shù)為n-1。由于刪除回路上的邊和選擇不構(gòu)成任何回路的邊有 多種選法，所以產(chǎn)生的生成樹不是惟一的。例2分別用破圈法和避圈法求下圖的生成樹。1破圈法26534分析 分別用破圈法和避圈法依次進行即可。用破圈法時， 由于n = 6，m = 9，所以m-n+1 = 4，故要刪除的邊數(shù)為4， 因此只需4步即可。用避圈法時，由于n = 6，所以n-1 = 5， 故要選取5條邊，因此需5步即可。避圈法112652653434Ø由于生成樹的形式不惟一，故上述兩棵生成樹都是所求的。Ø破圈法和避圈法的計算量較大，主要是需要找 出回路或驗證不存在回路。思考：現(xiàn)要鋪設

10、一個連接各個城市的輸油管道，邊上的 權(quán)代表費用，問如鋪設才能使總費用最??？27123518732443466上圖即為最小生成樹問題最小生成樹定義3 設G = <V, E>是連通的帶權(quán)圖，T是G的一 棵 生 成樹 ， T的 每個 樹 枝所賦權(quán)值之和稱為 T的 權(quán)，記為w(T)。G中具有最小權(quán)的生成樹稱為G的 最小生成樹。一個無向圖的生成樹不是惟一的，同樣地， 一個帶權(quán)圖的最小生成樹也不一定是惟一的。算法3Kruskal算法(避圈法)（1）在G中選取最小權(quán)邊e1，置i=1。（2）當i=n-1時，結(jié)束，否則轉(zhuǎn)(3)。（3）設已選取的邊為e1, e2, , ei，在G中選取不同 于e1,

11、e2, , ei的邊ei+1，使e1, e2, , ei, ei+1中無回 路且ei+1是滿足此條件的最小權(quán)邊。要點：在與已選取的邊不構(gòu)成回路的邊中 選取最小者。（4）置i=i+1，轉(zhuǎn)(2)。在Kruskal算法的步驟1和3中，若滿足條件 的最小權(quán)邊不止一條，則可從中任選一條，這樣 就會產(chǎn)生不同的最小生成樹。例3用Kruskal算法求圖的最小生成樹。a5b4c3dab4c3d43234e1gh54233e1fgf792h278545468i6j5k6mij5km解 n=12，按算法要執(zhí)行n-1=11次， w(T)=36。例4用避圈法求下圖所示的最小生成樹解: W(T)=1+2+3+4+5=15a551b5f5e注意：最小生成樹的結(jié)點數(shù)與原圖相等，邊的數(shù)3642目比原圖少。cd6例5：鋪設一