圖論 第二章 樹

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

(1)

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

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

無圈圖稱為森林，樹也是森林；§2.1樹的概念與性質(zhì)由定義,平凡圖也是樹,稱為平凡樹。3/39樹樹不是樹不是樹，是森林例平凡樹●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é)點v及v關(guān)聯(lián)的所有邊得到的圖，稱為刪除結(jié)點v。又設(shè)VV，用G-V

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

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

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

“（1）G是樹

因G是樹，樹是連通的，故G中任意兩個不同點之間存在路。下證唯一性。

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

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

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

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

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

相加得

n1+n2=m1+m2+2（*）n1=m1+1，n2=m2+1同時有

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

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

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

mi

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

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

與v

的路，矛盾。vuG+uvC’11/39（6）G無圈，添加任一條邊可得唯一的圈。（1）G是樹需證明G連通。假設(shè)不連通，則存在兩個頂點u與v之間不存在通路，因此增加uv邊不會在G+uv產(chǎn)生圈，矛盾！命題得證12/39推論1由k棵樹組成的森林滿足：m=n-k。其中n為G的頂點數(shù)，m為G的邊數(shù)。證明設(shè)森林中每棵樹的頂點數(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è)非平凡樹T有x片樹葉，n個點,m條邊。因為T

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

個點的度至少為

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

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

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

非平凡的無向圖G是樹的充要條件是G為最小連通圖。證明

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

設(shè)樹T

有ni

個度為i

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

有x

片樹葉，則T的點數(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樹的中心和形心定義1設(shè)G=(V,E)是一連通圖，

v∈V，令

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

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

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

=r(G)的點

v

，稱為G的一個中心點，G中全體中心點的集合稱為G的中心。16/39例1

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

=4，直徑d(G)

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

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

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

若圖G的生成子圖T是樹，則稱T為G的生成樹；若T為森林，稱它是G的生成森林。生成樹的邊稱為樹枝，G中非生成樹的邊稱為弦?！?.3生成樹圖和它的生成森林連通圖和它的一棵生成樹21/39定理5

連通圖的生成樹必存在。證明

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

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

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

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

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

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

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

若

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

定理6

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

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

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

τ(G●e)

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

G試計算τ(G)

。G26/39G解

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

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

=4+4=8定理7

τ(Kn)

=nn-2。定理7

τ(Kn)

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

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

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

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

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

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

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

e5

e6

(c)e1

e2

e3

e4

(d)定理8

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

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

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

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

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

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

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