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