資源描述：
《離散數(shù)學(xué)第九章：樹》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、樹第九章9.1無向樹及生成樹樹：連通而不含回路的無向圖稱為無向樹，簡稱樹，記作T。森林：連通分支數(shù)大于等于2，且每個(gè)連通分支均是樹的非連通無向圖。平凡樹：平凡圖為平凡樹。一、樹的概念森林樹葉:樹中度數(shù)為1的頂點(diǎn)分支點(diǎn):樹中度數(shù)?2的頂點(diǎn)樹的性質(zhì)：(1)G連通而不含回路；(2)每對(duì)頂點(diǎn)之間具有唯一一條初級(jí)通路(3)n=m+1(4)若在G中任意兩個(gè)不相鄰的頂點(diǎn)之間增加一條邊，就形成唯一一條初級(jí)回路。(5)連通且每條邊都是橋(6)連通但刪除任何一條邊后就不連通設(shè)G=是n階m條邊的無向樹，則下面各命題是等價(jià)的：性質(zhì)(7):任一棵非平凡樹T=
2、，至少有兩片葉。證明：設(shè)T有x片樹葉，由握手定理及定理9.1知，由上式解出x?2.生成樹：若圖G為無向連通圖.T為G的生成子圖，且T為樹，稱T為G的生成樹。三、生成樹及其構(gòu)造方法樹枝與弦：G在T中的邊稱為T的樹枝，G不在T中的邊稱為T的弦。余樹：T的弦的集合的導(dǎo)出子圖稱為T的余樹。生成樹余樹生成樹余樹例子無向連通圖的生成樹不一定唯一生成樹的余樹不一定是樹帶權(quán)圖的最小生成樹：設(shè)G=是帶權(quán)的連通簡單圖，具有權(quán)最小的生成樹稱為最小生成樹。T是G的一棵生成樹，T中所有枝的權(quán)之和稱為T的權(quán)，記作：W(T)。四、最小生成樹方法：避
3、圈法在不產(chǎn)生回路的基礎(chǔ)上依次畫出權(quán)值最小的邊，直至畫出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è)T是n階m條邊的無向連通圖G的一棵生成樹，設(shè)e1?,e2?,…,e?m?n+1為T的弦.設(shè)Cr為T添加弦er?產(chǎn)生的G中惟一的圈(由er?和樹枝組成),稱
4、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的一棵生成樹,e1?,e2?,…,e?n?1為T的樹枝，Si是G的只含樹枝ei?,其他邊都是弦的割集,稱Si為對(duì)應(yīng)生成樹T由樹枝ei?生成的基本割集。i=1,2,…,n?1.稱{S1,S2,…,Sn?1}為對(duì)應(yīng)T的基本割集系統(tǒng).六：基本割集與基本割集系統(tǒng)例9.1.4：Sa={a,f,g}Sb={b
5、,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根樹及其應(yīng)用一、樹的概念有向樹:基圖為無向樹的有向圖根樹:有一個(gè)頂點(diǎn)入度為0,其余的入度均為1的非平凡的有向樹樹根:有向樹中入度為0的頂點(diǎn)樹葉:有向樹中入度為1,出度為0的頂點(diǎn)內(nèi)點(diǎn):有向樹中入度為1,出度大于0的頂點(diǎn)分支點(diǎn):樹根與內(nèi)點(diǎn)的總稱(出度大于等于1）頂點(diǎn)v的層數(shù):從樹根到v的通路長度，記作l(v)樹高:有向樹中
6、頂點(diǎn)的最大層數(shù)，記作h(T)根樹的畫法:樹根放上方,省去所有有向邊上的箭頭如右圖所示a是樹根b,e,f,h,i是樹葉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.樹高為4定義把根樹看作一棵家族樹:(1)若頂點(diǎn)a鄰接到頂點(diǎn)b,則稱b是a的兒子,a是b的父親;(2)若b和c為同一個(gè)頂點(diǎn)的兒子,則稱b和c是兄弟;(3)若a?b且a可達(dá)b,則稱a是b的祖先,b是a的后代.(4)設(shè)v為根樹的一個(gè)頂點(diǎn)且不是樹根,稱v及其所有后代的導(dǎo)出子圖為以v為根的根子樹.家族樹：有序樹:每一層的結(jié)點(diǎn)均有序r元樹
7、:根樹的每個(gè)分支點(diǎn)至多有r個(gè)兒子r元正則樹:根樹的每個(gè)分支點(diǎn)恰有r個(gè)兒子r元完全正則樹:所有樹葉層數(shù)相同都等于樹高的r元正則樹r元有序樹:有序的r元樹r元正則有序樹:有序的r元正則樹r元完全正則有序樹:有序的r元完全正則樹根樹的分類：定義設(shè)2元樹T有t片樹葉v1,v2,…,vt,樹葉的權(quán)分別為w1,w2,…,wt,稱為T的權(quán),記作W(T),其中l(wèi)(vi)是vi的層數(shù).在所有有t片樹葉,帶權(quán)w1,w2,…,wt的2元樹中,權(quán)最小的2元樹稱為最優(yōu)2元樹.最優(yōu)二元樹：給定實(shí)數(shù)w1,w2,…,wt,①作t片樹葉,分別以w1,w2,…,wt為權(quán).②在所
8、有入度為0的頂點(diǎn)(不一定是樹葉)中選出兩個(gè)權(quán)最小的頂點(diǎn),添加一個(gè)新分支點(diǎn),以這2個(gè)頂點(diǎn)為兒子,其權(quán)等于這2個(gè)兒子的權(quán)之和.③重復(fù)②,直到只有1個(gè)入度為0的頂點(diǎn)為止.
