圖論 第二章 樹(shù)

1/111圖論及其應(yīng)用公共郵箱：graphtheory2015@163.com密碼：graphtheory2/39第二章樹(shù)定義1

(1)

無(wú)圈連通圖稱為樹(shù),樹(shù)常用字母T表示；(2)

樹(shù)中，度數(shù)為1的頂點(diǎn)稱為樹(shù)葉，度數(shù)大于1的頂點(diǎn)稱為分支點(diǎn)；(3)

無(wú)圈圖稱為森林，樹(shù)也是森林；§2.1樹(shù)的概念與性質(zhì)由定義,平凡圖也是樹(shù),稱為平凡樹(shù)。3/39樹(shù)樹(shù)不是樹(shù)不是樹(shù)，是森林例平凡樹(shù)●4/39圖的操作定義設(shè)圖G=

<V,E>。設(shè)e∈E，用G-e表示從G中去掉邊e得到的圖，稱為刪除邊e。又設(shè)EE，用G-E表示從G中刪除E中所有邊得到的圖，稱為刪除E。設(shè)v∈V，用G-v表示從G中去掉結(jié)點(diǎn)v及v關(guān)聯(lián)的所有邊得到的圖，稱為刪除結(jié)點(diǎn)v。又設(shè)VV，用G-V

表示從G中刪除V中所有結(jié)點(diǎn)及關(guān)聯(lián)的所有邊得到的圖，稱為刪除V。設(shè)e=(u,v)∈E，用G●e表示從G中刪除e，將e的兩個(gè)端點(diǎn)u,v用一個(gè)新的結(jié)點(diǎn)w代替，使w關(guān)聯(lián)除e外的u和v關(guān)聯(lián)的一切邊，稱為邊e的收縮。一個(gè)圖G可以收縮為圖H，是指H可以從G經(jīng)過(guò)若干次邊的收縮而得到。設(shè)u,v∈V(u,v可能相鄰，也可能不相鄰)，用G∪(u,v)表示在u,v之間加一條邊(u,v)，稱為加新邊，

也可記為G+uv。5/39定理1

設(shè)G是具有n個(gè)點(diǎn)m條邊的圖，則以下關(guān)于樹(shù)的命題等價(jià)。（1）G是樹(shù)。（2）G中任意兩個(gè)不同點(diǎn)之間存在唯一的路。（3）G連通，刪去任一邊便不連通。（4）G連通，且n=m+1。（5）G無(wú)圈，且n=m+1。（6）G無(wú)圈，添加任一條邊可得唯一的圈。6/39（2）G中任意兩個(gè)不同點(diǎn)之間存在唯一的路”證

“（1）G是樹(shù)

因G是樹(shù)，樹(shù)是連通的，故G中任意兩個(gè)不同點(diǎn)之間存在路。下證唯一性。

若不然，設(shè)點(diǎn)u與v之間存在兩條不同的路Γ1與Γ2。從u出發(fā)沿Γ1搜索，設(shè)x是具有第一個(gè)如下性質(zhì)的點(diǎn)：它在Γ2上，但它的下一個(gè)點(diǎn)w不在Γ2上；繼續(xù)搜索，設(shè)y是w之后的第一個(gè)既在Γ1上又在Γ2上的點(diǎn)。這樣Γ1上從x到y(tǒng)段與Γ2上從y到x段便構(gòu)成一個(gè)圈，這與G是樹(shù)無(wú)圈矛盾，所以任意兩點(diǎn)間的路唯一。wvuyΓ1Γ27/39(2)G中任意兩個(gè)不同點(diǎn)之間存在唯一的路（3）G連通，刪去任一邊便不連通。vu（4）G連通，且n=

m+1(3)G連通，刪去任一邊便不連通只需證

n=m+1即可。對(duì)n用歸納法。當(dāng)n=

1時(shí)，G無(wú)邊，滿足n=m+1。設(shè)對(duì)少于n個(gè)點(diǎn)的圖（4）的結(jié)論成立。下證對(duì)n個(gè)點(diǎn)成立vuG1G2G-uv8/39

