資源描述：
《《無向樹和生成樹》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第七章1.無向樹和生成樹2.根樹樹連通而不含回路的無向圖稱為無向樹,簡(jiǎn)稱樹,常用T表示樹.連通分支數(shù)大于等于2,且每個(gè)連通分支均是樹的非連通無向圖稱為森林.平凡圖稱為平凡樹.樹葉設(shè)T＝為一棵無向樹,v∈V,若d(v)＝1,則稱v為T的樹葉.若d(v)≥2,則稱v為T的分支點(diǎn).設(shè)G＝,則下面各命題是等價(jià)的:(1)G連通而不含回路;(2)G的每對(duì)頂點(diǎn)之間具有唯一的一條路徑;(3)G是連通的且n＝m+1;(4)G中無回路且n＝m+1;定理1(5)G中無回路,但在G中任兩個(gè)不相鄰的頂點(diǎn)之間增加一條邊,就形成唯一的一條初級(jí)回路;(6)G
2、是連通的且G中每條邊都是橋;(7)G是連通的,但刪除任何一條邊后,就不連通了.其中n為G中頂點(diǎn)數(shù),m為邊數(shù).定理2設(shè)T＝是n階非平凡的樹,則T中至少有2片樹葉.證明因?yàn)門是非平凡樹,所以T中每個(gè)頂點(diǎn)的度數(shù)都大于等于1,設(shè)有k片樹葉,則有(n-k)個(gè)頂點(diǎn)度數(shù)大于等于2,由握手定理可知由定理1可知m＝n-1,將此結(jié)果代入上式經(jīng)過整理得k≥2,這說明T至少有2片樹葉.生成樹設(shè)G＝是無向連通圖,T是G的生成子圖,并且T是樹,則稱T是G的生成樹.G在T中的邊稱為T的樹枝,G不在T中的邊稱為T的弦.T的所有弦的集合的導(dǎo)出子圖稱為T的余樹.
3、(2)為(1)的一棵生成樹T,(3)為T的余樹,注意余樹不一定是樹.定理任何連通圖G至少存在一棵生成樹.推論1設(shè)n階無向連通圖G有m條邊,則m≥n-1.推論2設(shè)n階無向連通圖G有m條邊,T是G的生成樹,T'是T的余樹,則T'中有m-n+1條邊.圖2基本回路在圖2中,實(shí)邊所示的子圖是圖G的一棵生成樹T,d,e,f為T的樹枝,a,b,c為T的弦.在T上加弦a,產(chǎn)生G的一個(gè)初級(jí)回路aed.在T上加弦b,產(chǎn)生G的一個(gè)初級(jí)回路bdf.在T上加弦c,產(chǎn)生G的一個(gè)初級(jí)回路cef.這3個(gè)回路中每一個(gè)回路都只含一條弦,其余的邊都是樹枝,這樣的回路稱為基本回路.基本
4、回路系統(tǒng)定義設(shè)T是n階連通圖G=的一棵生成樹,G有n條邊.設(shè)e1,e2···,em-n+1為T的弦,設(shè)Cr是T加弦er產(chǎn)生的G的回路,r=1,2,…m-n+1.稱Cr為對(duì)應(yīng)于弦er的基本回路,稱{C1,C2,···,Cm-n+1}為對(duì)應(yīng)生成樹T的基本回路系統(tǒng).基本割集系統(tǒng)定義設(shè)T是n階連通圖G=的一棵生成樹,稱T的n-1個(gè)樹枝對(duì)應(yīng)的G的n-1個(gè)割集(每個(gè)割集只含一個(gè)樹枝,其余的邊都是弦)S1,S2,···,Sn-1為對(duì)應(yīng)生成樹T的G的基本割集,稱{S1,S2,···,Sn-1}為對(duì)應(yīng)生成樹T的基本割集系統(tǒng).對(duì)一個(gè)n階連通圖G來
5、說,對(duì)應(yīng)不同的生成樹的基本割集可能不一樣,但基本割集的個(gè)數(shù)必為n-1個(gè),這也是G的固有特性.例1圖G中,實(shí)線邊所構(gòu)成的子圖是G的一棵生成樹T,求T對(duì)應(yīng)的基本回路和基本回路系統(tǒng),基本割集和基本割集系統(tǒng).解:G中頂點(diǎn)數(shù)n=6,邊數(shù)m=9,基本回路個(gè)數(shù)為m-n+1=4,即T有4條弦f,g,h,i.對(duì)應(yīng)的基本回路:Cf=facd;Cg=gba;Ch=hdcb;Ci=ied.基本回路系統(tǒng)為{Cf,Cg,Ch,Ci}T有5個(gè)樹枝a,b,c,d,e,因而有5個(gè)基本割集:Sa={a,g,f};Sb={b,g,h};Sc={c,f,h};Sd={d,i,h};Se
6、={e,f,i};基本割集系統(tǒng)為{Sa,Sb,Sc,Sd,Se}.定義設(shè)無向連通帶權(quán)圖G=,T是G的一棵生成樹.T各邊帶權(quán)之和稱為T的權(quán),記作W(T).G的所有生成樹中帶權(quán)最小的生成樹稱為最小生成樹.Kruskal算法設(shè)n階無向連通帶權(quán)圖G=中有m條邊e1,e2···,em,它們帶的權(quán)分別為a1,a2,…am,不妨設(shè)a1≤a2≤…≤am.(1)取e1在T中(e1非環(huán),若e2為環(huán),則棄e1);(2)若e2不與e1構(gòu)成回路,取e2在T中,否則棄e2,再查e3,繼續(xù)這一過程,直到形成生成樹T為止.用以上算法生成的T是最小生成
7、樹.實(shí)邊所示的生成樹均由避圈法得到的最小生成樹.圖(1)中,W(T)=15,圖(2)中,W(T)=23.
