圖論及其應(yīng)用char2-1-樹(shù)的概念與性質(zhì)

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1第二章第二章 樹(shù)樹(shù)本章主要內(nèi)容本章主要內(nèi)容一、樹(shù)的概念與性質(zhì)一、樹(shù)的概念與性質(zhì)二、生成樹(shù)二、生成樹(shù)三、最小生成樹(shù)三、最小生成樹(shù)授課學(xué)時(shí)授課學(xué)時(shí)授課學(xué)時(shí)：授課學(xué)時(shí)：6學(xué)時(shí)學(xué)時(shí) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2本次課主要內(nèi)容本次課主要內(nèi)容(一一)、樹(shù)的概念與應(yīng)用、樹(shù)的概念與應(yīng)用(二二)、樹(shù)的性質(zhì)、樹(shù)的性質(zhì) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n

2、 31、樹(shù)的概念、樹(shù)的概念(一一)、樹(shù)的概念與應(yīng)用、樹(shù)的概念與應(yīng)用定義定義1 不含圈的圖稱為無(wú)圈圖，樹(shù)是連通的無(wú)圈圖。不含圈的圖稱為無(wú)圈圖，樹(shù)是連通的無(wú)圈圖。例如：下面的圖均是樹(shù)例如：下面的圖均是樹(shù)樹(shù)樹(shù)T1樹(shù)樹(shù)T2樹(shù)樹(shù)T3樹(shù)樹(shù)T4 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4定義定義2 稱無(wú)圈圖稱無(wú)圈圖G為森林。為森林。注注: (1)樹(shù)與森林都是單圖樹(shù)與森林都是單圖;(2) 樹(shù)與森林都是偶圖。樹(shù)與森林都是偶圖。例例1 畫出所有不同構(gòu)的畫出所有不同構(gòu)的6階樹(shù)。階樹(shù)。解：按樹(shù)中存在的最長(zhǎng)路進(jìn)行枚舉。解：按樹(shù)中存在的最長(zhǎng)路進(jìn)行枚舉。6

3、階樹(shù)中能夠存在階樹(shù)中能夠存在的最長(zhǎng)路最小值為的最長(zhǎng)路最小值為2，最大值為，最大值為5。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 樹(shù)是圖論中應(yīng)用最為廣泛的一類圖。在理論上，由樹(shù)是圖論中應(yīng)用最為廣泛的一類圖。在理論上，由于樹(shù)的簡(jiǎn)單結(jié)構(gòu)，常常是圖論理論研究的于樹(shù)的簡(jiǎn)單結(jié)構(gòu)，常常是圖論理論研究的“試驗(yàn)田試驗(yàn)田”。在實(shí)際問(wèn)題中，許多實(shí)際問(wèn)題的圖論模型就是樹(shù)。在實(shí)際問(wèn)題中，許多實(shí)際問(wèn)題的圖論模型就是樹(shù)。例例2 族譜圖與樹(shù)族譜圖與樹(shù)2、樹(shù)的應(yīng)用、樹(shù)的應(yīng)用 要把一個(gè)家族的繁衍情況簡(jiǎn)潔直觀表達(dá)出來(lái)，用點(diǎn)要把一個(gè)家族的繁衍情況簡(jiǎn)潔直觀表達(dá)出來(lái)

4、，用點(diǎn)表示家族中成員，成員表示家族中成員，成員x是成員是成員y的兒女，把點(diǎn)的兒女，把點(diǎn)x畫在點(diǎn)畫在點(diǎn)y的下方，并連線。如此得到的圖，是一顆樹(shù)，稱為根的下方，并連線。如此得到的圖，是一顆樹(shù)，稱為根樹(shù)。示意如下：樹(shù)。示意如下：根樹(shù)根樹(shù) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 實(shí)際上，根樹(shù)是許多問(wèn)題的模型，如社會(huì)結(jié)構(gòu)，實(shí)際上，根樹(shù)是許多問(wèn)題的模型，如社會(huì)結(jié)構(gòu)，計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)，數(shù)學(xué)中的公式結(jié)構(gòu)，分類枚舉表計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)，數(shù)學(xué)中的公式結(jié)構(gòu)，分類枚舉表示等。示等。例例3 道路的鋪設(shè)與樹(shù)道路的鋪設(shè)與樹(shù) 假設(shè)要在某地建造假設(shè)要在某地建造4