對(duì)于有n個(gè)點(diǎn)的圖G，由（3）的假設(shè)知?jiǎng)h去G中某邊可得兩個(gè)具有同樣性質(zhì)的子圖G1與G2。設(shè)Gi的點(diǎn)數(shù)與邊數(shù)分別為ni與mi（i=1,2）。顯然n1<n，n2<n。由歸納假設(shè)有

相加得

n1+n2=m1+m2+2（*）n1=m1+1，n2=m2+1同時(shí)有

n1+n2=n，m1+m2=m-1代入（*）式得：n=m+1。9/39（4）G連通，且n=m+1。（5）G無(wú)圈，且n=m+1。證明：假設(shè)G

中存在一個(gè)圈，則去掉圈中的一條邊會(huì)去掉這個(gè)圈，而不改變頂點(diǎn)個(gè)數(shù)和圖的連通性。重復(fù)這個(gè)過(guò)程，將圖中的所有圈去掉，則得到一顆樹(shù)，因此

n<m+1，矛盾。（5）G無(wú)圈，且n=m+1。（6）G無(wú)圈，添加任一條邊可得唯一的圈。證明：首先證明G連通。假設(shè)G可分為k個(gè)連通分支，則每個(gè)連通分支均無(wú)圈，即為樹(shù)。設(shè)這k棵樹(shù)分別為G1，G2，…,Gk，且Gi頂點(diǎn)數(shù)與邊數(shù)分別是ni和mi(i=1,2,…,k)，因此

mi

=ni-1,i=1,2,…,k得：10/39所以k=1,即G連通。根據(jù)前面證明可知（2）成立，即任何兩個(gè)頂點(diǎn)之間都存在一條唯一的路。考慮任意兩個(gè)頂點(diǎn)u與v，設(shè)G中有一條連接u，

v的路P。添加邊uv后得到圖G+uv。則在G+uv中存在P和uv構(gòu)成的一個(gè)圈C。下證此圈是G+uv唯一的圈。若不然，則G+uv存在另一個(gè)圈C’，且C’與C都是圖G添加邊uv后產(chǎn)生的，即這兩個(gè)不同圈都含有uv邊。因而在原圖中有兩條不同的連接u

與v

的路，矛盾。vuG+uvC’11/39（6）G無(wú)圈，添加任一條邊可得唯一的圈。（1）G是樹(shù)需證明G連通。假設(shè)不連通，則存在兩個(gè)頂點(diǎn)u與v之間不存在通路，因此增加uv邊不會(huì)在G+uv產(chǎn)生圈，矛盾！命題得證12/39推論1由k棵樹(shù)組成的森林滿足：m=n-k。其中n為G的頂點(diǎn)數(shù)，m為G的邊數(shù)。證明設(shè)森林中每棵樹(shù)的頂點(diǎn)數(shù)與邊數(shù)分別是ni和mi(i=1,2,…,k)。則由定理1，mi

=ni-1,i=1,2,…,k因此即

m=n-k

13/39推論2一棵階數(shù)大于或等于2的樹(shù)至少有兩片樹(shù)葉。證明設(shè)非平凡樹(shù)T有x片樹(shù)葉，n個(gè)點(diǎn),m條邊。因?yàn)門

連通非平凡，故T的其余n-x

個(gè)點(diǎn)的度至少為

。由§1.1定理2和§2.1定理1有：x+2(n-x)

≤度數(shù)之和=2m=2(n-1)x≥2定義2

設(shè)圖G是一個(gè)非平凡的無(wú)向連通圖，如果對(duì)G中每一條邊e,G-e都不連通，則稱G是一個(gè)最小連通圖。定理2

非平凡的無(wú)向圖G是樹(shù)的充要條件是G為最小連通圖。證明

這是定理1和定義2的直接結(jié)果。連通圖的割邊e是指刪去e后使G不連通的邊非平凡圖G是樹(shù)當(dāng)且僅當(dāng)它的每條邊均為割邊214/39例

設(shè)樹(shù)T

有ni

個(gè)度為i

的點(diǎn)，2≦i≦k（k>1),其余點(diǎn)均為葉，求T中葉點(diǎn)的數(shù)目。解設(shè)T

有x

片樹(shù)葉，則T的點(diǎn)數(shù)為：又由握手定理得：解得x為:故T的邊數(shù)為:x+n2+n3+…+nkx+n2+n3+…+nk-1x+2n2+3n3+…+knk=2(x+n2+n3+…+nk-1)x15/39§2.2樹(shù)的中心和形心定義1設(shè)G=(V,E)是一連通圖，

