離散數(shù)學(xué) 第九章：樹(shù).ppt

《離散數(shù)學(xué) 第九章：樹(shù).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫(kù)。

1、樹(shù)第九章9.1無(wú)向樹(shù)及生成樹(shù)樹(shù)：連通而不含回路的無(wú)向圖稱為無(wú)向樹(shù)，簡(jiǎn)稱樹(shù)，記作T。森林：連通分支數(shù)大于等于2，且每個(gè)連通分支均是樹(shù)的非連通無(wú)向圖。平凡樹(shù)：平凡圖為平凡樹(shù)。一、樹(shù)的概念森林樹(shù)葉:樹(shù)中度數(shù)為1的頂點(diǎn)分支點(diǎn):樹(shù)中度數(shù)?2的頂點(diǎn)樹(shù)的性質(zhì)：(1)G連通而不含回路；(2)每對(duì)頂點(diǎn)之間具有唯一一條初級(jí)通路(3)n=m+1(4)若在G中任意兩個(gè)不相鄰的頂點(diǎn)之間增加一條邊，就形成唯一一條初級(jí)回路。(5)連通且每條邊都是橋(6)連通但刪除任何一條邊后就不連通設(shè)G=是n階m條邊的無(wú)向樹(shù)，則下面各命題是等價(jià)的：性

2、質(zhì)(7):任一棵非平凡樹(shù)T=，至少有兩片葉。證明：設(shè)T有x片樹(shù)葉，由握手定理及定理9.1知，由上式解出x?2.生成樹(shù)：若圖G為無(wú)向連通圖.T為G的生成子圖，且T為樹(shù)，稱T為G的生成樹(shù)。三、生成樹(shù)及其構(gòu)造方法樹(shù)枝與弦：G在T中的邊稱為T(mén)的樹(shù)枝，G不在T中的邊稱為T(mén)的弦。余樹(shù)：T的弦的集合的導(dǎo)出子圖稱為T(mén)的余樹(shù)。生成樹(shù)余樹(shù)生成樹(shù)余樹(shù)例子無(wú)向連通圖的生成樹(shù)不一定唯一生成樹(shù)的余樹(shù)不一定是樹(shù)帶權(quán)圖的最小生成樹(shù)：設(shè)G=是帶權(quán)的連通簡(jiǎn)單圖，具有權(quán)最小的生成樹(shù)稱為最小生成樹(shù)。T是G的一棵生成樹(shù)，T中所有枝的

3、權(quán)之和稱為T(mén)的權(quán)，記作：W(T)。四、最小生成樹(shù)方法：避圈法在不產(chǎn)生回路的基礎(chǔ)上依次畫(huà)出權(quán)值最小的邊，直至畫(huà)出n-1條邊為止v15656541v2v4v5v323例9.1.1：5v1541v2v4v5v323W(T)=1+2+3+4+5=15651v2v4v5v323例9.1.2：v1551v2v4v5v323v1565551v2v4v5v32355oror551v2v4v5v323W(T)=1+2+3+5+5=16！最小生成樹(shù)不一定唯一定義：設(shè)T是n階m條邊的無(wú)向連通圖G的一棵生成樹(shù)，設(shè)e1?,e2?,…,e?m