5、個(gè)工廠，擬修筑道路連接這個(gè)工廠，擬修筑道路連接這4處。處。經(jīng)勘探，其道路可按下圖的無(wú)向邊鋪設(shè)?，F(xiàn)在每條邊的經(jīng)勘探，其道路可按下圖的無(wú)向邊鋪設(shè)?，F(xiàn)在每條邊的長(zhǎng)度已經(jīng)測(cè)出并標(biāo)記在圖的對(duì)應(yīng)邊上，如果我們要求鋪長(zhǎng)度已經(jīng)測(cè)出并標(biāo)記在圖的對(duì)應(yīng)邊上，如果我們要求鋪設(shè)的道路總長(zhǎng)度最短，這樣既能節(jié)省費(fèi)用設(shè)的道路總長(zhǎng)度最短，這樣既能節(jié)省費(fèi)用 ，又能縮短，又能縮短工期工期 ，如何鋪設(shè)？，如何鋪設(shè)？ v2 v3 v4 e2 e3 e4 v1 e1 e5 e6 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 該問(wèn)題歸結(jié)于在圖中求所謂的最小生成樹(shù)問(wèn)題?；蛟搯?wèn)

6、題歸結(jié)于在圖中求所謂的最小生成樹(shù)問(wèn)題?；蚍Q為賦權(quán)圖中的最小連接問(wèn)題。稱為賦權(quán)圖中的最小連接問(wèn)題。例例4 化學(xué)中的分子結(jié)構(gòu)與樹(shù)化學(xué)中的分子結(jié)構(gòu)與樹(shù)例如：例如：C4H10的兩種同分異構(gòu)結(jié)構(gòu)圖模型為：的兩種同分異構(gòu)結(jié)構(gòu)圖模型為：hhhhhhhhhhhhhhhhhhhh 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8例例5 電網(wǎng)絡(luò)中獨(dú)立回路與圖的生成樹(shù)電網(wǎng)絡(luò)中獨(dú)立回路與圖的生成樹(shù) 早在早在19世紀(jì)，圖論還沒(méi)有引起人們關(guān)注的時(shí)候，物理學(xué)世紀(jì)，圖論還沒(méi)有引起人們關(guān)注的時(shí)候，物理學(xué)家克希荷夫就已經(jīng)注意到電路中的獨(dú)立回路與該電路中的所家克希荷夫就

7、已經(jīng)注意到電路中的獨(dú)立回路與該電路中的所謂生成樹(shù)的關(guān)系。即：如果電路是謂生成樹(shù)的關(guān)系。即：如果電路是(n, m)圖，則獨(dú)立回路的圖，則獨(dú)立回路的個(gè)數(shù)為個(gè)數(shù)為m-n+1.并且，生成樹(shù)添上生成樹(shù)外的并且，生成樹(shù)添上生成樹(shù)外的G的一條邊，就的一條邊，就可以得到一獨(dú)立回路?？梢缘玫揭华?dú)立回路。例例6 通信網(wǎng)絡(luò)中的組播樹(shù)通信網(wǎng)絡(luò)中的組播樹(shù) 在單播模型中，數(shù)據(jù)包通過(guò)網(wǎng)絡(luò)沿著單一路徑從源主機(jī)向在單播模型中，數(shù)據(jù)包通過(guò)網(wǎng)絡(luò)沿著單一路徑從源主機(jī)向目標(biāo)主機(jī)傳遞，但在組播模型中，組播源向某一組地址傳遞數(shù)目標(biāo)主機(jī)傳遞，但在組播模型中，組播源向某一組地址傳遞數(shù)據(jù)包，而這一地址卻代表一個(gè)主機(jī)組。為了向所有接收者傳據(jù)包，而

8、這一地址卻代表一個(gè)主機(jī)組。為了向所有接收者傳遞數(shù)據(jù)，一般采用組播分布樹(shù)描述遞數(shù)據(jù)，一般采用組播分布樹(shù)描述IP組播在網(wǎng)絡(luò)里經(jīng)過(guò)的路組播在網(wǎng)絡(luò)里經(jīng)過(guò)的路徑。組播分布樹(shù)有四種基本類型：泛洪法、有源樹(shù)、有核樹(shù)徑。組播分布樹(shù)有四種基本類型：泛洪法、有源樹(shù)、有核樹(shù)和和Steiner樹(shù)樹(shù) 。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 總之，樹(shù)在圖論研究和圖論應(yīng)用上都是十分典型總之，樹(shù)在圖論研究和圖論應(yīng)用上都是十分典型的特殊圖。的特殊圖。定理定理1 每棵非平凡樹(shù)至少有兩片樹(shù)葉。每棵非平凡樹(shù)至少有兩片樹(shù)葉。證明證明 設(shè)設(shè)P=v1v2vk是非平

