離散數學05二月2023電子科技大學計算機科學與工程學院2023/2/5第10章樹

樹是圖論中的一個非常重要的概念，而在計算機科學中有著非常廣泛的應用，例如現代計算機操作系統均采用樹形結構來組織文件和文件夾，本章介紹樹的基本知識和應用。在本章中，所談到的圖都假定是簡單圖；所談到的回路均指簡單回路或基本回路。并且同一個圖形表示的回路(簡單的或基本的)，可能有不同的交替序列表示方法，但我們規定它們表示的是同一條回路。2023/2/510.0內容提要與樹相關的概念：樹、森林、根樹、根、葉、分支點、生成樹、最小生成樹、k元樹、k元完全樹、子樹、有序樹、祖先與后代、父親與兒子、最優樹等；樹的基本性質：m=n-1等；樹的算法：求生成樹與最小生成樹的算法、求最優樹的算法、二元樹遍歷的算法、根樹與二元樹相互轉化的算法等；樹的應用。2023/2/510.1本章學習要求重點掌握一般掌握了解11與樹相關基本概念2樹的性質3樹的基本算法31樹的同構2樹的應用2樹的算法

2023/2/510.2樹10.2.1樹的定義與性質例10.2.12006年德國世界杯8強的比賽結果圖，最后勝利的隊捧得大力神杯。德國阿根廷意大利烏克蘭英格蘭葡萄牙巴西法國德國意大利葡萄牙法國意大利法國意大利2023/2/5定義10.2.1連通而不含回路的無向圖稱為無向樹(UndirectedTree)，簡稱樹(Tree)，常用T表示樹。樹中度數為1的結點稱為葉(Leaf)；度數大于1的結點稱為分支點(BranchPoint)或內部結點(InteriorPoint)。每個連通分支都是樹的無向圖稱為森林(Forest)。平凡圖稱為平凡樹(TrivialTree)。樹中沒有環和平行邊，因此一定是簡單圖在任何非平凡樹中，都無度數為0的結點。2023/2/5例10.2.2判斷下圖中的圖哪些是樹？為什么？(a)(b)(c)(d)分析判斷無向圖是否是樹，根據定義10.2.1，首先看它是否連通，然后看它是否有回路。解圖(a)、(b)都是連通，并且不含回路，因此是樹；圖(c)不連通，因此不是樹，但由于它不含回路，因此是森林；圖(d)雖然連通，但存在回路，因此不是樹。2023/2/5樹的性質定理10.2.1

