離散數(shù)學(xué)課件-無向樹

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

1、離散數(shù)學(xué)李書杰合肥工業(yè)大學(xué)lisjhfut@hfut.edu.cn離散數(shù)學(xué)1學(xué)習(xí)內(nèi)容10.1無向樹10.2根樹23如果將上圖看作一個圖的話，這個圖就是一棵樹，如下圖。4定義10.2.1無向樹－－從無向圖出發(fā)定義的樹無向樹(樹):連通而無回路的無向圖，一般用T＝表示葉:樹中度數(shù)為1的頂點分支點/內(nèi)部結(jié)點:樹中度數(shù)>1的頂點森林:一個非連通圖，如果其每個連通分支都是樹，則稱為森林平凡樹:平凡圖，只有一個點且無邊的圖右圖為一棵12階樹.聲明:本章中所討論的回路均指簡單回路或初級回路5無向樹的性質(zhì)定理10.2.1設(shè)G=

2、是n階m條邊的無向圖，則下面各命題是等價的：（1）G是樹(連通無回路);（2）G中無回路且m=n?1;（3）G是連通的且m=n?1;（4）G中沒有回路,但在任何兩個不同的頂點之間加一條新邊,就會得到一條唯一的基本回路.（5）G是連通的且G中任何邊均為橋;（6）G中任意兩個頂點之間存在惟一的一條基本通路。6(1)?(2)的證明如果G是無回路的連通圖，則G中無回路且m=n?1，其中m是邊數(shù)，n是結(jié)點數(shù)證明歸納法。當(dāng)n=2時，因為G連通無回路，所以只有m=1，故m=n-1成立。假設(shè)n=k-1時命題成立，當(dāng)n=k時，因G是無回路且連通，則

3、至少有一個度為1的結(jié)點u，設(shè)與其關(guān)聯(lián)的邊為(u,w)，刪去u，得到一個k-1個結(jié)點的連通無向圖G’，7(1)?(2)的證明（續(xù)）由歸納假設(shè)可知，G’的邊數(shù)m’=n’-1=(k-1)-1=k-2。再將結(jié)點u及(u,w)放入原位，恢復(fù)到圖G，那么G的邊數(shù)m=m’+1=(k-2)+1=k-1，結(jié)點數(shù)n=n’+1=k，故m=n-1成立。8(2)?(3)的證明如果G中無回路且m=n?1，其中m是邊數(shù)，n是結(jié)點數(shù)，則連通且m=n?1;只須證明G是連通的。證明設(shè)G有k個連通分枝G1,…,Gk(k≥1），Gi有ni個結(jié)點,mi條邊，因為Gi連通無

4、回路，所以有mi=ni-1，n=n1+n2+…+nkm=m1+m2+…+mk=(n1-1)+(n2-1)+…+(nk-1)=n-k因為m=n-1，所以k=1，故G是連通的。9(3)?(4)的證明如果G連通且m=n?1，則G中無回路,但增加一條新邊，得到一個且僅有一個包含新邊的回路。證明歸納法。當(dāng)n=2時，m=n-1=1，必?zé)o回路，如果增加一邊得到且僅得到一個回路。設(shè)n=k-1時命題成立。考察n=k時的情況。因為G是連通的，所以每個結(jié)點u有deg(u)≥1，下面證明至少有一個結(jié)點u0使deg(u0)=1。若不存在，則每個結(jié)點的度至少

5、為2，所以2n≥2m，即n≥m，這與m=n-1矛盾。10(3)?(4)的證明首先證明G中也無回路刪去u0及其關(guān)聯(lián)的邊，得到含有k-1個結(jié)點的圖G’，G’連通且m’=n’?1。由歸納假設(shè)知G’無回路。在G’中加入u0及其關(guān)聯(lián)的邊恢復(fù)到G，則G無回路。再證明在G中任意兩結(jié)點之間增加一條邊，得到一條且僅有一條回路。若在G中增加一條邊(ui,uj)，因為G連通，則在G中存在一條從ui到uj的路，那么這條路與新加入的邊(ui,uj)構(gòu)成回路，而且這個回路是唯一的。若不唯一，刪掉邊(ui,uj)邊,G中必有回路，矛盾。11(4)?(5)的證明

6、如果G中無回路,但增加一條新邊，得到一個且僅有一個包含新邊的回路，則G連通且每條邊均為橋。證明反證法。假設(shè)G不連通，則存在結(jié)點ui與uj，在ui和uj之間沒有路，所以增加邊(ui,uj)不會產(chǎn)生回路，與已知矛盾。由于G無回路，故刪掉任意條邊e都使G-e為非連通，所以G中每條邊都是橋。12(5)?(6)的證明如果G連通且每條邊均為橋，則G中任意兩個結(jié)點之間存在惟一的路徑。證明由G是連通的可知，任意兩個結(jié)點間有一條路，若存在兩點它們之間有多于一條的路，則G中必有回路，刪去該回路上任一邊，圖仍是連通的，與G中每條邊都是橋矛盾。13(6)

7、?(1)的證明如果G中任意兩個結(jié)點之間存在惟一的路徑，則G是無回路的連通圖。證明因為任意兩結(jié)點間有唯一條路，則圖G必連通。若G有回路，則在回路上任意兩結(jié)點間有兩條路，與已知矛盾。14定理10.2.2設(shè)T是n階非平凡的無向樹，則T中至少有兩片樹葉.證設(shè)T有x片樹葉，m條邊。由握手定理及定理10.2.1可知，由上式解出x?2.無向樹的性質(zhì)(續(xù))15例題例1已知無向樹T中,有1個3度頂點,2個2度頂點,其余頂點全是樹葉.試求樹葉數(shù),并畫出滿足要求的非同構(gòu)的無向樹.解用樹的性質(zhì)m=n?1和握手定理.設(shè)有x片樹葉，于是n=1+2+x=3+x

8、,2m=2(n?1)=2?(2+x)=1?3+2?2+x解出x=3，故T有3片樹葉.T的度數(shù)列為1,1,1,2,2,3有2棵非同構(gòu)的無向樹,如圖所示16例題例2已知無向樹T有5片樹葉,2度與3度頂點各1個,其余頂點的度數(shù)均為4.求T的階數(shù)n.解設(shè)T