9、凡樹(shù)是非平凡樹(shù)T中一條最長(zhǎng)路，則中一條最長(zhǎng)路，則v1與與vk在在T中的鄰接點(diǎn)只能有一個(gè)，否則，要么推出中的鄰接點(diǎn)只能有一個(gè)，否則，要么推出P不是最長(zhǎng)路，要么推出不是最長(zhǎng)路，要么推出T中存在圈，這都是矛盾！中存在圈，這都是矛盾！即說(shuō)明即說(shuō)明v1與與v2是樹(shù)葉。是樹(shù)葉。定理定理2 圖圖G是樹(shù)當(dāng)且僅當(dāng)是樹(shù)當(dāng)且僅當(dāng)G中任意兩點(diǎn)都被唯一的路中任意兩點(diǎn)都被唯一的路連接。連接。證明：證明：“必要性必要性”若不然，設(shè)若不然，設(shè)P1與與P2是連接是連接u與與v的兩條不同的路。則的兩條不同的路。則(二二)、樹(shù)的性質(zhì)、樹(shù)的性質(zhì) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5

10、0 0.5 1 n 10由這兩條路的全部或部分將構(gòu)成一個(gè)圈，這與由這兩條路的全部或部分將構(gòu)成一個(gè)圈，這與G是是樹(shù)相矛盾。樹(shù)相矛盾?！俺浞中猿浞中浴笔紫?，因首先，因G的任意兩點(diǎn)均由唯一路相連，所以的任意兩點(diǎn)均由唯一路相連，所以G是連是連通的。通的。其次，若其次，若G中存在圈，則在圈中任取點(diǎn)中存在圈，則在圈中任取點(diǎn)u與與v，可得，可得到連接到連接u與與v的兩條不同的路，與條件矛盾。的兩條不同的路，與條件矛盾。定理定理3 設(shè)設(shè)T是是(n, m)樹(shù)，則：樹(shù)，則：1mn證明：對(duì)證明：對(duì)n作數(shù)學(xué)歸納。作數(shù)學(xué)歸納。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0

11、0.5 1 n 11當(dāng)當(dāng)n=1時(shí)，等式顯然成立；時(shí)，等式顯然成立；設(shè)設(shè)n=k時(shí)等式成立?？紤]時(shí)等式成立?？紤]n=k+1的樹(shù)的樹(shù)T。由定理由定理1 T中至少有兩片樹(shù)葉，設(shè)中至少有兩片樹(shù)葉，設(shè)u是是T中樹(shù)葉，考中樹(shù)葉，考慮慮T1=T-u,則則T1為為k階樹(shù)，于是階樹(shù)，于是m(T1)=k-1, 得得m(T)=k。這就證明了定理這就證明了定理3。例例7 設(shè)設(shè)T為為12條邊的樹(shù)，其頂點(diǎn)度為條邊的樹(shù)，其頂點(diǎn)度為1,2,5。如果。如果T恰有恰有3個(gè)度為個(gè)度為2的頂點(diǎn)，那么的頂點(diǎn)，那么T有多少片樹(shù)葉？有多少片樹(shù)葉？解：設(shè)解：設(shè)T有有x片樹(shù)葉。片樹(shù)葉。由由m=n-1得得n=13. 于是由握手定理得：于是由握手定

12、理得：1235(10)212xx 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12得得x=8例例8 設(shè)設(shè)T為為(n, m)樹(shù)，樹(shù)，T中有中有ni個(gè)度為個(gè)度為i的點(diǎn)的點(diǎn)(1ik),ik),且且有：有：n ni i=n.=n.證明：證明：13422(2)knnnkn證明：由證明：由m=n-1得：得：12()1kmnnn又由握手定理得：又由握手定理得：1222kmnnkn由上面兩等式得：由上面兩等式得：13422(2)knnnkn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n