設無向圖G=<V,E>，|V|=n，|E|=m，下列各命題是等價的：G連通而不含回路(即G是樹)；G中無回路，且m=n-1；G是連通的，且m=n-1；G中無回路，但在G中任二結點之間增加一條新邊，就得到惟一的一條基本回路；G是連通的，但刪除G中任一條邊后，便不連通；(n≥2)G中每一對結點之間有惟一一條基本通路。(n≥2)2023/2/5分析直接證明這6個命題兩兩等價工作量太大，一般采用循環論證的方法，即證明(1)(2)(3)(4)(5)(6)(1)然后利用傳遞性，得到結論。2023/2/5證明(1)(2)：對n作歸納。n=1時，m=0，顯然有m=n-1。假設n=k時命題成立，現證n=k+1時也成立。由于G連通而無回路，所以G中至少有一個度數為1的結點v0，在G中刪去v0及其關聯的邊，便得到k個結點的連通而無回路的圖，由歸納假設知它有k-1條邊。再將結點v0及其關聯的邊加回得到原圖G，所以G中含有k+1個結點和k條邊，符合公式m=n-1。所以，G中無回路，且m=n-1。G連通而不含回路(即G是樹)G中無回路，且m=n-1；2023/2/5(2)(3)：證明只有一個連通分支。設G有k個連通分支G1，G2，…，Gk，其結點數分別為n1，n2，…，nk，邊數分別為m1，m2，…，mk，且，。由于G中無回路，所以每個Gi(i=1,2,…,k)均為樹，因此mi=ni-1(i=1,2,…,k)，于是故k=1，所以G是連通的，且m=n-1。G中無回路，且m=n-1；G是連通的，且m=n-1；2023/2/5(3)(4)：首先證明G中無回路。對n作歸納。n=1時，m=n-1=0，顯然無回路。假設結點數n=k-1時無回路，下面考慮結點數n=k的情況。因G連通，故G中每一個結點的度數均大于等于1。可以證明至少有一個結點v0，使得deg(v0)=1，因若k個結點的度數都大于等于2，則，從而m≥k，即至少有k條邊，但這與m=n-1矛盾。G是連通的，且m=n-1；G中無回路，但在G中任二結點之間增加一條新邊，就得到惟一的一條基本回路；2023/2/5在G中刪去v0及其關聯的邊，得到新圖G’，根據歸納假設知G’無回路，由于deg(v0)=1，所以再將結點v0及其關聯的邊加回得到原圖G，則G也無回路。其次證明在G中任二結點vi，vj之間增加一條邊(vi,vj)，得到一條且僅一條基本回路。由于G是連通的，從vi到vj有一條通路L，再在L中增加一條邊(vi,vj)，就構成一條回路。若此回路不是惟一和基本的，則刪去此新邊，G中必有回路，得出矛盾。2023/2/5(4)(5)：若G不連通，則存在兩結點vi和vj，在vi和vj之間無通路，此時增加邊(vi,vj)，不會產生回路，但這與題設矛盾。由于G無回路，所以刪去任一邊，圖便不連通。G中無回路，但在G中任二結點之間增加一條新邊，就得到惟一的一條基本回路；G是連通的，但刪除G中任一條邊后，便不連通；(n≥2)2023/2/5G是連通的，但刪除G中任一條邊后，便不連通；(n≥2)G中每一對結點之間有惟一一條基本通路。(n≥2)(5)(6)：由于G是連通的，因此G中任二結點之間都有通路，于是有一條基本通路。若此基本通路不惟一，則G中含有回路，刪去回路上的一條邊，G仍連通，這與題設不符。所以此基本通路是惟一的。2023/2/5(6)(1)：顯然G是連通的。若G中含回路，則回路上任二結點之間有兩條基本通路，這與題設矛盾。因此，G連通且不含回路。G中每一對結點之間有惟一一條基本通路。(n≥2)G連通而不含回路(即G是樹)；2023/2/5樹的特點在結點給定的無向圖中，樹是邊數最多的無回路圖樹是邊數最少的連通圖由此可知，在無向圖G=(n,m)中，若m＜n-1，則G是不連通的若m＞n-1，則G必含回路由定理10.2.1(4)由定理10.2.1(5)2023/2/5定理10.2.2任意非平凡樹T=(n,m)都至少有兩片葉。分析利用握手定理和m=n-1即可。證明因非平凡樹T是連通的，從而T中各結點的度數均大于等于1。設T中有k個度數為1的結點(即k片葉)，其余的結點度數均大于等于2。由于樹中有m=n-1，于是2(n-1)≥2n-k，因此可得k≥2，這說明T中至少有兩片葉。于是由握手定理2023/2/510.2.2生成樹定義10.2.2

