離散數(shù)學第10章樹

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

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

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

設(shè)無向圖G=<V,E>，|V|=n，|E|=m，下列各命題是等價的：G連通而不含回路(即G是樹)；G中無回路，且m=n-1；G是連通的，且m=n-1；G中無回路，但在G中任二結(jié)點之間增加一條新邊，就得到惟一的一條基本回路；G是連通的，但刪除G中任一條邊后，便不連通；(n≥2)G中每一對結(jié)點之間有惟一一條基本通路。(n≥2)2023/2/5分析直接證明這6個命題兩兩等價工作量太大，一般采用循環(huán)論證的方法，即證明(1)(2)(3)(4)(5)(6)(1)然后利用傳遞性，得到結(jié)論。2023/2/5證明(1)(2)：對n作歸納。n=1時，m=0，顯然有m=n-1。假設(shè)n=k時命題成立，現(xiàn)證n=k+1時也成立。由于G連通而無回路，所以G中至少有一個度數(shù)為1的結(jié)點v0，在G中刪去v0及其關(guān)聯(lián)的邊，便得到k個結(jié)點的連通而無回路的圖，由歸納假設(shè)知它有k-1條邊。再將結(jié)點v0及其關(guān)聯(lián)的邊加回得到原圖G，所以G中含有k+1個結(jié)點和k條邊，符合公式m=n-1。所以，G中無回路，且m=n-1。G連通而不含回路(即G是樹)G中無回路，且m=n-1；2023/2/5(2)(3)：證明只有一個連通分支。設(shè)G有k個連通分支G1，G2，…，Gk，其結(jié)點數(shù)分別為n1，n2，…，nk，邊數(shù)分別為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，顯然無回路。假設(shè)結(jié)點數(shù)n=k-1時無回路，下面考慮結(jié)點數(shù)n=k的情況。因G連通，故G中每一個結(jié)點的度數(shù)均大于等于1?？梢宰C明至少有一個結(jié)點v0，使得deg(v0)=1，因若k個結(jié)點的度數(shù)都大于等于2，則，從而m≥k，即至少有k條邊，但這與m=n-1矛盾。G是連通的，且m=n-1；G中無回路，但在G中任二結(jié)點之間增加一條新邊，就得到惟一的一條基本回路；2023/2/5在G中刪去v0及其關(guān)聯(lián)的邊，得到新圖G’，根據(jù)歸納假設(shè)知G’無回路，由于deg(v0)=1，所以再將結(jié)點v0及其關(guān)聯(lián)的邊加回得到原圖G，則G也無回路。其次證明在G中任二結(jié)點vi，vj之間增加一條邊(vi,vj)，得到一條且僅一條基本回路。由于G是連通的，從vi到vj有一條通路L，再在L中增加一條邊(vi,vj)，就構(gòu)成一條回路。若此回路不是惟一和基本的，則刪去此新邊，G中必有回路，得出矛盾。2023/2/5(4)(5)：若G不連通，則存在兩結(jié)點vi和vj，在vi和vj之間無通路，此時增加邊(vi,vj)，不會產(chǎn)生回路，但這與題設(shè)矛盾。由于G無回路，所以刪去任一邊，圖便不連通。G中無回路，但在G中任二結(jié)點之間增加一條新邊，就得到惟一的一條基本回路；G是連通的，但刪除G中任一條邊后，便不連通；(n≥2)2023/2/5G是連通的，但刪除G中任一條邊后，便不連通；(n≥2)G中每一對結(jié)點之間有惟一一條基本通路。(n≥2)(5)(6)：由于G是連通的，因此G中任二結(jié)點之間都有通路，于是有一條基本通路。若此基本通路不惟一，則G中含有回路，刪去回路上的一條邊，G仍連通，這與題設(shè)不符。所以此基本通路是惟一的。2023/2/5(6)(1)：顯然G是連通的。若G中含回路，則回路上任二結(jié)點之間有兩條基本通路，這與題設(shè)矛盾。因此，G連通且不含回路。G中每一對結(jié)點之間有惟一一條基本通路。(n≥2)G連通而不含回路(即G是樹)；2023/2/5樹的特點在結(jié)點給定的無向圖中，樹是邊數(shù)最多的無回路圖樹是邊數(shù)最少的連通圖由此可知，在無向圖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中各結(jié)點的度數(shù)均大于等于1。設(shè)T中有k個度數(shù)為1的結(jié)點(即k片葉)，其余的結(jié)點度數(shù)均大于等于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)分析判斷是否是生成樹，根據(jù)定義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是連通的。分析必要性由樹的定義即得，充分性利用構(gòu)造性方法，具體找出一顆生成樹即可證明必要性：假設(shè)TG=<V,ET>是G=<V,E>的生成樹，由定義10.2.1，TG是連通的，于是G也是連通的。充分性：假設(shè)G=<V,E>是連通的。如果G中無回路，G本身就是生成樹。如果G中存在回路C1，可刪除C1中一條邊得到圖G1，它仍連通且與G有相同的結(jié)點集。如果G1中無回路，G1就是生成樹。如果G1仍存在回路C2，可刪除C2中一條邊，如此繼續(xù)，直到得到一個無回路的連通圖H為止。因此，H是G的生成樹。2023/2/5破圈法與避圈法算法10.2.1

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

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

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

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

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

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

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

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