13、 13推論推論1 具有具有k個(gè)分支的森林有個(gè)分支的森林有n-k條邊。條邊。證明：設(shè)森林證明：設(shè)森林G的的k個(gè)分支為個(gè)分支為Ti (1ik).ik).對(duì)每個(gè)分支，對(duì)每個(gè)分支，使用定理使用定理3 3得：得：()1,() )iiiim TnnV T所以：所以：1()()kiimGm Tnk定理定理4 每個(gè)每個(gè)n階連通圖的邊數(shù)至少為階連通圖的邊數(shù)至少為n-1.證明：如果證明：如果n階連通圖沒(méi)有一度頂點(diǎn)，那么由握手定理階連通圖沒(méi)有一度頂點(diǎn)，那么由握手定理有：有：()1()()2vVGmGdvn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1

14、4如果如果G有一度頂點(diǎn)。對(duì)頂點(diǎn)數(shù)作數(shù)學(xué)歸納。有一度頂點(diǎn)。對(duì)頂點(diǎn)數(shù)作數(shù)學(xué)歸納。當(dāng)當(dāng)n=1時(shí)，結(jié)論顯然時(shí)，結(jié)論顯然()1()()2vVGumGudvk設(shè)當(dāng)設(shè)當(dāng)n=k時(shí)，結(jié)論成立。時(shí)，結(jié)論成立。當(dāng)當(dāng)n=k+1時(shí)，設(shè)時(shí)，設(shè)u是是G的一度頂點(diǎn)，則的一度頂點(diǎn)，則G-u為具有為具有k個(gè)頂個(gè)頂點(diǎn)的連通圖。點(diǎn)的連通圖。若若G-u有一度頂點(diǎn)，則由歸納假設(shè)，其邊數(shù)至少有一度頂點(diǎn)，則由歸納假設(shè)，其邊數(shù)至少k-1,于于是是G的邊數(shù)至少有的邊數(shù)至少有k條；條；若若G-u沒(méi)有一度頂點(diǎn)，則由握手定理：沒(méi)有一度頂點(diǎn)，則由握手定理：所以所以G至少有至少有k+1條邊。條邊。 0.8 1 0.6 0.4 0.2 0 x t 0 0.

15、5 1 1.5 2 1 0.5 0 0.5 1 n 15而當(dāng)而當(dāng)G是樹(shù)時(shí)，邊數(shù)恰為是樹(shù)時(shí)，邊數(shù)恰為n-1.所以所以n階連通圖階連通圖G至少有至少有n-1條邊。條邊。所以，樹(shù)也被稱為最小連通圖。所以，樹(shù)也被稱為最小連通圖。定理定理5 任意樹(shù)任意樹(shù)T的兩個(gè)不鄰接頂點(diǎn)之間添加一條邊后，的兩個(gè)不鄰接頂點(diǎn)之間添加一條邊后，可以得到唯一圈?？梢缘玫轿ㄒ蝗?。證明：設(shè)證明：設(shè)u與與v是樹(shù)是樹(shù)T的任意兩個(gè)不鄰接頂點(diǎn)，由定理的任意兩個(gè)不鄰接頂點(diǎn)，由定理2知：有唯一路知：有唯一路P連接連接u與與v.于是于是Pu v是一個(gè)圈。是一個(gè)圈。顯然，由顯然，由P P的唯一性也就決定了的唯一性也就決定了Pu v的唯一性。的唯一

16、性。例例9 設(shè)設(shè)G是樹(shù)且是樹(shù)且k,k,則則G G至少有至少有k k個(gè)一度頂點(diǎn)。個(gè)一度頂點(diǎn)。證明：若不然，設(shè)證明：若不然，設(shè)G有有n個(gè)頂點(diǎn)，至多個(gè)頂點(diǎn)，至多k-1個(gè)一度頂點(diǎn)，個(gè)一度頂點(diǎn)，由于由于k，于是，由握手定理得：，于是，由握手定理得： 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16所以，有：所以，有：m (G)n-1,與與G是樹(shù)矛盾！是樹(shù)矛盾！()2 ( )( )12()2122v V Gm Gd vkknknn 例例10 設(shè)設(shè)G是森林且恰有是森林且恰有2k個(gè)奇數(shù)頂點(diǎn)，則在個(gè)奇數(shù)頂點(diǎn)，則在G中有中有k條條邊不重合的路邊不重合

