離散數(shù)學(xué)圖論-樹(shù)x

《離散數(shù)學(xué)圖論-樹(shù)x》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第16章樹(shù)第十六章樹(shù)一、無(wú)向樹(shù)1）定義：連通無(wú)回路（初級(jí)回路或簡(jiǎn)單回路）的無(wú)向圖稱(chēng)為無(wú)向樹(shù)，或簡(jiǎn)稱(chēng)樹(shù)常用T表示樹(shù)，平凡圖稱(chēng)為平凡樹(shù)．若無(wú)向圖G至少有兩個(gè)連通分支，則稱(chēng)G為森林．在無(wú)向樹(shù)中，懸掛頂點(diǎn)稱(chēng)為樹(shù)葉，度數(shù)大于或等于2的頂點(diǎn)稱(chēng)為分支結(jié)點(diǎn)．2）樹(shù)的等價(jià)定義設(shè)G＝是n階m條邊的無(wú)向圖，則下面各命題是等價(jià)的：(1)G是連通無(wú)回路（樹(shù)）．可通過(guò)循環(huán)證明(2)G中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑．（連通則存在路徑，若不唯一，不同路徑則構(gòu)成回路）(3)G中無(wú)回路且m=n-1．有長(zhǎng)大于等于2的回路都與唯一路徑

2、矛盾。對(duì)結(jié)點(diǎn)進(jìn)行歸納：n=1平凡圖m=0=n-1；設(shè)n=k成立；n=k+1時(shí)兩個(gè)結(jié)點(diǎn)有唯一的路，去掉則為兩個(gè)連通分支（各自滿(mǎn)足假設(shè)）m=m1+m2+1=n1-1+n2-1+1=n1+n2-1=n-1(4)G是連通的且m=n-1．若不連通，對(duì)各個(gè)(s>=2)連通分支是樹(shù)且有mi=ni-1m=n-ss>=2矛盾(5)G中沒(méi)有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到惟一的一個(gè)含新邊的初級(jí)回路．(6)G是連通的，但刪去任何一條邊后，所得圖不連通．G連通：若存在二個(gè)結(jié)點(diǎn)無(wú)通路，則在二個(gè)結(jié)點(diǎn)添加邊后不

3、會(huì)出現(xiàn)回路3）樹(shù)的性質(zhì)對(duì)于給定的無(wú)向圖—樹(shù)是邊數(shù)最小的連通圖（mn-1則有回路）結(jié)點(diǎn)的度：Σd(vi)=2m=2(n-1)定理：設(shè)T是n階非平凡的無(wú)向樹(shù)，則T中至少有片樹(shù)葉設(shè)：有x片樹(shù)葉，其余結(jié)點(diǎn)度數(shù)至少為2x+2(n-x)<=2(n-1)例：無(wú)向樹(shù)T中度為4、3、2的結(jié)點(diǎn)各一個(gè)，其余為樹(shù)葉，樹(shù)葉＝？4+3+2+k=2(3+k-1)4)階數(shù)n比較小的所有非同構(gòu)的無(wú)向樹(shù)．例1：畫(huà)出6階所有非同構(gòu)的無(wú)向樹(shù)．m=n-1=5從樹(shù)的節(jié)點(diǎn)之和來(lái)分析：結(jié)點(diǎn)之和為10分配給6個(gè)

4、結(jié)點(diǎn)111115111124111133111223112222例2：7階無(wú)向樹(shù)中有3片樹(shù)葉和1個(gè)3度頂點(diǎn)，其余3個(gè)頂點(diǎn)的度數(shù)均無(wú)1和3．試畫(huà)出滿(mǎn)足要求的所有非同構(gòu)的無(wú)向樹(shù)．解答：從樹(shù)的節(jié)點(diǎn)之和來(lái)分析：7階無(wú)向樹(shù)的邊數(shù)m=（），于是∑d(vi)＝12＝3＋3+d(v5)+d(v6)+d(v7)1112223加入2，2，2如何組成結(jié)點(diǎn)的度數(shù)序列使之不同構(gòu)主要分析：度為3的結(jié)點(diǎn)v與其三個(gè)鄰接點(diǎn)的關(guān)系鄰接關(guān)系不同就能得到不同構(gòu)的樹(shù)三個(gè)鄰接點(diǎn)度數(shù)：112122222§16.2生成樹(shù)（一些連通圖不是樹(shù)，但它的子圖是樹(shù)