例10.2.8

假設(shè)有5個信息中心A、B、C、D、E，它們之間的距離(以百公里為單位)如圖所示。要交換數(shù)據(jù)，我們可以在任意兩個信息中心之間通過光纖連接，但是費用的限制要求鋪設(shè)盡可能少的光纖線路。重要的是每個信息中心能和其它中心通信，但并不需要在任意兩個中心之間都鋪設(shè)線路，可以通過其它中心轉(zhuǎn)發(fā)。ABCDE3547962879ABCDE3462分析這實際上就是求賦權(quán)連通圖的最小生成樹問題，可用Prim算法或Kruskal算法求解。解求得圖的最小生成樹如圖所示，w(T)=15百公里。即按圖的圖鋪設(shè)，使得鋪設(shè)的線路最短。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一棵非平凡的有向樹，如果恰有一個結(jié)點的入度為0，其余所有結(jié)點的入度均為1，則稱之為根樹(RootTree)或外向樹(OutwardTree)。入度為0的結(jié)點稱為根(Root)；出度為0的結(jié)點稱為葉(Leaf)；入度為1，出度大于0的結(jié)點稱為內(nèi)點(InteriorPoint)；又將內(nèi)點和根統(tǒng)稱為分支點(BranchPoint)。在根樹中，從根到任一結(jié)點v的通路長度，稱為該結(jié)點的層數(shù)(LayerNumber)；稱層數(shù)相同的結(jié)點在同一層上；所有結(jié)點的層數(shù)中最大的稱為根樹的高(Height)。2023/2/5例10.3.2判斷下圖所示的圖是否是根樹？若是根樹，給出其根、葉和內(nèi)點，計算所有結(jié)點所在的層數(shù)和高。v1v2v3v4v5v6v7v8v9v10v11v12v13v1v2v3v4v5v6v7v8v9v10v11v12v13解是一棵根樹，其中v1為根，v5,v6,v8,v9,v10,v12,v13為葉，v2,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；v13處在第四層，層數(shù)為4；這棵樹的高為4。倒置法

2023/2/5家族關(guān)系定義10.3.3

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

如果在根樹中規(guī)定了每一層上結(jié)點的次序，這樣的根樹稱為有序樹(OrderedTree)。一般地，在有序樹中同一層中結(jié)點的次序為從左至右。有時也可以用邊的次序來代替結(jié)點的次序。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中，任一結(jié)點v及其所有后代導(dǎo)出的子圖T’稱為T的以v為根的子樹(Subtree)。當然，T’也可以有自己的子樹。二元有序樹的每個結(jié)點v至多有兩個兒子，分別稱為v的左兒子(LeftSon)和右兒子(RightSon)。二元有序樹的每個結(jié)點v至多有兩棵子樹，分別稱為v的左子樹(LeftSubtree)和右子樹(RightSubtree)。注意區(qū)分以v為根的子樹和v的左(右)子樹，v為根的子樹包含v，而v的左(右)子樹不包含v。

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

3元樹

3元完全樹

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

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

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

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