4、?n+1為T(mén)的弦.設(shè)Cr為T(mén)添加弦er?產(chǎn)生的G中惟一的圈(由er?和樹(shù)枝組成),稱Cr為對(duì)應(yīng)弦er?的基本回路r=1,2,…,m?n+1.稱{C1,C2,…,Cm?n+1}為對(duì)應(yīng)T的基本回路系統(tǒng).五：基本回路與基本回路系統(tǒng)例9.1.3：Ca=aefCb=bdeCc=cdf基本回路系統(tǒng)為：{Ca,Cb,Cc}定義：設(shè)T是n階連通圖G的一棵生成樹(shù),e1?,e2?,…,e?n?1為T(mén)的樹(shù)枝，Si是G的只含樹(shù)枝ei?,其他邊都是弦的割集,稱Si為對(duì)應(yīng)生成樹(shù)T由樹(shù)枝ei?生成的基本割集。i=1,2,…,n?1.稱{S1,S

5、2,…,Sn?1}為對(duì)應(yīng)T的基本割集系統(tǒng).六：基本割集與基本割集系統(tǒng)例9.1.4：Sa={a,f,g}Sb={b,g,h}Sd={d,h,i}Sc={c,f,h}Se={e,f,i}基本割集系統(tǒng)為：{Sa,Sb,Sc,Sd,Se}課后例題：9.5，9.6，9.7，9.8課后作業(yè)：9.1，9.3，9.4，9.5，9.6，9.7，9.89.2根樹(shù)及其應(yīng)用一、樹(shù)的概念有向樹(shù):基圖為無(wú)向樹(shù)的有向圖根樹(shù):有一個(gè)頂點(diǎn)入度為0,其余的入度均為1的非平凡的有向樹(shù)樹(shù)根:有向樹(shù)中入度為0的頂點(diǎn)樹(shù)葉:有向樹(shù)中入度為1,出度為0的頂點(diǎn)內(nèi)點(diǎn)

6、:有向樹(shù)中入度為1,出度大于0的頂點(diǎn)分支點(diǎn):樹(shù)根與內(nèi)點(diǎn)的總稱(出度大于等于1）頂點(diǎn)v的層數(shù):從樹(shù)根到v的通路長(zhǎng)度，記作l(v)樹(shù)高:有向樹(shù)中頂點(diǎn)的最大層數(shù)，記作h(T)根樹(shù)的畫(huà)法:樹(shù)根放上方,省去所有有向邊上的箭頭如右圖所示a是樹(shù)根b,e,f,h,i是樹(shù)葉c,d,g是內(nèi)點(diǎn)a,c,d,g是分支點(diǎn)a為0層;1層有b,c;2層有d,e,f;3層有g(shù),h;4層有i.樹(shù)高為4定義把根樹(shù)看作一棵家族樹(shù):(1)若頂點(diǎn)a鄰接到頂點(diǎn)b,則稱b是a的兒子,a是b的父親;(2)若b和c為同一個(gè)頂點(diǎn)的兒子,則稱b和c是兄弟;(3)若a?b

7、且a可達(dá)b,則稱a是b的祖先,b是a的后代.(4)設(shè)v為根樹(shù)的一個(gè)頂點(diǎn)且不是樹(shù)根,稱v及其所有后代的導(dǎo)出子圖為以v為根的根子樹(shù).家族樹(shù)：有序樹(shù):每一層的結(jié)點(diǎn)均有序r元樹(shù):根樹(shù)的每個(gè)分支點(diǎn)至多有r個(gè)兒子r元正則樹(shù):根樹(shù)的每個(gè)分支點(diǎn)恰有r個(gè)兒子r元完全正則樹(shù):所有樹(shù)葉層數(shù)相同都等于樹(shù)高的r元正則樹(shù)r元有序樹(shù):有序的r元樹(shù)r元正則有序樹(shù):有序的r元正則樹(shù)r元完全正則有序樹(shù):有序的r元完全正則樹(shù)根樹(shù)的分類：定義設(shè)2元樹(shù)T有t片樹(shù)葉v1,v2,…,vt,樹(shù)葉的權(quán)分別為w1,w2,…,wt,稱為T(mén)的權(quán),記作W(T),其中l(wèi)(v

8、i)是vi的層數(shù).在所有有t片樹(shù)葉,帶權(quán)w1,w2,…,wt的2元樹(shù)中,權(quán)最小的2元樹(shù)稱為最優(yōu)2元樹(shù).最優(yōu)二元樹(shù)：給定實(shí)數(shù)w1,w2,…,wt,①作t片樹(shù)葉,分別以w1,w2,…,wt為權(quán).②在所有入度為0的頂點(diǎn)(不一定是樹(shù)葉)中選出兩個(gè)權(quán)最小的頂點(diǎn),添加一個(gè)新分支點(diǎn),以這2個(gè)頂點(diǎn)為兒子,其權(quán)等于這2個(gè)兒子的權(quán)之和.③重復(fù)②,直到只有1個(gè)入度為0的頂點(diǎn)為止.