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

《離散數(shù)學(xué)課件-無向樹》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(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如果將上圖看作一個(gè)圖的話，這個(gè)圖就是一棵樹，如下圖。4定義10.2.1無向樹－－從無向圖出發(fā)定義的樹無向樹(樹):連通而無回路的無向圖，一般用T＝表示葉:樹中度數(shù)為1的頂點(diǎn)分支點(diǎn)/內(nèi)部結(jié)點(diǎn):樹中度數(shù)>1的頂點(diǎn)森林:一個(gè)非連通圖，如果其每個(gè)連通分支都是樹，則稱為森林平凡樹:平凡圖，只有一個(gè)點(diǎn)且無邊的圖右圖為一棵12階樹.聲明:本章中所討論的回路均指簡單回路或初級(jí)回路5無向樹的性質(zhì)定理10.2.1設(shè)G=

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

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

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

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

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

7、?(1)的證明如果G中任意兩個(gè)結(jié)點(diǎn)之間存在惟一的路徑，則G是無回路的連通圖。證明因?yàn)槿我鈨山Y(jié)點(diǎn)間有唯一條路，則圖G必連通。若G有回路，則在回路上任意兩結(jié)點(diǎn)間有兩條路，與已知矛盾。14定理10.2.2設(shè)T是n階非平凡的無向樹，則T中至少有兩片樹葉.證設(shè)T有x片樹葉，m條邊。由握手定理及定理10.2.1可知，由上式解出x?2.無向樹的性質(zhì)(續(xù))15例題例1已知無向樹T中,有1個(gè)3度頂點(diǎn),2個(gè)2度頂點(diǎn),其余頂點(diǎn)全是樹葉.試求樹葉數(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度頂點(diǎn)各1個(gè),其余頂點(diǎn)的度數(shù)均為4.求T的階數(shù)n.解設(shè)T