v∈V，令

e(v)=max{d(u,v)|u∈V}則稱e(v)為頂點(diǎn)v的離心率；又令

r(G)=min{e(v)|v∈V}

稱r(G)為圖G的半徑。比較圖的直徑與離心率的定義可知，圖G的直徑是G的最大離心率；e(v)

=r(G)的點(diǎn)

v

，稱為G的一個(gè)中心點(diǎn)，G中全體中心點(diǎn)的集合稱為G的中心。16/39例1

在下圖所示的樹(shù)中，圖中每個(gè)頂點(diǎn)處標(biāo)出的數(shù)字為該點(diǎn)的離心率。圖中的頂點(diǎn)u為該樹(shù)的中心，該樹(shù)的半徑r(G)

=4，直徑d(G)

=8。在該圖中，樹(shù)的中心是點(diǎn)u。478888675665656517/39定理5每棵樹(shù)有一個(gè)由一個(gè)點(diǎn)或兩個(gè)鄰接的點(diǎn)組成的中心。證明結(jié)論對(duì)于樹(shù)K1,K2

是成立的。我們證明任何一個(gè)其它的樹(shù)T，與除去T的所有度為1的頂點(diǎn)(即T的葉點(diǎn))得到的樹(shù)T1有同樣的中心。顯然，由T的一個(gè)給定的頂點(diǎn)u到T的任何一個(gè)其它點(diǎn)v的距離僅當(dāng)v是一葉點(diǎn)時(shí)，才可能達(dá)到最大值。于是故樹(shù)T與樹(shù)T1有相同的中心。43454566418/39重復(fù)這種除去端點(diǎn)的過(guò)程，我們相繼得到一系列與T具有相同中心的樹(shù)，因?yàn)門有限，故經(jīng)過(guò)有限步后，我們最終得到的樹(shù)是K1或K2，且K1,K2的中心即為T的中心。從而T的中心正好由一個(gè)頂點(diǎn)或兩個(gè)相鄰頂點(diǎn)組成。定義2

設(shè)T是樹(shù)，u是樹(shù)T的任意一個(gè)頂點(diǎn)，樹(shù)T在點(diǎn)u處的一個(gè)分枝是指包含u作為一個(gè)葉點(diǎn)的極大子樹(shù)，其分枝數(shù)為該頂點(diǎn)的度數(shù)；樹(shù)T在點(diǎn)u的分枝中邊的最大數(shù)目稱為點(diǎn)u的權(quán)；樹(shù)T中權(quán)值最小的點(diǎn)稱為它的一個(gè)形心點(diǎn)，全體形心點(diǎn)的集合稱為樹(shù)T的形心。19/39例在圖2-3的樹(shù)中，每個(gè)頂點(diǎn)處的數(shù)字表示該頂點(diǎn)的權(quán)值，權(quán)值為4的頂點(diǎn)為該樹(shù)的形心。定理6每一棵樹(shù)有一個(gè)由一個(gè)點(diǎn)或兩個(gè)鄰接的點(diǎn)組成的形心。(證明留作習(xí)題)20/39定義1

若圖G的生成子圖T是樹(shù)，則稱T為G的生成樹(shù)；若T為森林，稱它是G的生成森林。生成樹(shù)的邊稱為樹(shù)枝，G中非生成樹(shù)的邊稱為弦。§2.3生成樹(shù)圖和它的生成森林連通圖和它的一棵生成樹(shù)21/39定理5

連通圖的生成樹(shù)必存在。證明

給定連通圖G，若G無(wú)圈，則G就是自己的生成樹(shù)。若G有圈，則任取G中一個(gè)圈C，記刪去C中一條邊后所得之圖為H1。顯然在H1中，圈C已不存在，但仍連通。

定理4的證明方法也是求生成樹(shù)的一種方法，稱為“破圈法”。若H1中還有圈，重復(fù)以上過(guò)程，直至得到一個(gè)無(wú)圈的連通圖H。H便是G的生成樹(shù)。22/39解

