離散數(shù)學(xué)屈婉玲第十章課件

離散數(shù)學(xué)第十章樹主要內(nèi)容無向樹及其性質(zhì)生成樹●根樹及其應(yīng)用離散數(shù)學(xué)1離散數(shù)學(xué)10.1無向樹及其性質(zhì)定義101連通無回路的無向圖稱為無向樹,簡(jiǎn)稱樹每個(gè)連通分支都是樹的無向圖稱為森林.平凡圖稱為平凡樹.在無向樹中,懸掛頂點(diǎn)稱為樹葉,度數(shù)大于或等于2的頂點(diǎn)稱為分支點(diǎn)例星形樹離散數(shù)學(xué)2離散數(shù)學(xué)無向樹的性質(zhì)定理101設(shè)G=<VE>是m階m條邊的無向圖,則下面各命題是等價(jià)的:(1)G是樹(2)G中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑(3)G中無回路且m=n-1(4)G是連通的且m=n-1.(5)G是連通的且G中任何邊均為橋.(6)G中沒有回路,但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊后所得圖中有惟一的一個(gè)含新邊的圈.離散數(shù)學(xué)3離散數(shù)學(xué)證明證(1)→(2).若路徑不惟一,必有回路.(2)→(3.若G中有回路,則回路上任意兩點(diǎn)之間的路徑不惟一對(duì)n用歸納法證明m=n-1當(dāng)n=1時(shí)成立.設(shè)ns時(shí)成立,證n=k+1時(shí)也成立:任取一條邊e,Ge有且僅有兩個(gè)連通分支G1,G2·nk,由歸納假設(shè)得m=n-1,=1,2.于是,m=m1+m2+1=n1+n2-2+1=n-13)→(4).只需證明G連通用反證法.否則G有(s≥2)個(gè)連通分支,它們都是樹.于是,有m=m-1∑m=∑n-s=n-S(s≥2)這與m=n-1矛盾離散數(shù)學(xué)4離散數(shù)學(xué)證明(4)→(5).只需證明G中每條邊都是橋.下述命題顯然成立:G是n階m條邊的無向連通圖,則m≥n-1ve∈E,G-e只有n-2條邊,由命題可知Ge不連通,故e為橋.(5)→(6).由5易知G為樹.由(1)=(2)知,Va,v∈V(up),u到v有惟一路徑,加新邊(u,)得惟一的一個(gè)圈(6)→(1).只需證明G連通,這是顯然的離散數(shù)學(xué)5離散數(shù)學(xué)屈婉玲第十章課件6離散數(shù)學(xué)屈婉玲第十章課件7離散數(shù)學(xué)屈婉玲第十章課件8離散數(shù)學(xué)屈婉玲第十章課件9離散數(shù)學(xué)屈婉玲第十章課件10離散數(shù)學(xué)屈婉玲第十章課件11離散數(shù)學(xué)屈婉玲第十章課件12離散數(shù)學(xué)屈婉玲第十章課件13離散數(shù)學(xué)屈婉玲第十章課件14離散數(shù)學(xué)屈婉玲第十章課件15離散數(shù)學(xué)屈婉玲第十章課件16離散數(shù)學(xué)屈婉玲第十章課件17離散數(shù)學(xué)屈婉玲第十章課件18離散數(shù)學(xué)屈婉玲第十章課件19離散數(shù)學(xué)屈婉玲第十章課件20離散數(shù)學(xué)屈婉玲第十章課件21離散數(shù)學(xué)屈婉玲第十章課件22離散數(shù)學(xué)屈婉玲第十章課件23離散數(shù)學(xué)屈婉玲第十章課件24離散數(shù)學(xué)屈婉玲第十章課件25離散數(shù)學(xué)屈婉玲第十章課件26離散數(shù)學(xué)屈婉