《離散數(shù)學(xué)-樹》PPT課件.ppt

《《離散數(shù)學(xué)-樹》PPT課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第16章樹離散數(shù)學(xué)本章說(shuō)明樹是圖論中重要內(nèi)容之一。本章所談回路均指初級(jí)回路（圈）或簡(jiǎn)單回路，不含復(fù)雜回路（有重復(fù)邊出現(xiàn)的回路）。16.1無(wú)向樹及其性質(zhì)定義16.1無(wú)向樹——連通無(wú)回路的無(wú)向圖，簡(jiǎn)稱樹，用T表示。平凡樹——平凡圖。森林——若無(wú)向圖G至少有兩個(gè)連通分支（每個(gè)都是樹）。樹葉——無(wú)向圖中懸掛頂點(diǎn)。分支點(diǎn)——度數(shù)大于或等于2的頂點(diǎn)。舉例如圖為九個(gè)頂點(diǎn)的樹。定理16.1設(shè)G＝是n階m條邊的無(wú)向圖，則下面各命題是等價(jià)的：（1）G是樹。（2）G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑。（3）G中無(wú)回路且m＝n?1。

2、（4）G是連通的且m＝n?1。（5）G是連通的且G中任何邊均為橋。（6）G中沒(méi)有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到唯一的一個(gè)含新邊的圈。無(wú)向樹的等價(jià)定義(1)?(2)如果G是樹，則G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑。存在性。由G的連通性及定理14.5的推論（在n階圖G中，若從頂點(diǎn)vi到vj(vi?vj)存在通路，則vi到vj一定存在長(zhǎng)度小于等于n-1的初級(jí)通路(路徑)）可知，?u,v∈V，u與v之間存在路徑。唯一性（反證法）。若路徑不是唯一的，設(shè)Г1與Г2都是u到v的路徑，易知必存在由Г1和Г

3、2上的邊構(gòu)成的回路，這與G中無(wú)回路矛盾。(2)?(3)如果G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑，則G中無(wú)回路且m＝n-1。首先證明G中無(wú)回路。若G中存在關(guān)聯(lián)某頂點(diǎn)v的環(huán)，則v到v存在長(zhǎng)為0和1的兩條路經(jīng)(注意初級(jí)回路是路徑的特殊情況)，這與已知矛盾。若G中存在長(zhǎng)度大于或等于2的圈，則圈上任何兩個(gè)頂點(diǎn)之間都存在兩條不同的路徑，這也與已知矛盾。(2)?(3)如果G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑，則G中無(wú)回路且m＝n-1。其次證明m＝n-1。（歸納法）n＝1時(shí)，G為平凡圖，結(jié)論顯然成立。設(shè)n≤k(k≥1)時(shí)結(jié)論成立，當(dāng)n=

4、k+1時(shí)，設(shè)e＝(u,v)為G中的一條邊，由于G中無(wú)回路，所以G-e為兩個(gè)連通分支G1、G2。設(shè)ni、mi分別為Gi中的頂點(diǎn)數(shù)和邊數(shù)，則ni≤k，i＝1,2，由歸納假設(shè)可知mi＝ni-1，于是m＝m1+m2+1＝n1-1+n2-1+1＝n1+n2-1＝n-1。只需證明G是連通的。（采用反證法）假設(shè)G是不連通的，由s(s≥2)個(gè)連通分支G1,G2,…,Gs組成，并且Gi中均無(wú)回路，因而Gi全為樹。由(1)?(2)?(3)可知，mi＝ni-1。于是，由于s≥2，與m＝n-1矛盾。(3)?(4)如果G中無(wú)回路且m＝n-1，

5、則G是連通的且m＝n-1。如果G是連通的且m＝n?1，則G是連通的且G中任何邊均為橋。只需證明G中每條邊均為橋。?e∈E，均有

6、E(G-e)

7、＝n-1-1＝n-2，由習(xí)題十四題49（若G是n階m條邊的無(wú)向連通圖，則m≥n-1）可知，G-e已不是連通圖，所以，e為橋。(4)?(5)如果G是連通的且G中任何邊均為橋，則G中沒(méi)有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到唯一的一個(gè)含新邊的圈。因?yàn)镚中每條邊均為橋，刪掉任何邊，將使G變成不連通圖，所以，G中沒(méi)有回路，也即G中無(wú)圈。又由于G連通，所以G為樹，由(

8、1)?(2)可知，?u,v∈V，且u≠v，則u與v之間存在唯一的路徑Г，則Г∪(u,v)（(u,v)為加的新邊）為G中的圈，顯然圈是唯一的。(5)?(6)如果G中沒(méi)有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到唯一的一個(gè)含新邊的圈，則G是樹。只需證明G是連通的。?u,v∈V，且u≠v，則新邊(u,v)∪G產(chǎn)生唯一的圈C，顯然有C-(u,v)為G中u到v的通路，故u～v，由u,v的任意性可知，G是連通的。(6)?(1)定理16.2設(shè)T是n階非平凡的無(wú)向樹，則T中至少有兩片樹葉。設(shè)T有x片樹葉，由握手定理及

9、定理16.1可知，證明由上式解出x≥2。無(wú)向樹的性質(zhì)例16.1例16.1畫出6階所有非同構(gòu)的無(wú)向樹。解答設(shè)Ti是6階無(wú)向樹。由定理16.1可知，Ti的邊數(shù)mi＝5，由握手定理可知，∑dTi(vj)＝10，且δ(Ti)≥1，△(Ti)≤5。于是Ti的度數(shù)列必為以下情況之一。(1)1，1，1，1，1，5(2)1，1，1，1，2，4(3)1，1，1，1，3，3(4)1，1，1，2，2，3(5)1，1，2，2，2，2(4)對(duì)應(yīng)兩棵非同構(gòu)的樹，在一棵樹中兩個(gè)2度頂點(diǎn)相鄰，在另一棵樹中不相鄰，其他情況均能畫出一棵非同構(gòu)的樹。例1

10、6.1人們常稱只有一個(gè)分支點(diǎn)，且分支點(diǎn)的度數(shù)為n-1的n(n≥3)階無(wú)向樹為星形圖，稱唯一的分支點(diǎn)為星心。例16.2例16.27階無(wú)向圖有3片樹葉和1個(gè)3度頂點(diǎn)，其余3個(gè)頂點(diǎn)的度數(shù)均無(wú)1和3。試畫出滿足要求的所有非同構(gòu)的無(wú)向樹。解答設(shè)Ti為滿足要求的無(wú)向樹，則邊數(shù)mi＝6，于是∑d(vj)＝12＝e+3+d(v4)+d(v5)+d(v6)。由于