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

離散數(shù)學(xué)第十章樹(shù)主要內(nèi)容無(wú)向樹(shù)及其性質(zhì)生成樹(shù)●根樹(shù)及其應(yīng)用離散數(shù)學(xué)1離散數(shù)學(xué)10.1無(wú)向樹(shù)及其性質(zhì)定義101連通無(wú)回路的無(wú)向圖稱為無(wú)向樹(shù),簡(jiǎn)稱樹(shù)每個(gè)連通分支都是樹(shù)的無(wú)向圖稱為森林.平凡圖稱為平凡樹(shù).在無(wú)向樹(shù)中,懸掛頂點(diǎn)稱為樹(shù)葉,度數(shù)大于或等于2的頂點(diǎn)稱為分支點(diǎn)例星形樹(shù)離散數(shù)學(xué)2離散數(shù)學(xué)無(wú)向樹(shù)的性質(zhì)定理101設(shè)G=<VE>是m階m條邊的無(wú)向圖,則下面各命題是等價(jià)的:(1)G是樹(shù)(2)G中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑(3)G中無(wú)回路且m=n-1(4)G是連通的且m=n-1.(5)G是連通的且G中任何邊均為橋.(6)G中沒(méi)有回路,但在任何兩個(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è)連通分支,它們都是樹(shù).于是,有m=m-1∑m=∑n-s=n-S(s≥2)這與m=n-1矛盾離散數(shù)學(xué)4離散數(shù)學(xué)證明(4)→(5).只需證明G中每條邊都是橋.下述命題顯然成立:G是n階m條邊的無(wú)向連通圖,則m≥n-1ve∈E,G-e只有n-2條邊,由命題可知Ge不連通,故e為橋.(5)→(6).由5易知G為樹(shù).由(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é)屈婉玲第十章課件27離散數(shù)學(xué)屈婉玲第十章課件28離散數(shù)學(xué)屈婉玲第十章課件29離散數(shù)學(xué)屈婉玲第十章課件30離散數(shù)學(xué)第十章樹(shù)主要內(nèi)容無(wú)向樹(shù)及其性質(zhì)生成樹(shù)●根樹(shù)及其應(yīng)用離散數(shù)學(xué)31離散數(shù)學(xué)10.1無(wú)向樹(shù)及其性質(zhì)定義101連通無(wú)回路的無(wú)向圖稱為無(wú)向樹(shù),簡(jiǎn)稱樹(shù)每個(gè)連通分支都是樹(shù)的無(wú)向圖稱為森林.平凡圖稱為平凡樹(shù).在無(wú)向樹(shù)中,懸掛頂點(diǎn)稱為樹(shù)葉,度數(shù)大于或等于2的頂點(diǎn)稱為分支點(diǎn)例星形樹(shù)離散數(shù)學(xué)32離散數(shù)學(xué)無(wú)向樹(shù)的性質(zhì)定理101設(shè)G=<VE>是m階m條邊的無(wú)向圖,則下面各命題是等價(jià)的:(1)G是樹(shù)(2)G中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑(3)G中無(wú)回路且m=n-1(4)G是連通的且m=n-1.(5)G是連通的且G中任何邊均為橋.(6)G中沒(méi)有回路,但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊后所得圖中有惟一的一個(gè)含新邊的圈.離散數(shù)學(xué)33離散數(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è)連通分支,它們都是樹(shù).于是,有m=m-1∑m=∑n-s=n-S(s≥2)這與m=n-1矛盾離散數(shù)學(xué)34離散數(shù)學(xué)證明(4)→(5).只需證明G中每條邊都是橋.下述命題顯然成立:G是n階m條邊的無(wú)向連通圖,則m≥n-1ve∈E,G-e只有n-2條邊,由命題可知Ge不連通,故e為橋.(5)→(6).由5易知G為樹(shù).由(1)=(2)知,Va,v∈V(up),u到v有惟一路徑,加新邊(u,)得惟一的一個(gè)圈(6)→(1).只需證明G連通,這是顯然的離散數(shù)學(xué)35離散數(shù)學(xué)屈婉玲第十章課件36離散數(shù)學(xué)屈婉玲第十章課件37離散數(shù)學(xué)屈婉玲第十章課件38離散數(shù)學(xué)屈婉玲第十章課件39離散數(shù)學(xué)屈婉玲第十章課件40離散數(shù)學(xué)屈婉玲第十章課件41離散數(shù)學(xué)屈婉玲第十章課件42離散數(shù)學(xué)屈婉玲第十章課件43離散數(shù)學(xué)屈婉玲第十章課件44離散數(shù)學(xué)屈婉玲第十章課件45離散數(shù)學(xué)屈婉玲第十章課件46離散數(shù)學(xué)屈婉玲第十章課件47離散數(shù)學(xué)屈婉玲第十章課件48離散數(shù)學(xué)屈婉玲第十章課件49離散數(shù)學(xué)屈婉玲第十章課件50離散數(shù)學(xué)屈婉玲第十章課件51離散數(shù)學(xué)屈婉玲第十章課件52離散數(shù)學(xué)屈婉玲第十章