給定圖G=<V,E>，若G的某個生成子圖是樹，則稱之為G的生成樹(SpanningTree)，記為TG。生成樹TG中的邊稱為樹枝(Branch)；G中不在TG中的邊稱為弦(Chord)；TG的所有弦的集合稱為生成樹的補(Complement)。2023/2/5例10.2.3判斷下圖中的圖(b)、(c)、(d)、(e)是否是圖(a)的生成樹。abcdef(a)abcdef(b)abcdef(c)abcdef(d)bcdef(e)分析判斷是否是生成樹，根據定義10.2.2，首先看它是否是樹，然后再看它是否是生成子圖。由于圖(b)和(d)不是樹，圖(e)不是生成子圖，因此它們都不是圖(a)的生成樹，而圖(c)既是樹，又是生成子圖，因此是生成樹。解圖(b)、(d)和(e)不是圖(a)的生成樹，圖(c)是圖(a)的生成樹，其中邊(a,c)、(a,d)、(b,f)、(c,f)、(c,e)是樹枝，而(a,b)、(b,c)、(c,d)、(d,e)、(e,f)是弦。2023/2/5定理10.2.3一個圖G=<V,E>存在生成樹TG=<V,ET>的充分必要條件是G是連通的。分析必要性由樹的定義即得，充分性利用構造性方法，具體找出一顆生成樹即可證明必要性：假設TG=<V,ET>是G=<V,E>的生成樹，由定義10.2.1，TG是連通的，于是G也是連通的。充分性：假設G=<V,E>是連通的。如果G中無回路，G本身就是生成樹。如果G中存在回路C1，可刪除C1中一條邊得到圖G1，它仍連通且與G有相同的結點集。如果G1中無回路，G1就是生成樹。如果G1仍存在回路C2，可刪除C2中一條邊，如此繼續，直到得到一個無回路的連通圖H為止。因此，H是G的生成樹。2023/2/5破圈法與避圈法算法10.2.1

求連通圖G=<V,E>的生成樹的破圈法： 每次刪除回路中的一條邊，其刪除的邊的總數為m-n+1。算法10.2.2

求連通圖G=<V,E>的生成樹的避圈法： 每次選取G中一條與已選取的邊不構成回路的邊，選取的邊的總數為n-1。由于刪除回路上的邊和選擇不構成任何回路的邊有多種選法，所以產生的生成樹不是惟一的。2023/2/5例10.2.4分別用破圈法和避圈法求下圖的生成樹。123456分析分別用破圈法和避圈法依次進行即可。用破圈法時，由于n=6，m=9，所以m-n+1=4，故要刪除的邊數為4，因此只需4步即可。用避圈法時，由于n=6，所以n-1=5，故要選取5條邊，因此需5步即可。破圈法2023/2/5避圈法由于生成樹的形式不惟一，故上述兩棵生成樹都是所求的。破圈法和避圈法的計算量較大，主要是需要找出回路或驗證不存在回路。1234561234562023/2/5算法10.2.3求連通圖G=<V,E>的生成樹的廣度優先搜索算法：（1）任選s∈V，將s標記為0，令L={s}，V=V-{s}，k=0；（2）如果V=Φ，則轉(4)，否則令k=k+1；（3）依次對L中所有標記為k-1的結點v，如果它與V中的結點w相鄰接，則將w標記為k，指定v為w的前驅，令L=L∪{w}，V=V-{w}，轉(2)；（4）EG={(v,w)|w∈L-{s}，v為w的前驅}，結束。2023/2/5例10.2.5利用廣度優先搜索算法求下圖的生成樹。0(-)1(a)1(a)2(c)2(b)3(e)3(e)3(e)4(d)4(h)bacdgjifeh0(-)1(a)1(a)2(c)2(b)3(e)3(f)3(e)4(h)4(h)bacdgjifeh2023/2/510.2.3最小生成樹定義10.2.3

設G=<V,E>是連通的賦權圖，T是G的一棵生成樹，T的每個樹枝所賦權值之和稱為T的權(Weight)，記為w(T)。G中具有最小權的生成樹稱為G的最小生成樹(MinimalSpanningTree)。

一個無向圖的生成樹不是惟一的，同樣地，一個賦權圖的最小生成樹也不一定是惟一的。2023/2/5算法10.2.3Kruskal算法（1）在G中選取最小權邊e1，置i=1。（2）當i=n-1時，結束，否則轉(3)。（3）設已選取的邊為e1,e2,…,ei，在G中選取不同于e1,e2,…,ei的邊ei+1，使{e1,e2,…,ei,ei+1}中無回路且ei+1是滿足此條件的最小權邊。（4）置i=i+1，轉(2)。要點：在與已選取的邊不構成回路的邊中選取最小者。