17、的路P1, P2 , Pk,使得：使得：12( )()()()kE GE PE PE P證明：對(duì)證明：對(duì)k作數(shù)學(xué)歸納。作數(shù)學(xué)歸納。當(dāng)當(dāng)k=1時(shí)，時(shí)，G只有兩個(gè)奇數(shù)度頂點(diǎn)，此時(shí)，容易證明，只有兩個(gè)奇數(shù)度頂點(diǎn)，此時(shí)，容易證明，G是一條路；是一條路；設(shè)當(dāng)設(shè)當(dāng)k=t時(shí)，結(jié)論成立。令時(shí)，結(jié)論成立。令k=t+1 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17 在在G中一個(gè)分支中取兩個(gè)一度頂點(diǎn)中一個(gè)分支中取兩個(gè)一度頂點(diǎn)u與與v，令，令P是連接是連接該兩個(gè)頂點(diǎn)的唯一路，則該兩個(gè)頂點(diǎn)的唯一路，則G-P是有是有2t個(gè)奇數(shù)頂點(diǎn)的森林，個(gè)奇數(shù)頂點(diǎn)的森林

18、，由歸納假設(shè)，它可以分解為由歸納假設(shè)，它可以分解為t條邊不重合的路之并，所條邊不重合的路之并，所以以G可以分解為可以分解為t+1條邊不重合的路之并。條邊不重合的路之并。注：對(duì)圖作某種形式的分解，是圖論的一個(gè)研究對(duì)象，注：對(duì)圖作某種形式的分解，是圖論的一個(gè)研究對(duì)象，它在網(wǎng)絡(luò)結(jié)構(gòu)分析中具有重要作用。它在網(wǎng)絡(luò)結(jié)構(gòu)分析中具有重要作用。例例11 設(shè)設(shè)T是是k k階階樹(shù)。若圖樹(shù)。若圖G滿足滿足k-1,k-1,則則T T同構(gòu)于同構(gòu)于G G的的某個(gè)子圖。某個(gè)子圖。證明：對(duì)證明：對(duì)k作數(shù)學(xué)歸納。作數(shù)學(xué)歸納。當(dāng)當(dāng)k=1時(shí)，結(jié)論顯然。時(shí)，結(jié)論顯然。假設(shè)對(duì)假設(shè)對(duì)k-1(k3)3)的每顆樹(shù)的每顆樹(shù)T T1 1, ,以及

19、最小度至少為以及最小度至少為k-2k-2的每的每個(gè)圖個(gè)圖 H H，T T1 1同構(gòu)于同構(gòu)于H H的某個(gè)子圖的某個(gè)子圖F F?，F(xiàn)在設(shè)?，F(xiàn)在設(shè)T T是是k k階樹(shù)，且階樹(shù)，且 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 18 G滿足滿足(G)k-1(G)k-1的圖。我們證明的圖。我們證明T T同構(gòu)于同構(gòu)于G G的某個(gè)子圖。的某個(gè)子圖。設(shè)設(shè)u是是T的樹(shù)葉，的樹(shù)葉，v是是u的鄰接頂點(diǎn)。則的鄰接頂點(diǎn)。則T-u是是k-1階樹(shù)。階樹(shù)。 由于由于(G)k-1 k-2，由歸納假設(shè)，由歸納假設(shè)，T-u同構(gòu)于同構(gòu)于G的某個(gè)的某個(gè)子圖子圖F. 設(shè)設(shè)v1是與是與T中中v相對(duì)應(yīng)的相對(duì)應(yīng)的F中的點(diǎn)，由于中的點(diǎn)，由于dG(v1) k-1,所所以以v1在在G中一定有相異于中一定有相異于F中的鄰點(diǎn)中的鄰點(diǎn)w, 作作Fv1w,則該則該子圖和子圖和T同構(gòu)。同構(gòu)。v1wFG證明示意圖證明示意圖 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19樹(shù)的度序列問(wèn)題：樹(shù)的度序列問(wèn)題： 在第一章中，介紹了判定一個(gè)非增非負(fù)序列是否為簡(jiǎn)單在第一章中，介紹了判定一個(gè)非增非負(fù)序列是否為簡(jiǎn)單圖的度序列定理。下面介紹一個(gè)判定非增非負(fù)序列是否為圖的度序列定理。下面介紹一個(gè)判定非增非負(fù)序列是否為