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

離散數(shù)學(xué)第十章樹主要內(nèi)容無向樹及其性質(zhì)生成樹●根樹及其應(yīng)用離散數(shù)學(xué)1離散數(shù)學(xué)10.1無向樹及其性質(zhì)定義101連通無回路的無向圖稱為無向樹,簡稱樹每個連通分支都是樹的無向圖稱為森林.平凡圖稱為平凡樹.在無向樹中,懸掛頂點稱為樹葉,度數(shù)大于或等于2的頂點稱為分支點例星形樹離散數(shù)學(xué)2離散數(shù)學(xué)無向樹的性質(zhì)定理101設(shè)G=<VE>是m階m條邊的無向圖,則下面各命題是等價的:(1)G是樹(2)G中任意兩個頂點之間存在惟一的路徑(3)G中無回路且m=n-1(4)G是連通的且m=n-1.(5)G是連通的且G中任何邊均為橋.(6)G中沒有回路,但在任何兩個不同的頂點之間加一條新邊后所得圖中有惟一的一個含新邊的圈.離散數(shù)學(xué)3離散數(shù)學(xué)證明證(1)→(2).若路徑不惟一,必有回路.(2)→(3.若G中有回路,則回路上任意兩點之間的路徑不惟一對n用歸納法證明m=n-1當(dāng)n=1時成立.設(shè)ns時成立,證n=k+1時也成立:任取一條邊e,Ge有且僅有兩個連通分支G1,G2·nk,由歸納假設(shè)得m=n-1,=1,2.于是,m=m1+m2+1=n1+n2-2+1=n-13)→(4).只需證明G連通用反證法.否則G有(s≥2)個連通分支,它們都是樹.于是,有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,)得惟一的一個圈(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é)屈婉