這是一個(gè)求圖G的生成樹(shù)的問(wèn)題。因G有5個(gè)點(diǎn)，由定理1的（4）知G的生成樹(shù)有4條邊，即至少需4條光纖不出故障，通信才不會(huì)中斷，且這些不出故障的光纖應(yīng)按上圖中的H進(jìn)行分布，其中H是由破圈法求得的G的一個(gè)生成樹(shù)。（注：H不唯一）例1設(shè)有五個(gè)城市v1,v2,v3,v4,v5。它們之間有通信光纖連通，其布置如圖中的G。問(wèn)至少有幾條光纖不出故障，城市間的通信才不會(huì)中斷，且這些不出故障的光纖應(yīng)如何分布？Gv1v2v3v4v5v1v2v3v5v4H23/39推論

若G是連通的(n,m)圖，則m≥n-1

。證明設(shè)G是連通圖，由定理5，包含一棵生成樹(shù)T，所以G的邊e稱為被收縮，是指刪去邊e并使它的兩個(gè)端點(diǎn)重合,如此得到的圖記為G●e

。e1e5e2e4e3圖(a)圖(b)例下圖(b)表示圖(a)收縮邊e1,e2,e3,e4,e5后得到的圖。

24/39有下列關(guān)系:

若

e是G的一條邊，則有若T是樹(shù)，則T●e也是樹(shù)。

定理6

(Cayley)若e是圖G的邊，則其中表G的生成樹(shù)的棵數(shù).凱萊(Cayley1821—1895):劍橋大學(xué)數(shù)學(xué)教授，著名代數(shù)學(xué)家，發(fā)表論文數(shù)僅次于Erdos,Euler,Cauchy.著名成果是1854年定義了抽象群，并且得到著名定理：任意一個(gè)群都和一個(gè)變換群同構(gòu)。同時(shí)，他也是一名出色的律師，作律師14年期間，發(fā)表200多篇數(shù)學(xué)論文，著名定理也是在該期間發(fā)表的。凱萊生成樹(shù)遞推計(jì)數(shù)公式是他在1889年建立的。25/39證明由于G的每一棵不包含e

的生成樹(shù)也是G-e的生成樹(shù)。由此推知，τ(G-e)

就是G的不包含e的生成樹(shù)的棵數(shù)。類似,

τ(G●e)

就是G的包含e的生成樹(shù)的棵數(shù)。從而知結(jié)論成立。例對(duì)右圖

G試計(jì)算τ(G)

。G26/39G解

τ(G)的部分遞推計(jì)算過(guò)程如下（其中τ

已被省略）：=+=+=2+2=4=4所以τ(G)

=4+4=8定理7

τ(Kn)

=nn-2。定理7

τ(Kn)

=nn-2。分析：設(shè)Kn的頂點(diǎn)集是N={1,2,…,n}。

取自N可能組成的長(zhǎng)為n-2的序列的個(gè)數(shù)是nn-2。

為了證明本定理，只須在Kn的生成樹(shù)的集和這種序列的集之間建立一一對(duì)應(yīng)的關(guān)系。把N看成是一個(gè)有序集，設(shè)s1是T中第一個(gè)1度頂點(diǎn)，把與s1相鄰的那個(gè)頂點(diǎn)取作t1。現(xiàn)在從T中刪去s1，用s2記T-s1中第一個(gè)1度頂點(diǎn)，并把與s2相鄰的那個(gè)頂點(diǎn)作為t2。重復(fù)這個(gè)過(guò)程，直到tn-2被確定，留下來(lái)恰好是有兩個(gè)頂點(diǎn)的一棵樹(shù)。因此，對(duì)于Kn的每顆生成樹(shù)T，恰好與唯一的序列(t1,t2,…,tn-2)對(duì)應(yīng)。27/3951327846（）4,3,5,3,4,528/39逆過(guò)程：注意T的任意一點(diǎn)v在(t1,t2,…,tn-2)中出現(xiàn)d(v)-1次。且度為1的點(diǎn)，即葉點(diǎn)不會(huì)出現(xiàn)在該序列中。設(shè)s1是不在(t1,t2,…,tn-2)中的N的第一個(gè)頂點(diǎn)；連接s1與t1

。其次,設(shè)s2是不在(t2,…,tn-2)中的N\{s1}的第一個(gè)頂點(diǎn),并且連接s2與t2

