資源描述：
《無向樹及生成樹ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第9章樹9.1無向樹及生成樹9.2根樹及其應(yīng)用19.1無向樹及生成樹無向樹、森林樹枝、弦、余樹生成樹基本回路與基本回路系統(tǒng)基本割集與基本割集系統(tǒng)最小生成樹2無向樹無向樹(樹):連通而無回路的無向圖，用T表示.平凡樹:平凡圖森林:每個連通分支都是樹的非連通的無向圖樹葉:樹中度數(shù)為1的頂點分支點:樹中度數(shù)?2的頂點右圖為一棵12階樹.聲明:本章中所討論的回路均指簡單回路或初級回路3無向樹的性質(zhì)定理9.1設(shè)G=是n階m條邊的無向圖，則下面各命題是等價的：（1）G是樹(連通無回路);（2）G中任意兩個頂點之
2、間存在惟一的路徑;（3）G中無回路且m=n?1;（4）G是連通的且m=n?1;（5）G是連通的且G中任何邊均為橋;（6）G中沒有回路,但在任何兩個不同的頂點之間加一條新邊后所得圖中有惟一的一個含新邊的圈.4無向樹的性質(zhì)(續(xù))定理9.2設(shè)T是n階非平凡的無向樹，則T中至少有兩片樹葉.證設(shè)T有x片樹葉，由握手定理及定理9.1可知，由上式解出x?2.5例題例1已知無向樹T中,有1個3度頂點,2個2度頂點,其余頂點全是樹葉.試求樹葉數(shù),并畫出滿足要求的非同構(gòu)的無向樹.解用樹的性質(zhì)m=n?1和握手定理.設(shè)有x片樹葉，于
3、是n=1+2+x=3+x,2m=2(n?1)=2?(2+x)=1?3+2?2+x解出x=3，故T有3片樹葉.T的度數(shù)列為1,1,1,2,2,3有2棵非同構(gòu)的無向樹,如圖所示6例題例2已知無向樹T有5片樹葉,2度與3度頂點各1個,其余頂點的度數(shù)均為4.求T的階數(shù)n,并畫出滿足要求的所有非同構(gòu)的無向樹.解設(shè)T的階數(shù)為n,則邊數(shù)為n?1,4度頂點的個數(shù)為n?7.由握手定理得2m=2(n?1)=5?1+2?1+3?1+4(n?7)解出n=8,4度頂點為1個.T的度數(shù)列為1,1,1,1,1,2,3,4有3棵非同構(gòu)的無向
4、樹7生成樹設(shè)G為無向連通圖G的生成樹:G的生成子圖并且是樹生成樹T的樹枝:G在T中的邊生成樹T的弦:G不在T中的邊生成樹T的余樹:所有弦的集合的導(dǎo)出子圖注意：不一定連通,也不一定不含回路.右圖黑邊構(gòu)成生成樹紅邊構(gòu)成余樹8生成樹的存在性定理任何無向連通圖都有生成樹.證用破圈法.若圖中無圈,則圖本身就是自己的生成樹.否則刪去圈上的任一條邊,這不破壞連通性,重復(fù)進行直到無圈為止,剩下的圖是一棵生成樹.推論1設(shè)n階無向連通圖有m條邊,則m?n?1.推論2設(shè)n階無向連通圖有m條邊,則它的生成樹的余樹有m?n+1條邊.推
5、論3設(shè)為G的生成樹T的余樹，C為G中任意一個圈，則C與一定有公共邊.9基本回路與基本回路系統(tǒng)定義設(shè)T是n階m條邊的無向連通圖G的一棵生成樹，設(shè)e1?,e2?,…,e?m?n+1為T的弦.設(shè)Cr為T添加弦er?產(chǎn)生的G中惟一的圈(由er?和樹枝組成),稱Cr為對應(yīng)弦er?的基本回路或基本圈,r=1,2,…,m?n+1.稱{C1,C2,…,Cm?n+1}為對應(yīng)T的基本回路系統(tǒng).求基本回路的算法:設(shè)弦e=(u,v),先求T中u到v的路徑?uv,再并上弦e,即得對應(yīng)e的基本回路.10基本割集與基本割集系統(tǒng)定義設(shè)T是n
6、階連通圖G的一棵生成樹,e1?,e2?,…,e?n?1為T的樹枝，Si是G的只含樹枝ei?,其他邊都是弦的割集,稱Si為對應(yīng)生成樹T由樹枝ei?生成的基本割集,i=1,2,…,n?1.稱{S1,S2,…,Sn?1}為對應(yīng)T的基本割集系統(tǒng).求基本割集的算法:設(shè)e?為生成樹T的樹枝,T?e?由兩棵子樹T1與T2組成,令Se?={e
7、e?E(G)且e的兩個端點分別屬于T1與T2}則Se?為e?對應(yīng)的基本割集.11實例例圖中紅邊為一棵生成樹,求對應(yīng)它的基本回路系統(tǒng)與基本割集系統(tǒng)解弦e,f,g對應(yīng)的基本回路分別為Ce=
8、ebc,Cf=fabc,Cg=gabcd,C基={Ce,Cf,Cg}.樹枝a,b,c,d對應(yīng)的基本割集分別為Sa={a,f,g},Sb={b,e,f,g},Sc={c,e,fg},Sd={d,g},S基={Sa,Sb,Sc,Sd}.12無向圖與最小生成樹對無向圖或有向圖的每一條邊e附加一個實數(shù)w(e),稱作邊e的權(quán).圖連同附加在邊上的權(quán)稱作帶權(quán)圖,記作G=.設(shè)G?是G的子圖,G?所有邊的權(quán)的和稱作G?的權(quán),記作W(G?).最小生成樹:帶權(quán)圖權(quán)最小的生成樹求最小生成樹的算法——避圈法(Kruska
9、l)設(shè)G=,將非環(huán)邊按權(quán)從小到大排序：e1,e2,…,em.(1)取e1在T中(2)檢查e2,若e2與e1不構(gòu)成回路,則將e2加入T中,否則棄去e2.(3)檢查e3,…,重復(fù)進行直至得到生成樹為止.13實例例求圖的一棵最小生成樹W(T)=38149.2根樹及其應(yīng)用有向樹根樹、樹根、樹葉、內(nèi)點、分支點家族樹、根子樹、有序樹r元樹（r元有序樹）r元正則樹（r元有序正則樹）r元完全正則樹（r
