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

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

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

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

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

4、結(jié)點(diǎn)111115111124111133111223112222例2：7階無向樹中有3片樹葉和1個(gè)3度頂點(diǎn)，其余3個(gè)頂點(diǎn)的度數(shù)均無1和3．試畫出滿足要求的所有非同構(gòu)的無向樹．解答：從樹的節(jié)點(diǎn)之和來分析：7階無向樹的邊數(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)的樹三個(gè)鄰接點(diǎn)度數(shù)：112122222§16.2生成樹（一些連通圖不是樹，但它的子圖是樹

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

6、E(G)

7、≥

8、E(T)

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

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

11、(挑選n-1條邊）3、帶權(quán)圖的最小生成樹(1)定義5設(shè)無向連通帶權(quán)圖G＝，T是G的一棵生成樹．T的各邊權(quán)之和稱為T的權(quán)，記作W(T)；G的所有生成樹中權(quán)最小的生成樹稱為G的最小生成樹。(2)最小生成樹的求法（這里介紹避圈法Kruskal算法)設(shè)n階無向連通帶權(quán)圈G＝有m條邊，不妨設(shè)G中沒有環(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的最小生成樹。避圈法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根樹及其應(yīng)用有向樹：設(shè)D是有向圖，若D的基圖是無向樹，則稱D為有向樹.有向樹中,根樹最重要,故只討論根樹.一、根樹1、定義：設(shè)T是n(n≥2)階有向樹,若T中有一個(gè)頂點(diǎn)的入