在Kruskal算法的步驟1和3中，若滿足條件的最小權邊不止一條，則可從中任選一條，這樣就會產生不同的最小生成樹。2023/2/5例10.2.6用Kruskal算法求圖中賦權圖的最小生成樹。4655761f923adbcimjkehg343446587582345k1fech34a3i5dm2g2bj4解n=12，按算法要執行n-1=11次，w(T)=36。2023/2/5算法10.2.5Prim算法（1）在G中任意選取一個結點v1，置VT={v1},ET=Φ，k=1；（2）在V-VT中選取與某個vi∈VT鄰接的結點vj，使得邊(vi,vj)的權最小，置VT=VT∪{vj},ET=ET∪{(vi,vj)}，k=k+1；（3）重復步驟2，直到k=|V|。要點：從任意結點開始，每次增加一條最小權邊構成一棵新樹。

在Prim算法的步驟2中，若滿足條件的最小權邊不止一條，則可從中任選一條，這樣就會產生不同的最小生成樹。

2023/2/5例10.2.7用Prim算法求圖中賦權圖的最小生成樹。5f102dbce7g64582a7ge2f5b42cad5解n=7，按算法要執行n-1=6次，w(T)=25。由Prim算法可以看出，每一步得到的圖一定是樹，故不需要驗證是否有回路，因此它的計算工作量較Kruskal算法要小。

2023/2/510.2.4無向樹的難點樹是不含回路的連通圖。注意把握樹的性質，特別是樹中葉結點的數目及邊數與結點數的關系：m=n-1；生成樹是無向連通圖是樹的生成子圖。注意把握所有連通圖都有生成樹，知道生成樹的樹枝與弦及其數目，會使用避圈法、破圈法和廣度優先搜索算法求生成樹；最小生成樹是賦權連通圖的權值之和最小的生成樹。會使用Kruskal算法和Prim算法求最小生成樹。2023/2/510.2.5無向樹的應用

例10.2.8

假設有5個信息中心A、B、C、D、E，它們之間的距離(以百公里為單位)如圖所示。要交換數據，我們可以在任意兩個信息中心之間通過光纖連接，但是費用的限制要求鋪設盡可能少的光纖線路。重要的是每個信息中心能和其它中心通信，但并不需要在任意兩個中心之間都鋪設線路，可以通過其它中心轉發。ABCDE3547962879ABCDE3462分析這實際上就是求賦權連通圖的最小生成樹問題，可用Prim算法或Kruskal算法求解。解求得圖的最小生成樹如圖所示，w(T)=15百公里。即按圖的圖鋪設，使得鋪設的線路最短。2023/2/510.3根樹10.3.1根樹的定義與分類定義10.3.1

一個有向圖，若略去所有有向邊的方向所得到的無向圖是一棵樹，則這個有向圖稱為有向樹(DirectedTree)。2023/2/5例10.3.1判斷下圖中的圖哪些是樹？為什么？(a)(c)(e)(d)(b)2023/2/5定義10.3.2一棵非平凡的有向樹，如果恰有一個結點的入度為0，其余所有結點的入度均為1，則稱之為根樹(RootTree)或外向樹(OutwardTree)。入度為0的結點稱為根(Root)；出度為0的結點稱為葉(Leaf)；入度為1，出度大于0的結點稱為內點(InteriorPoint)；又將內點和根統稱為分支點(BranchPoint)。在根樹中，從根到任一結點v的通路長度，稱為該結點的層數(LayerNumber)；稱層數相同的結點在同一層上；所有結點的層數中最大的稱為根樹的高(Height)。2023/2/5例10.3.2判斷下圖所示的圖是否是根樹？若是根樹，給出其根、葉和內點，計算所有結點所在的層數和高。v1v2v3v4v5v6v7v8v9v10v11v12v13v1v2v3v4v5v6v7v8v9v10v11v12v13解是一棵根樹，其中v1為根，v5,v6,v8,v9,v10,v12,v13為葉，v2,v3,v4,v7,v11為內點。v1處在第零層，層數為0；v2,v3,v4同處在第一層，層數為1；v5,v6,v7,v8,v9同處在第二層，層數為2；v10,v11,v12同處在第三層，層數為3；v13處在第四層，層數為4；這棵樹的高為4。倒置法