5、——重要的是生成樹(shù)）1、定義：設(shè)T是無(wú)向圖G的子圖并且為樹(shù)，則稱(chēng)T為G的樹(shù)．若T是G的樹(shù)且為生成子圖，則稱(chēng)T是G的生成樹(shù)．設(shè)T是G的生成樹(shù)，?e∈E(G)，若e∈E(T)，則稱(chēng)e為T(mén)的樹(shù)枝，否則稱(chēng)e為T(mén)的弦．并稱(chēng)導(dǎo)出子圖G[E(G)—E(T)]為T(mén)的余樹(shù)，記作．注：不一定連通，也不一定不含回路.(無(wú)規(guī)律)2、生成樹(shù)的性質(zhì)1）定理：無(wú)向圖G具有生成樹(shù)當(dāng)且僅當(dāng)G是連通圖（破圈法-不斷去掉回路）2）設(shè)G為n階m條邊的無(wú)向連通圖，則m=

6、E(G)

7、≥

8、E(T)

9、=n-1．3）設(shè)G是n階m條邊的無(wú)向連通圖，T為G的生

10、成樹(shù)，則T的余樹(shù)中含m–n+1條邊(即T有m-n+1條弦)4）任何無(wú)向連通圖G，都存在生成樹(shù)無(wú)向連通圖G的生成樹(shù)是不唯一的實(shí)邊圖為該圖的一棵生成樹(shù)T，余樹(shù)為虛邊所示，它不連通，同時(shí)也含回路3、生成樹(shù)的應(yīng)用要建6個(gè)工廠，修建連接的通路（見(jiàn)圖），為使5處都有路相通，至少要建幾條路？如何鋪設(shè)？由于n=6所以建5條路即可4、無(wú)向圖G的生成樹(shù)的確定：二種方法：1、破圈法：每次去掉回路中的一條邊，去掉總數(shù)為m-n+1條弦2、避圈法：由一個(gè)結(jié)點(diǎn)開(kāi)始選一條邊，逐漸添加與邊關(guān)聯(lián)的結(jié)點(diǎn)（只要不構(gòu)成回路即可）直到所有結(jié)點(diǎn)被添加，

11、(挑選n-1條邊）3、帶權(quán)圖的最小生成樹(shù)(1)定義5設(shè)無(wú)向連通帶權(quán)圖G＝，T是G的一棵生成樹(shù)．T的各邊權(quán)之和稱(chēng)為T(mén)的權(quán)，記作W(T)；G的所有生成樹(shù)中權(quán)最小的生成樹(shù)稱(chēng)為G的最小生成樹(shù)。(2)最小生成樹(shù)的求法（這里介紹避圈法Kruskal算法)設(shè)n階無(wú)向連通帶權(quán)圈G＝有m條邊，不妨設(shè)G中沒(méi)有環(huán)(否則，可以將所有的環(huán)先刪去)，將m條邊按權(quán)從小到大順序排列，設(shè)為e1,e2，…,em；取e1在T中，然后依次檢查e2，e3，…，em.若ej(j≥2)與已在T中的邊不能構(gòu)成回路，則取ej在T

12、中，否則棄去ej；算法停止時(shí)得到的T為G的最小生成樹(shù)。避圈法Kruskal算法(n-1次)1121241245(1)(2)(3)(4)破圈法(1)512436(3)1245(2)12435作業(yè)：P319習(xí)題十六1、2、3、4、5、13§16.3根樹(shù)及其應(yīng)用有向樹(shù)：設(shè)D是有向圖，若D的基圖是無(wú)向樹(shù)，則稱(chēng)D為有向樹(shù).有向樹(shù)中,根樹(shù)最重要,故只討論根樹(shù).一、根樹(shù)1、定義：設(shè)T是n(n≥2)階有向樹(shù),若T中有一個(gè)頂點(diǎn)的入