資源描述：
《離散數(shù)學(xué)樹PPT課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第16章樹離散數(shù)學(xué)本章說明樹是圖論中重要內(nèi)容之一。本章所談回路均指初級回路（圈）或簡單回路，不含復(fù)雜回路（有重復(fù)邊出現(xiàn)的回路）。216.1無向樹及其性質(zhì)定義16.1無向樹——連通無回路的無向圖，簡稱樹，用T表示。平凡樹——平凡圖。森林——若無向圖G至少有兩個連通分支（每個都是樹）。樹葉——無向圖中懸掛頂點。分支點——度數(shù)大于或等于2的頂點。舉例如圖為九個頂點的樹。3定理16.1設(shè)G＝是n階m條邊的無向圖，則下面各命題是等價的：（1）G是樹。（2）G中任意兩個頂點之間存在唯一的路徑。（3）G中無回路且m＝n?1。（4）G是連通的且m＝n?1。（5）G
2、是連通的且G中任何邊均為橋。（6）G中沒有回路，但在任何兩個不同的頂點之間加一條新邊，在所得圖中得到唯一的一個含新邊的圈。無向樹的等價定義4(1)?(2)如果G是樹，則G中任意兩個頂點之間存在唯一的路徑。存在性。由G的連通性及定理14.5的推論（在n階圖G中，若從頂點vi到vj(vi?vj)存在通路，則vi到vj一定存在長度小于等于n-1的初級通路(路徑)）可知，?u,v∈V，u與v之間存在路徑。唯一性（反證法）。若路徑不是唯一的，設(shè)Г1與Г2都是u到v的路徑，易知必存在由Г1和Г2上的邊構(gòu)成的回路，這與G中無回路矛盾。5(2)?(3)如果G中任意兩個頂點之
3、間存在唯一的路徑，則G中無回路且m＝n-1。首先證明G中無回路。若G中存在關(guān)聯(lián)某頂點v的環(huán)，則v到v存在長為0和1的兩條路經(jīng)(注意初級回路是路徑的特殊情況)，這與已知矛盾。若G中存在長度大于或等于2的圈，則圈上任何兩個頂點之間都存在兩條不同的路徑，這也與已知矛盾。6(2)?(3)如果G中任意兩個頂點之間存在唯一的路徑，則G中無回路且m＝n-1。其次證明m＝n-1。（歸納法）n＝1時，G為平凡圖，結(jié)論顯然成立。設(shè)n≤k(k≥1)時結(jié)論成立，當(dāng)n=k+1時，設(shè)e＝(u,v)為G中的一條邊，由于G中無回路，所以G-e為兩個連通分支G1、G2。設(shè)ni、mi分別為Gi
4、中的頂點數(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。7只需證明G是連通的。（采用反證法）假設(shè)G是不連通的，由s(s≥2)個連通分支G1,G2,…,Gs組成，并且Gi中均無回路，因而Gi全為樹。由(1)?(2)?(3)可知，mi＝ni-1。于是，由于s≥2，與m＝n-1矛盾。(3)?(4)如果G中無回路且m＝n-1，則G是連通的且m＝n-1。8如果G是連通的且m＝n?1，則G是連通的且G中任何邊均為橋。只需證明G中每條邊均為橋。?e∈E，均有
5、E(G-e)
6、＝n-1-1
7、＝n-2，由習(xí)題十四題49（若G是n階m條邊的無向連通圖，則m≥n-1）可知，G-e已不是連通圖，所以，e為橋。(4)?(5)9如果G是連通的且G中任何邊均為橋，則G中沒有回路，但在任何兩個不同的頂點之間加一條新邊，在所得圖中得到唯一的一個含新邊的圈。因為G中每條邊均為橋，刪掉任何邊，將使G變成不連通圖，所以，G中沒有回路，也即G中無圈。又由于G連通，所以G為樹，由(1)?(2)可知，?u,v∈V，且u≠v，則u與v之間存在唯一的路徑Г，則Г∪(u,v)（(u,v)為加的新邊）為G中的圈，顯然圈是唯一的。(5)?(6)10如果G中沒有回路，但在任何兩個不同的
8、頂點之間加一條新邊，在所得圖中得到唯一的一個含新邊的圈，則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)11定理16.2設(shè)T是n階非平凡的無向樹，則T中至少有兩片樹葉。設(shè)T有x片樹葉，由握手定理及定理16.1可知，證明由上式解出x≥2。無向樹的性質(zhì)12例16.1例16.1畫出6階所有非同構(gòu)的無向樹。解答設(shè)Ti是6階無向樹。由定理16.1可知，Ti的邊數(shù)mi＝5，由握手定理可知，∑dTi(vj)＝10，且δ(Ti)≥1，△
9、(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)對應(yīng)兩棵非同構(gòu)的樹，在一棵樹中兩個2度頂點相鄰，在另一棵樹中不相鄰，其他情況均能畫出一棵非同構(gòu)的樹。13例16.1人們常稱只有一個分支點，且分支點的度數(shù)為n-1的n(n≥3)階無向樹為星形圖，稱唯一的分支點為星心。14例16.2例16.27階無向圖有3片樹葉和1個3度頂點，其余3個頂點的度數(shù)均無1和3。試畫出滿足要求的所有非同構(gòu)的無向樹。解答設(shè)Ti為滿足要求的無向樹，
10、則邊數(shù)mi＝6，于是∑d(vj)＝12＝e+3+d(