2023/2/5家族關系定義10.3.3

在根樹中，若從結點vi到vj可達，則稱vi是vj的祖先(Ancestor)，vj是vi的后代(Descendant)；又若<vi,vj>是根樹中的有向邊，則稱vi是vj的父親(Father)，vj是vi的兒子(Son)；如果兩個結點是同一個結點的兒子，則稱這兩個結點是兄弟(Brother)。定義10.3.4

如果在根樹中規定了每一層上結點的次序，這樣的根樹稱為有序樹(OrderedTree)。一般地，在有序樹中同一層中結點的次序為從左至右。有時也可以用邊的次序來代替結點的次序。2023/2/5定義10.3.5(J0430)在根樹T中，若每個分支點至多有k個兒子，則稱T為k元樹(k-aryTree)；若每個分支點都恰有k個兒子，則稱T為k元完全樹(k-aryCompleteTree)；若k元樹T是有序的，則稱T為k元有序樹(k-aryOrderedTree)；若k元完全樹T是有序的，則稱T為k元有序完全樹(k-aryOrderedCompleteTree)。2023/2/5子樹在根樹T中，任一結點v及其所有后代導出的子圖T’稱為T的以v為根的子樹(Subtree)。當然，T’也可以有自己的子樹。二元有序樹的每個結點v至多有兩個兒子，分別稱為v的左兒子(LeftSon)和右兒子(RightSon)。二元有序樹的每個結點v至多有兩棵子樹，分別稱為v的左子樹(LeftSubtree)和右子樹(RightSubtree)。注意區分以v為根的子樹和v的左(右)子樹，v為根的子樹包含v，而v的左(右)子樹不包含v。

2023/2/5例10.3.3判斷下圖所示的幾棵根樹是什么樹？(b)(c)(a)2元完全樹

3元樹

3元完全樹

3元有序完全樹122(d)1332132023/2/5k元完全樹中分支點與葉結點數目之間的關系定理10.3.1

在k元完全樹中，若葉數為t，分支點數為i，則下式成立：(k-1)×i=t-1證明由假設知，該樹有i+t個結點。由定理10.2.1知，該樹的邊數為i+t-1。由握手定理知，所有結點的出度之和等于邊數。而根據k元完全樹的定義知，所有分支點的出度為k×i。因此有k×i=i+t-1即 (k-1)×i=t-12023/2/5例10.3.4假設有一臺計算機，它有一條加法指令，可計算3個數的和。如果要求9個數x1,x2,x3,x4,x5,x6,x7,x8,x9之和，問至少要執行幾次加法指令？解用3個結點表示3個數，將表示3個數之和的結點作為它們的父結點。這樣本問題可理解為求一個三元完全樹的分支點問題。把9個數看成葉。由定理10.9知，有(3-1)i=9-1，得i=4。所以至少要執行4次加法指令。(a)x1x2x3x43x5x6x7x8x9x1x2x3x4x5x6x7x9(b)2023/2/5一個多種解法的例子例10.3.5

設T為任意一棵二元完全樹，m為邊數，t為葉數，試證明：m=2t-2。這里t≥2。證明

方法一：設T中的結點數為n，分支點數為i。根據二元完全樹的定義，容易知道下面等式均成立：n=i+t，m=2i，m=n-1解關于m,n,i的三元一次方程組得m=2t-2。2023/2/5方法二：在二元完全樹中，除樹葉外，每個結點的出度均為2；除根結點外，每個結點的入度均為1。設T中的結點數為n，由握手定理可知2m==+=2(n-t)+n-1=3n-2t-1=3(m+1)-2t-1故m=2t-2。2023/2/5方法三：對樹葉數t作歸納法。當t=2時，結點數為3，邊數m=2，故m=2t-2成立。假設t=k(k≥2)時，結論成立，下面證明t=k+1時結論也成立。由于T是二元完全樹，因此T中一定存在都是樹葉的兩個兄弟結點v1,