資源描述：
《離散數(shù)學(xué)樹解讀課件.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第7章樹7.1無向樹及生成樹7.2根樹及其應(yīng)用17.1無向樹及生成樹無向樹與森林生成樹與余樹基本回路與基本回路系統(tǒng)基本割集與基本割集系統(tǒng)最小生成樹與避圈法2無向樹無向樹:無回路的連通無向圖平凡樹:平凡圖森林:每個連通分支都是樹的非連通的無向圖樹葉:樹中度數(shù)為1的頂點(diǎn)分支點(diǎn):樹中度數(shù)?2的頂點(diǎn)右圖為一棵12階樹.注:本章中所討論的回路均指簡單回路或初級回路3樹的應(yīng)用英國數(shù)學(xué)家凱萊(ArthurCayley)于19世紀(jì)中葉研究飽和碳?xì)浠衔顲nH2n+2的同分異構(gòu)體時提出樹的概念.當(dāng)n=1,2,3時,都只有一棵非同構(gòu)的樹;當(dāng)n=4時,有
2、2棵不同構(gòu)的樹.甲烷乙烷丙烷丁烷異丁烷4無向樹的性質(zhì)定理設(shè)G=是n階m條邊的無向圖,則下面各命題是等價(jià)的：(1)G是樹(連通無回路);(2)G中任意兩個頂點(diǎn)之間存在惟一的路徑;(3)G中無回路且m=n?1;(4)G是連通的且m=n?1;(5)G是連通的且G中任何邊均為橋;(6)G中沒有回路,但在任何兩個不同的頂點(diǎn)之間加一條新邊后所得圖中有惟一的一個含新邊的圈.5無向樹的性質(zhì)(續(xù))定理設(shè)T是n階非平凡的無向樹，則T中至少有兩片樹葉.證設(shè)T有x片樹葉,由握手定理及前面的定理，2(n-1)?x+2(n-x)解得x?2.6例題例1
3、已知無向樹T中,有1個3度頂點(diǎn),2個2度頂點(diǎn),其余頂點(diǎn)全是樹葉.試求樹葉數(shù),并畫出滿足要求的非同構(gòu)的無向樹.解用樹的性質(zhì)m=n?1和握手定理.設(shè)有x片樹葉，于是n=1+2+x=3+x,2m=2?(2+x)=1?3+2?2+x解得x=3，故T有3片樹葉.T的度數(shù)列為1,1,1,2,2,3有2棵非同構(gòu)的無向樹.7例題例2已知無向樹T有5片樹葉,2度與3度頂點(diǎn)各1個,其余頂點(diǎn)的度數(shù)均為4.求T的階數(shù)n,并畫出滿足要求的所有非同構(gòu)的無向樹.解設(shè)T的階數(shù)為n,則邊數(shù)為n?1,4度頂點(diǎn)的個數(shù)為n?7.由握手定理得2m=2(n?1)=5?1+2?
4、1+3?1+4(n?7)解得n=8,4度頂點(diǎn)為1個.T的度數(shù)列為1,1,1,1,1,2,3,4有3棵非同構(gòu)的無向樹8生成樹設(shè)G為無向連通圖G的生成樹:G的生成子圖并且是樹生成樹T的樹枝:G在T中的邊生成樹T的弦:G不在T中的邊生成樹T的余樹:所有弦的集合的導(dǎo)出子圖注意：不一定連通,也不一定不含回路.黑邊構(gòu)成生成樹紅邊構(gòu)成余樹9生成樹的存在性定理任何無向連通圖都有生成樹.證用破圈法.若圖中無圈,則圖本身就是自己的生成樹.否則刪去圈上的任一條邊,這不破壞連通性,重復(fù)進(jìn)行直到無圈為止,剩下的圖是一棵生成樹.推論設(shè)n階無向連通圖有m條邊,則
5、m?n?1.10基本回路與基本回路系統(tǒng)定義設(shè)T是連通圖G的一棵生成樹,對每一條弦e,存在惟一的由弦e和T的樹枝構(gòu)成的初級回路Ce,稱Ce為對應(yīng)于弦e的基本回路.稱所有基本回路的集合為對應(yīng)生成樹T的基本回路系統(tǒng).求基本回路的算法:設(shè)弦e=(u,v),先求T中u到v的路徑?uv,再加上弦e.例如Ce=ebc,Cf=fabc,Cg=gabcd,C基={Ce,Cf,Cg}.11基本割集與基本割集系統(tǒng)定義設(shè)T是連通圖G的一棵生成樹,對T的每一條樹枝a,存在惟一的由樹枝a,其余的邊都是弦的割集Sa,稱Sa為對應(yīng)樹枝a的基本割集，稱所有基本割集的
6、集合為對應(yīng)生成樹T的基本割集系統(tǒng).求基本割集的算法:設(shè)a為生成樹T的樹枝,T?a由兩棵子樹T1與T2組成,則Sa={e
7、e?E(G)且e的兩個端點(diǎn)分別屬于T1與T2}.例如Sa={a,f,g},Sb={b,e,f,g},Sc={c,e,fg},Sd={d,g},S基={Sa,Sb,Sc,Sd}.12回路合并合并回路C1和C2(C1?C2):C1?C2是C1和C2上的邊的對稱差構(gòu)成的(一條或幾條)回路.???13基本回路的性質(zhì)連通圖中的任一條回路都可以表成對應(yīng)它所含弦的基本回路的合并.例如,abcf=Cfaef=Ce?Cfaedg=C
8、e?Cgbcdgfe=Ce?Cf?Cg14基本割集的性質(zhì)連通圖中的任一割集都可以表成對應(yīng)它所含樹枝的基本割集的對稱差.例如{g,d}=Sd{a,b,e}=Sa?Sb{a,e,c}=Sa?Sc{b,e,f,d}=Sb?Sd15無向圖與最小生成樹對無向圖或有向圖的每一條邊e附加一個實(shí)數(shù)w(e),稱作邊e的權(quán).圖連同附加在邊上的權(quán)稱作帶權(quán)圖,記作G=.設(shè)T是G的生成樹,T所有邊的權(quán)的和稱作T的權(quán),記作W(T).最小生成樹:帶權(quán)圖權(quán)最小的生成樹避圈法(Kruskal)——求最小生成樹的算法設(shè)G是n階無向連通帶權(quán)圖G.(1)按權(quán)
9、從小到大排列邊(環(huán)除外),設(shè)W(e1)≤W(e2)≤…≤W(em).(2)令T??,i?1,k?0.(3)若ei與T中的邊不構(gòu)成回路，則令T?T?{ei},k?k+1.(4)若k
