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

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

1、樹LuChaojun,SJTU1注意?主要參考曹老師書：P302-310?部分參考清華教材?作業(yè)中紅色標(biāo)記為選做樹結(jié)構(gòu)簡介?樹(tree)是用來表示層次結(jié)構(gòu)的圖.–稱為樹是因?yàn)檫@種圖可以畫成樹狀:常倒過來畫(即樹根在上,樹葉在下).?樹結(jié)構(gòu)的例子:–化學(xué):Cayley最早(1857年)用樹來研究化合物結(jié)構(gòu).–計(jì)算機(jī)科學(xué)技術(shù):二叉查找樹,B樹,R樹,…–信息管理:目錄系統(tǒng)–管理:層次式組織機(jī)構(gòu)–生物學(xué):進(jìn)化樹–商務(wù):傳銷(金字塔銷售模式)LuChaojun,SJTU3樹的定義?定義:無圈（回路）連通無向圖稱為無向樹,簡稱樹.–樹中最長路的長度稱為樹的高度;–邊也稱為樹枝;–度為1的頂

2、點(diǎn)稱為樹葉,即懸點(diǎn);?平凡圖（只有一個(gè)頂點(diǎn)的圖）是樹,稱為平凡樹.?樹必不含重邊和環(huán),故是簡單圖.?定義:無圈（回路）無向圖稱為森林.–森林可能不是連通的.–森林的每個(gè)連通支都是樹.樹的等價(jià)定義?定理:設(shè)G是頂點(diǎn)數(shù)n?2的圖,則下列性質(zhì)互相等價(jià):(1)G是樹(即連通且無圈);滿足連通,無圈,有n?1條(2)G連通且有n?1條邊;邊之任意兩個(gè)就是樹(3)G有n?1條邊且無圈;(4)G連通且每條邊都是割邊;樹是邊數(shù)最少的連(5)G無圈,但任意增加一邊通圖;也是邊數(shù)最多的無圈圖.后恰有一個(gè)圈;(6)T的任意兩頂點(diǎn)間有唯一通道.樹的其他性質(zhì)?設(shè)樹T的頂點(diǎn)數(shù)n?2,則T中必有樹葉.證法1:若

3、各頂點(diǎn)度都?2,則總度數(shù)?2n?2m?2(n?1).證法2:考慮從任一頂點(diǎn)v出發(fā)沿邊前進(jìn),走過的邊不重復(fù),則必止步于某樹葉.?設(shè)樹T的頂點(diǎn)數(shù)n?2,則T至少有兩個(gè)樹葉.證明:同上面證法2,考慮從一樹葉出發(fā)前進(jìn),必止步于另一個(gè)樹葉.?若森林F有n個(gè)結(jié)點(diǎn)和k個(gè)連通支,則F有n?k條邊.生成樹?定義:如果T是圖G的生成子圖,而且是樹,則稱T是G的生成樹(或支撐樹).?圖G有生成樹iffG是連通的.?:顯然?:不斷對G破除圈即可得到生成樹.?若圖G本身不是樹,則其生成樹不唯一.LuChaojun,SJTU7一個(gè)連通圖的生成樹可能不唯一。因?yàn)樵谌《ㄒ粋€(gè)回路后，就可以從中去掉任一條邊，去掉的邊

4、不一樣，故可能得到不同的生成樹。ccc67677b5d5bdbd3143141a2eeaae)(a))(c(b在上圖(a)中，刪去邊2,3,5，就得到生成樹(b)，若刪去邊2，4，6,可得到生成樹(c)。余樹?定義:設(shè)T是G的生成樹,則從E(G)刪去E(T)中的邊及,所構(gòu)成的G的子圖稱為T的余樹T.–注意:余樹不一定連通，也不一定無回路，=>余樹本身不一定是樹,更不一定是生成樹。?定理:設(shè)G是連通圖,T是G的生成樹.(1)則T有m?n?1條邊.(2)若C是G中圈,則E(T)?E(C)??.dadaadfefefebbcbcc(a)(b)(c)(a)G(b)生成樹(c)余樹構(gòu)造生成樹

5、?破圈法?廣度優(yōu)先搜索(BFS)–從頂點(diǎn)s出發(fā),標(biāo)記其鄰點(diǎn)為1(s);?u上標(biāo)記k(v)的含義:u與s距離是k,u到s的最短路上的上一個(gè)頂點(diǎn)是v–從對每個(gè)標(biāo)記為k(v)的頂點(diǎn)u,若其鄰點(diǎn)未標(biāo)記,則標(biāo)記為k+1(u);–直至沒有與已標(biāo)記頂點(diǎn)相鄰的未標(biāo)記頂點(diǎn).–若頂點(diǎn)v標(biāo)記k(u),則取邊uv,所有這種邊的集合即構(gòu)成生成樹.–結(jié)果不唯一?深度優(yōu)先搜索(DFS)最小生成樹?最小生成樹問題:設(shè)G是帶權(quán)連通圖,求G的總權(quán)值最小的生成樹.?應(yīng)用例:在若干加油站之間鋪設(shè)輸油管道,在確保各加油站供應(yīng)的條件下,要使建設(shè)費(fèi)用最小.Kruskal算法?算法思想:不斷加入權(quán)值最小的邊,并保持無圈.?Kru

6、skal算法的描述如下（曹老師書上為等價(jià)描述）:T←Φ。當(dāng)

7、T

8、

9、T

10、

11、'?T.由算法的k挑選規(guī)則可推知:以e換e'所得T''也是生成樹(因k為連通且有n?1條邊),且其權(quán)值不會(huì)比T'大,故也是最小生成樹.但T''與T有更多公共e,...,e,矛盾.1k故必有k?n,即T?T'.Prim算法?算法思想:初始U為任一頂點(diǎn),然后不斷向U中加入距離U最近的頂點(diǎn).(1)T??;U?{u};(2)從V(G)?U中選擇與U中頂點(diǎn)相鄰且邊權(quán)值最小的頂點(diǎn)v:將v加入U(xiǎn),該邊加入T;(3)重復(fù)執(zhí)行(2),直至U?V.Prim算法實(shí)例UU1115561566