。如此繼續(xù)下去，直至確定了n-2條邊：s1t1,s2t2,…,sn-2tn-2。最后添加這樣一條邊：它連接N\{s1,s2,…,sn-2}中剩下的兩個(gè)頂點(diǎn)，即可得到T。51327846N\{s1,s2,…,sn-2}={5,8}{s1,s2,…,sn-2}={1,2,6,7,3,4}（）4,3,5,3,4,5（）3,5,3,4,5（5,3,4,5）（3,4,5）（4,5）（5）29/39注以上討論的生成樹(shù)的棵數(shù)均指標(biāo)定圖而言。標(biāo)定圖的生成樹(shù)的數(shù)量遠(yuǎn)大于非標(biāo)定圖生成樹(shù)的數(shù)量。如標(biāo)定圖K6有66-2=1296棵生成樹(shù)，而不同構(gòu)的6階樹(shù)僅6棵。按直徑從2到5依次是：30/39定義2

設(shè)T是圖G=(V,E)的一棵生成樹(shù)，m和n分別是G的邊數(shù)與頂點(diǎn)數(shù)，e1,e2,…,em-n+1為T的弦，設(shè)Cr是T加er產(chǎn)生的圈，r=1,2,…,m-n+1,稱Cr為對(duì)應(yīng)于弦er的基本回路，｛C1,C2,…,Cm-n+1｝稱為對(duì)應(yīng)于生成樹(shù)T的基本回路系統(tǒng)。例1

在下圖中，（a）為一無(wú)向圖，(b)為(a)的一棵生成樹(shù)，(c)與(d)分別是對(duì)應(yīng)于弦e6與e3的基本回路。31/39e4

e5

e6

(c)e1

e2

e3

e4

(d)定理8

連通圖G的任一回路均可表示成若干個(gè)基本回路的對(duì)稱差。對(duì)稱差G1△G2

：G1△G2=(G1∪G2)-(G1∩G2)=(G1-G2)∪(G2-G1)32/39例

假定有四個(gè)城市，準(zhǔn)備修筑鐵路將這四個(gè)城市連接起來(lái)，已知各城市間修鐵路的造價(jià)預(yù)算如下圖所示，圖中邊上的數(shù)值表示預(yù)算的造價(jià)（以億元為單位），問(wèn)如何選擇線路以使總造價(jià)最小。v1v4v3v2135187§2.4最小生成樹(shù)33/39分析：設(shè)求出的線路為H，因要保證將四個(gè)城市連接起來(lái)，故H應(yīng)是圖中的連通生成子圖。同時(shí)，因要保證造價(jià)最小，故H中應(yīng)無(wú)圈（因若有圈，則刪去圈中某邊還能保證連通性，但造價(jià)被減少）。所以H應(yīng)是圖中的生成樹(shù)，并且還應(yīng)是該圖中所有生成樹(shù)中邊權(quán)之和最小的一個(gè)。v1v4v3v213518734/39

定義3在連通賦權(quán)圖G中，邊權(quán)之和最小的生成樹(shù)稱為G的最小生成樹(shù)。

給定無(wú)環(huán)連通賦權(quán)圖G，設(shè)G有n個(gè)點(diǎn)，m條邊，下面給出求G的最小生成樹(shù)的一個(gè)算法?？唆斔箍藸査惴ǎ?）將G的邊按權(quán)從小到大排列，不妨設(shè)為

e1,e2，…，em(2)取T={e1}，再?gòu)膃2開(kāi)始依次將排好序的邊加入到T中，使加入后由T導(dǎo)出的子圖（即由T作為邊集，T中的邊相關(guān)聯(lián)的點(diǎn)作為點(diǎn)集所確定的子圖）不含圈，直至T中含有n-1條邊。35/39解邊權(quán)排序?yàn)?,1,2,2,3,3,4,4,5,5,6,6。對(duì)應(yīng)的邊為v1v2，v4v6，v2v7，v1v7，v2v4，v1v6，v2v3，v6v7，v4v5，v4v7，v5v6，v3v4例2

圖G如所示，求G的最優(yōu)樹(shù)。v1v7v2v3v4v6v512346515643依據(jù)算法，其中畫(huà)有下橫線的邊為依次被選為生成樹(shù)T的邊,且W(T)=