《離散數(shù)學(xué)教程》第9章 圖與樹

離散數(shù)學(xué)第9章圖與樹引例哥尼斯堡七橋問題Cb1b2

b6Ab5Bb3b4b7Db1b2b6

Bb4b7DAb5Cb3第9章圖與樹9.1圖9.2路徑、回路及連通圖

9.3圖的矩陣表示9.4樹9.1圖9.1.1圖的基本概念定義9.1

由以下兩個部分所組成的離散結(jié)構(gòu)G，稱為圖：（1）非空集合V(G)，稱為圖G的結(jié)點集，其成員稱為結(jié)點或頂點。結(jié)點用拉丁字母或希臘字母來表示。（2）多重集合E(G)，稱為圖G的邊集，其成員稱為邊。邊用結(jié)點的序偶或結(jié)點的兩元素多重集表示。結(jié)點序偶表示的邊稱為有向邊，兩元素多重集表示的邊稱為無向邊。當(dāng)圖的邊均為有向邊時，稱該圖為有向圖；當(dāng)圖的邊均為無向邊時，稱該圖為無向圖。

圖G的表示——二元組<V(G)，E(G)>,或<V，E>。9.1圖9.1.1圖的基本概念定義9.2：（1）邊e=<u,v>時：稱邊e關(guān)聯(lián)結(jié)點u、v，或u，v為e

的端點，并稱u為e

的起點，v為e

的終點。（2）邊e={u,v}時：稱邊e關(guān)聯(lián)結(jié)點u、v，并稱u、v為e的端點，這時u、v為相鄰(接)的結(jié)點。（3）當(dāng)e=<u,v>或{u,v}，u=v時，<u,v>和{u,v}均稱為環(huán)。例9.1：(1)哥尼斯堡七橋圖，可表示為：<{A,B,C,D},{{A,C},{A,C},{A,D},{A,D},{A,B},{C,B},{D,B}}>(2)左圖為一有向圖，可表示為：<{v1,v2,v3,v4,v5,v6},{<v1,v1>，<v2,v3>，<v3,v2>，<v3,v4>，<v5,v4>，<v5,v5>}>b1b2b6

Bb4b7DAb5Cb39.1圖9.1.1圖的基本概念e1v1v2e3e2v3v6e4e5e6v4v59.1圖9.1.1圖的基本概念定義9.3

設(shè)圖G為<V，E>。

（1）當(dāng)V和E為有限集時，稱G為有限圖，否則稱G為無限圖。（2）當(dāng)邊集合中至少有一個元素的重數(shù)不小于2時，稱G為重圖，否則稱G為單圖；重數(shù)不小于2的邊稱為重邊，或平行邊。（3）無環(huán)和重邊的圖稱為簡單圖。當(dāng)G為簡單無向圖時，也常用

(n,m)表示圖G，其中n=V

，m=E

。9.1圖9.1.1圖的基本概念（4）任何兩個不同結(jié)點間都有邊關(guān)聯(lián)的簡單無向圖，稱為完全圖。

n個頂點的完全圖常記作Kn。不是任何邊的端點的結(jié)點稱為孤立結(jié)點，僅由孤立結(jié)點構(gòu)成的圖K1（E=）稱為零圖。（5）當(dāng)給G賦予映射f：V→W，或g：E→W，W為任意集合，常為實數(shù)集的子集，此時稱G為賦權(quán)圖，用<V,E,f>或<V,E,g>或<V,E,f,g>表示之。f(v)稱為結(jié)點v的權(quán)，g(e)稱為邊e的權(quán)。

f(G)稱為圖G的結(jié)點權(quán)和，g(G)稱為圖G的邊權(quán)和。9.1.1圖的基本概念b1b2b6

Bb4b7DAb5Cb3重圖（b1、b2為重邊）有向圖e1為環(huán)，v6為孤立結(jié)點例9.2：9.1圖e1v1v2e3e2v3v6e4e5e6v4v59.1圖9.1.1圖的基本概念

例9.2：(a)簡單圖(b)完全圖K5(c)賦權(quán)圖f(v1)=9.3，g(e1)=800

f(G)=37.8，g(G)=4580

7209.380010009.986075.6v1e112006.09.1.2結(jié)點的度9.1圖定義9.4

在無向圖中，結(jié)點v的度d(v)是結(jié)點v作為邊的端點的次數(shù)。在有向圖中，結(jié)點v的出度是v作為有向邊起點的次數(shù)，v的入度是v作為有向邊終點的次數(shù)。結(jié)點v的度d(v)是v的出度d+(v)

與入

度d-(v)

的和。(a)d(v1)=5，環(huán)e兩次以結(jié)點v1為端點例9.3:

v3

v1

e

v2

v3

v1

e

v2(b)d+(v1)=2，d-(v1)=3，d(v1)=d+(v1)+d-(v1)=59.1.2結(jié)點的度9.1圖定理9.1：對任意圖G，設(shè)其邊數(shù)為m,頂點集為{v1,v2,…，vn}，那么證：當(dāng)一邊關(guān)聯(lián)于兩個不同結(jié)點時，它分別使兩結(jié)點各增加一度;當(dāng)一邊為一環(huán)時,它給該結(jié)點增加兩度,因此各結(jié)點的度的總和是邊的數(shù)目的兩倍。當(dāng)G為有向圖時，可改寫為:9.1.2結(jié)點的度9.1圖定理9.2：圖的奇數(shù)度頂點必為偶數(shù)個。證：反設(shè)某圖有奇數(shù)個奇數(shù)度頂點，則它們的度的總和是奇數(shù)。由于其余頂點是偶數(shù)度的，故這些頂點的度的總和是偶數(shù)。于是，圖的所有頂點的度數(shù)總和為奇數(shù)（奇數(shù)＋偶數(shù)），與定理8.1矛盾。命題得證。定理9.3：自然數(shù)序列(a1,a2,…,an)稱為一個度序列，如果它是一個圖的頂點的度的序列。(a1,a2,…,an)為一個度序列，當(dāng)且僅當(dāng)為一偶數(shù)。證必要性由定理9.l立得。證充分性：設(shè)為偶數(shù)，那么（a1,a2,…,an）中的奇數(shù)必定是偶數(shù)個。建立n個頂點的圖G，使得（1）當(dāng)ai為偶數(shù)2k時,vi上恰有k個環(huán)。（2）當(dāng)ai為奇數(shù)2k+1，必有aj為奇數(shù)?？墒箆i上恰有k個環(huán)及一條非環(huán)的邊，此邊以頂點vj為另一個端點。由于為奇數(shù)的ai是偶數(shù)個，上述構(gòu)造過程是可行的，構(gòu)造得到的圖G滿足d(vi)＝ai。定理得證。9.1.2結(jié)點的度9.1圖9.1.2結(jié)點的度9.1圖定義9.5（1）一度的頂點稱為懸掛點。（2）各頂點的度均相同的圖稱為正則圖。各頂點度均為k的正則圖稱為k-正則圖。完全圖都是正則圖。定義9.6

設(shè)圖G1＝<V1，E1>，G2＝<V2，E2>，如果V1V2，E1E2

且E1≤E2，則稱G1為G2的子圖。如果G1是G2的子圖，且G1不同于G2，則稱G1為G2的真子圖。如果G1是G2的子圖，且V1=V2，則稱G1為G2的生成子圖。定義9.7

設(shè)簡單無向圖G1＝<V1，E1>，G2＝<V2，E2>，稱G1與G2

互為補(bǔ)圖，如果V1=V2，E1E2=，且<V1(或V2),E1∪E2>是簡單完全圖。9.1.3子圖、補(bǔ)圖及圖同構(gòu)9.1圖9.1.3子圖、補(bǔ)圖及圖同構(gòu)9.1圖(a)和(b)關(guān)于(c)互為補(bǔ)圖。(a)(c)的真子圖(b)(c)的真子圖(c)完全圖K5例9.4：定義9.8

設(shè)G1＝<V1，E1>，G2＝<V2，E2>為兩個簡單圖，稱G1與G2

同構(gòu)，如果存在一個雙射h：V1V2，使得對任意vi，vj

V1<vi,vj>

E1<h(vi),h(vj)>E2或{vi,vj}E1{h(vi),h(vj)}E2

9.1.3子圖、補(bǔ)圖及圖同構(gòu)9.1圖v1abcdefh(v)δγ例9.5(1)：abcdefγδ(a)G1(c)

G2雙射h：9.1.3子圖、補(bǔ)圖及圖同構(gòu)9.1圖

G1，G2不是同構(gòu)的。(a)G1(b)

G2例9.5(2)：dabcδγ例9.6

某人m帶一條狗d，一只貓c和一只兔子r過河。m每次游過河時只能帶一只動物，而沒人管理時，狗與兔子不能共處，貓和兔子也不能共處。問m怎樣才能把三個動物帶過河去？9.1.4圖的應(yīng)用9.1圖<{d,r},{m,c}><{c},{m,d,r}><{m,c,r},t4bmhur><{r},{m,c,d}><{c,r},{m,d}><{r},{m,c,d}><{m,d,r},{c}><o5sw4pf,{m,c,r}><{m,d,c,r},><{d,c},{m,r}><{m,d,c},{r}><{m,r},{c,d}><,{m,d,c,r}>例9.7

用有向圖描述識別符號串01010的狀態(tài)轉(zhuǎn)換系統(tǒng)。9.1.4圖的應(yīng)用9.1圖0SS1S2S3S4S51010101例9.8

甲乙兩人進(jìn)行乒乓球賽，規(guī)定一方連勝兩局或勝局首先達(dá)到3局者為勝方。問甲乙至少、至多要進(jìn)行多少局比賽。9.1.4圖的應(yīng)用9.1圖

1

甲乙

2233

乙甲乙甲終止44終止甲乙甲乙終止55終止甲乙甲乙終止終止終止終止乙甲乙甲比賽至少要進(jìn)行2局，至多要進(jìn)行5局。9.2.1路徑、通路與回路9.2路徑、回路及連通圖定義9.9：圖G的頂點v1到頂點vl的擬路徑是指如下頂點與邊的序列：

v1,e1,v2,e2,v3,…,vl-1,el-1,vl

其中v1,v2,v3,…,vl-1,vl

為G的頂點，e1,e2,…,el-1

為G的邊，且ei

(i=1,2,…,l-1)以vi及vi+1為端點，(對有向圖G，ei以vi為起點，以vi+1為終點)。擬路徑的邊數(shù)l-1稱為該擬路徑的長度。當(dāng)ei

(i=1,2,…,l-1)各不相同時，該擬路徑稱為路徑，又當(dāng)vi

(i=1,2,…,l)各不相同時(除v1與vl)，則稱此路徑為通路。

v1=vl

的路徑稱為閉路徑；v1=vl的通路稱為回路。表示：簡單圖或無平行邊的有向圖，擬路徑、路徑、通路等可用頂點序列表示，如（v1,v2,v3,…,vl-1,vl）9.2.1路徑、通路與回路9.2路徑、回路及連通圖

(v2,v3,v1,v2)回路，長度3例9.9（1）(v1,v2,v3,v1,v2,v5)有重復(fù)邊點，擬路徑，長度5(v2,v3,v1,v2,v5,v4)無重復(fù)邊，路徑，長度5(v2,v3,v4)通路，長度2(v2,v3,v1,v2,v5,v4,v2)閉路徑，長度6

v5v2v1v3v4

v5v2v1v3v4

v5v2v1v3v4

v5v2v1v3v4

v5v2v1v3v49.2.1路徑、通路與回路9.2路徑、回路及連通圖例9.9（2）(v1,v2,v5,v4,v3,v1)回路，長度5

(v2,v3,v4,v5)路徑，長度3

v5v2v1v3v4

v5v2v1v3v4定理9.4

在有n個頂點的圖G中，如果有從頂點u到v(u

v)的擬路徑，那么從u到v必有路徑，并且必有長度不大于n–1的通路。證不失一般性，設(shè)G為一簡單圖。若G有從u到v的擬路徑(u=v1,v2,v3,…,vl-1,vl

=v)，且沒有vi＝vj

(i,j=l，2，…,l)，那么它便是一條通路，且l≤n–1；若G的這一擬路徑中有，vi＝vj

,則它可表示為

(u=v1,v2,…,vi,…,vi,…,vl-1,vl

=v)那么從中刪去從vi+1到第二個vi之間的所有邊及頂點，便得到一條從u到v的更短的擬路徑

(u=v1,v2,…,vi,…,vl-1,vl

=v)然后重復(fù)上述討論，直至沒有邊重復(fù)出現(xiàn)、沒有頂點重復(fù)出現(xiàn)，從而得到從u到v的路徑和長度不超過n–1的通路。9.2.1路徑、通路與回路9.2路徑、回路及連通圖定理9.5

在具有n個頂點的圖G中，如果有從v到v的閉路徑，那么必定有一條從v到v的長度不大于n的回路。9.2.1路徑、通路與回路9.2路徑、回路及連通圖例9.10閉路徑(v2,v3,v1,v2,v5,v4,v2)長度3的回路(v2,v5,v4,v2)擬路徑(v2,v3,v1,v2,v5,v4)長度2的通路(v2,v5,v4)

v5v2v1v3v4

v5v2v1v3v4定義9.10

稱圖中頂點u到v是達(dá)可的，如果u=v，或者有u到v的路徑。定義9.11

稱無向圖G是連通的，如果對G的任何兩個頂點u，v，u到

v都是可達(dá)的。稱有向圖G是強(qiáng)連通的，如果G的任何兩個頂點都是相互可達(dá)的；稱有向圖G是單向連通的，如果G的任何兩個頂點中，至少從一個頂點到另一個頂點是可達(dá)的；稱有向圖G是弱連通的，如果G的有向邊被看作無向邊時是連通的。定義9.12

圖G’稱為無向圖G的連通分支，如果G’是G的子圖，G’是連通的，并且不存在G的真子圖G’’，使G’’是連通的，且G’’以

G’為其真子圖。9.2.2連通性9.2路徑、回路及連通圖9.2路徑、回路及連通圖(a)連通圖(b)非連通圖(兩連通分支)(c)弱連通圖(d)單向連通圖(e)強(qiáng)連通圖例9.119.2.2連通性9.2路徑、回路及連通圖9.2.2連通性

定義9.13

設(shè)G’為有向圖G的子圖，若G’是強(qiáng)連通的（單向連通的、弱連通的），且G沒有強(qiáng)連通（單向連通、弱連通）的真子圖

G’’，使G’為其真子圖，那么稱G’為G的一個強(qiáng)分圖（單向分圖、弱分圖）。9.2路徑、回路及連通圖9.2.2連通性強(qiáng)分圖：

<{1,2,3},{e0,e2,e3}>，<{4},>，<{5},>，<{6},>，<{7,8},{e7,e8}>，<{9},>單向分圖：<{1,2,3,4,5},{e0,e1,e2,e3,e4,e5}>，<{5,6},{e6}>，

<{7,8},{e7,e8}>，<{9},>弱分圖:<{1,2,3,4,5,6},{e0,e1,e2,e3,e4,e5,e6}>，<{7,8},{e7,e8}>，<{9},>例9.12

2e4

4e0e2e1e5e691e335867e7e89.2路徑、回路及連通圖9.2.2連通性定理9.6

一個圖G是不連通的，當(dāng)且僅當(dāng)G的頂點集V可以分成兩個不交的非空子集V1和V2，使得任何邊都不以V1的一個頂點和V2

一個頂點為其兩端點。證充分性：顯然。必要性：設(shè)G不連通，那么有v1及v2，v2到v1是不可達(dá)的。構(gòu)造V1={v

v到v1是可達(dá)的}

V2=VV1

顯然V1，

V2，因為v1V1，v2V2。若有邊的兩端點分別在V1和V2中，那么該邊在V2中的端點到v1是可達(dá)的了，這與V2

的定義沖突。9.2路徑、回路及連通圖9.2.2連通性定理9.7

如果圖G恰有兩個不同的奇數(shù)度的頂點u，v，那么u到v必定是可達(dá)的。證如果u到v不可達(dá)，那么G不是連通的，u與v必分屬于兩個不連通的子圖G1，G2。從而G1，G2都是圖，且都恰有一個奇數(shù)度頂點。這是不可能的（定理9.2）。因而u到v是可達(dá)的。9.2路徑、回路及連通圖9.2.2連通性定理9.8：若圖G為具有n個頂點、k個連通分支的簡單圖，那么G

至多有條邊。證明：

設(shè)G的k個連通分支的頂點數(shù)分別是n1，n2，…，nk，從而，n=n1+n2+…+nk，諸ni≥1。

各連通分支的邊數(shù)不超過，因此G的邊數(shù)m滿足：現(xiàn)證9.2路徑、回路及連通圖9.2.2連通性證由于，因此從而于是定理得證。

v1v5

v2v4v7

v3v69.2.3連通度9.2路徑、回路及連通圖定義9.14

設(shè)S為連通圖G的頂點集V的子集，稱S為G的點割集,如果從G中刪除S中的所有頂點（注：刪除結(jié)點v時，同時要刪掉關(guān)聯(lián)v的所有邊）后得到的圖不連通，但S的任何真子集均無這一特性。當(dāng)點割集為單元素集合｛v｝時，v稱為割點。割集{v1，v3}，{v5，v6}，v4是割點，{v1，v3，v4}不是點割集。例9.139.2.3連通度9.2路徑、回路及連通圖定義9.15

χ(G)稱為G的點連通度，定義如下：點連通度1-9.2.3連通度9.2路徑、回路及連通圖定義9.16

設(shè)S為連通圖G邊集E的子集，稱S為G的邊割集，或割集，如果從G中刪除S的所有邊后所得的圖是不連通的，但S的任何真子集均無這一特性。當(dāng)割集為單元素集｛e｝時，稱e為割邊。割集{{v1,v2},{v2,v3}}，{{v1,v4},{v3,v4}}等，它沒有割邊。{{v1,v4},{v3,v4},{v5,v4}}不是割集，其中{v5,v4}是多余的。9.2.3連通度9.2路徑、回路及連通圖定義9.17

λ(G)稱為圖G的邊連通度，定義如下：邊連通度為2

定理9.9

對任何簡單無向圖G，χ(G)≤λ(G)≤δ(G)證若G為不連通圖或單一孤立結(jié)點的圖，那么據(jù)定義知:

χ(G)=λ(G)=0≤δ(G)或χ(G)=λ(G)=δ(G)=0。若G為完全圖Kn，那么χ(G)=λ(G)=δ(G)=n–1。對其它情況，先證λ(G)≤δ(G)。由于度數(shù)最小的那個結(jié)點上關(guān)聯(lián)的所有邊被刪除后，

G顯然不再連通，因而λ(G)至多是δ(G)，即λ(G)≤δ(G)。9.2.3連通度9.2路徑、回路及連通圖uvG1G29.2.3連通度9.2路徑、回路及連通圖定理9.9

對任何簡單無向圖G，χ(G)≤λ(G)≤δ(G)再證χ(G)≤λ(G)。當(dāng)在G中刪去構(gòu)成割集的λ(G)條邊，則G不連通，設(shè)產(chǎn)生連通分支G1(n1,m1)，G2(n2,m2)。可證G1，G2中分別有結(jié)點u,v，{u,v}不是割集中的邊。（否則割集中的邊有λ(G)=n1n2n–1δ(G)，從而λ(G)=n–1=δ(G)，G為完全圖）。于是，刪除G1中除u以外的割集中邊的s1個端點，再刪除G2中與u相鄰的s2個結(jié)點，即刪除s1+s2≤λ(G)個結(jié)點，就可使G不連通（結(jié)點u,v不可達(dá)，如圖）。因此G的點連通度χ(G)不超過λ(G)，即χ(G)≤λ(G)。uvG1G2證因為2m是圖G各頂點的度數(shù)總和，因此n個頂點中至少有一個頂點的度不超過,故G的邊連通度λ(G)不超過。定理9.10

設(shè)G為n個頂點、m條邊的簡單連通圖，那么

λ(G)≤9.2.3連通度9.2路徑、回路及連通圖例9.14

（1）零圖的鄰接矩陣為零矩陣。（2）一圖的每個頂點以且僅以環(huán)為關(guān)聯(lián)的邊,那么該圖的鄰接矩陣為幺矩陣。

（3）無向圖的鄰接矩陣是對稱矩陣。

（4）

定義9.18

設(shè)G=<V,E>為一無重邊的有向圖。其中V={v1,v2,…,vn}，那么nn矩陣A=[aij]，稱為圖G的鄰接矩陣，記為A[G]:9.3.1鄰接矩陣9.3圖的矩陣表示>,<0>,<1=EvvEvvajijiij當(dāng)當(dāng)

v1v2

v4

v3鄰接矩陣9.3.1鄰接矩陣設(shè)A為圖G的鄰接矩陣，A=[aij]，Aι為A的轉(zhuǎn)置矩陣，

?為通常的矩陣乘運算符。我們知道，若A?B=C，A=[aij]，B=[bij]，C=[cij]，那么

用Al表示l個矩陣A的乘積。9.3圖的矩陣表示,v3到v1長度為3的擬路徑:（v3,v1

,v1

,v1），（v3,v4,v1

,v1）（v3,v2,v4,v1），（v3,v2,v3,v1）事實(1)

令A(yù)l=[]，那么的意義是：G中從頂點vi到vj的長度為l的擬路徑恰為條。9.3.1鄰接矩陣9.3圖的矩陣表示

v1v2

v4

v3驗證：9.3.1鄰接矩陣對l歸納證明事實(1)

l=1時，Al

=A=[]=[]，命題顯然真。設(shè)Al

=[]中對任意i,j均表示vi到vj的長度為l的擬路徑條數(shù)?？紤]Al+1=[]。由矩陣乘積定義知9.3圖的矩陣表示其中表示從vi到vk有條長度為l的擬路徑。而表示從vi經(jīng)由vk到vj的長度為l+1的擬路徑數(shù)目，因而和式(9-5)表明是從vi到vj的長度為l+1的擬路徑的總條數(shù)。歸納完成，(1)得證。(9-5)9.3.1鄰接矩陣9.3圖的矩陣表示事實(2)

令A(yù)?Aι=[bij]，那么的意義是：有個頂點v，使得vi到v，

vj到v都有邊（兩邊交于v）。因而表示頂點vi的出度。驗證:

v1v2

v4

v3b31=2，正有兩個頂點v1，v2，使得v3與v1到它們都有邊；b33=3，頂點v3的出度恰為3。9.3.1鄰接矩陣9.3圖的矩陣表示證明事實(2)根據(jù)矩陣乘積的定義:等價于有bij個k的值使aikajk=1,

有bij個k的值使aik=1且ajk=1,有bij個頂點vk使vi到vk有邊且vj到vk也有邊。這正是事實(2)所表明的。9.3.1鄰接矩陣9.3圖的矩陣表示事實(3)

令A(yù)ι

?A=[bij]，那么bij的意義是：有個頂點v，使得v到vi,v到vj都有邊；因而表示頂點vi的入度。驗證:

v1v2

v4

v3b31＝0，確無到v3，v1均有邊的頂點；b44=2，v4的入度正是2。矩陣運算：設(shè)n個頂點的圖G的鄰接矩陣為A，若A=[aij]，C=[cij]，

A∨C=[dij]dij=aij∨cij

A·C=[eij]9.3.2路徑矩陣與可達(dá)性矩陣9.3圖的矩陣表示A(m)表示A·A·…·A(m個A的·乘積)矩陣B＝A∨A(2)∨…∨A(n)

bij=1當(dāng)且僅當(dāng)圖G中有vi到vj的路徑。定義9.19

設(shè)A是圖G的鄰接矩陣，那幺矩陣

B＝A∨A(2)∨…∨A(n)稱為圖G的路徑矩陣，矩陣P＝I∨B，其中I為nn么矩陣，稱為圖G的可達(dá)性矩陣。9.3.2路徑矩陣與可達(dá)性矩陣?yán)?.15

計算下圖的路徑矩陣B與可達(dá)性矩陣P。9.3圖的矩陣表示

v1v2

v3v5

v4B=A∨A(2)∨A(3)∨A(4)∨A(5)

P=I∨B定義9.20

連通無回路的無向圖稱為樹。樹中的懸掛點又稱為樹葉，其它結(jié)點稱為分支點。單一孤立結(jié)點稱為空樹。諸連通分支均為樹的圖稱為森林，樹也是森林。例9.16

9.4.1樹的基本概念9.4樹樹樹森林定理9.11

設(shè)圖T為一樹，其頂點數(shù)、邊數(shù)分別是n,m,那么

n–m=1或m=n–1證對T的頂點數(shù)n歸納。

n=1時m=0，故n–m=1成立?，F(xiàn)設(shè)n=k時命題真。令T有k+1個頂點。在T中刪一懸掛點，產(chǎn)生圖T1(k,m–1)，它必定是樹，且其頂點數(shù)為k=n–1。根據(jù)歸納假設(shè)，

k–(m–1)=n–1–(m–1)=1成立，即n–m=1真。歸納完成，定理得證。9.4.1樹的基本概念9.4樹定理9.12

任何不少于兩個頂點的樹都至少有兩片葉。證設(shè)T為任一樹，其頂點數(shù)、邊數(shù)分別為n,m。又設(shè)T中至多只有一個頂點是葉，那么

2m=(vi)≥2(n–1)+1=2n–1

m≥n

–>n–1這與定理9.11矛盾。因此T至少有兩片葉。9.4.1樹的基本概念9.4樹9.4.1樹的基本概念9.4樹定理9.13：“(n，m)圖T為樹”與下列5命題中的每一命題等價：(1)

T無回路且m=n–1。(2)

T連通且m=n–1。(3)

T無回路，但任意添加邊時，T中產(chǎn)生唯一的一條回路。(4)

T連通，但刪去任一邊時便不再連通(T的每一邊均為割邊)。(5)

任意兩個不同頂點之間有且僅有一條通路。證：記“T為樹”即“T連通無回路”為命題(0)。證明過程：(0)(1)(2)(3)(4)(5)(0)9.4.1樹的基本概念9.4樹(0)(1)

這由定理9.14立得。(1)(2)

設(shè)T無回路，m=n–1，欲證T連通。反設(shè)T有k個連通分支（k≥2），T1，T2,…

，Tk，它們的頂點數(shù)分別是n1,n2,…,nk，邊數(shù)分別是m1,m2,…,mk，顯然mi=ni–1(i=1,2,…,k)于是

矛盾。因此T連通。9.4.1樹的基本概念9.4樹(2)(3)

設(shè)T連通且m=n–1。

先證T無回路，為此對n歸納:

n=1時顯然T無回路，因這時m=n–1=0。設(shè)頂點數(shù)為n–1的滿足題設(shè)的圖無回路，考慮頂點數(shù)為n的圖T。去掉T的一懸掛點構(gòu)成T

。顯然T

仍連通，且m=m–1=n–2=n–1因此由歸納假設(shè)T

無回路。在T

上加回所刪去的懸掛點得T，故T亦無回路。

再證添加任一邊產(chǎn)生唯一回路，設(shè)在T的頂點vi

、vj

間添加邊e。由于T連通，故原本有vi到vj的通路，此通路連同邊e構(gòu)成T∪{e}的一條回路。若此回路不唯一，那么去掉邊e后T仍有回路，與以上證明沖突。得證。9.4.1樹的基本概念9.4樹(3)(4)

留給讀者自行證明。(4)(5)

留給讀者自行證明。(5)(0)

設(shè)T的任何兩個頂點之間有且僅有一條通路，那么T顯然連通。T也是無回路的，否則T中有回路上頂點vi

，vj

，使vi到vj有兩條通路，與題設(shè)矛盾。定義9.21

如果T為G的生成子圖且T為樹，那么，稱T為無向圖G的生成樹。定理9.14

任一連通圖G都至少有一棵生成樹。證若G無回路，則G本身為一樹。若G有回路。則刪去回路上任一邊e，G–e仍連通。對G–e重復(fù)上述討論，直到得到G的無回路的連通子圖——生成樹。例9.179.4.2生成樹9.4樹e2e1e4e3e7e5e10e11e9e12e6e8e5e2e1e4e11e12e8e7e5e10e11e9e12e6定理9.15

設(shè)G為連通無向圖，那么G的任一回路與任一生成樹T的關(guān)于G的補(bǔ)G–T

，至少有一條公共邊。證設(shè)C為G的一回路，它和G的生成樹T關(guān)于G的補(bǔ)G–T

無公共邊，那么C是T的子圖，從而樹T中有回路，矛盾。定理9.16

設(shè)G為連通無向圖，那么G的任一割集與任一生成樹至少有一條公共邊。證設(shè)S為G的割集，但它和G的生成樹T無公共邊。那么，刪去G中所有S的邊后所得的圖仍以T為子圖，從而仍連通，這與S為割集矛盾。9.4.2生成樹9.4樹定義9.22

設(shè)T為圖G的生成樹，稱T中的邊為樹枝，稱G–T中的邊為

弦。對每一樹枝t，T–t分為兩個連通分支T1，T2，那么t及兩端點分別在T1，T2中的弦組成G的一個割集，它被稱為枝t-割集；而每一條弦e與T中的通路構(gòu)成一回路，它被稱為弦e-回路。

(n,m)圖G的任一生成樹T恒有n–1條邊，m–n+1條弦；從而有n–1個枝t-割集，m–n+1個弦e-回路(t指任一樹枝，e指任一弦)，分別稱為枝割集系和弦回路系。9.4.2生成樹9.4樹9.4.2生成樹9.4樹e2e1e4e3e7e5e10e11e9e12e6e8e7e5e10e11e9e12e6

例9.18

(1)共8–1=7枝。(2)e1,e2,e3,e4,e8為弦，共12–8+1=5條。生成樹：(3)枝e5-割集{e5,e1,e4,e8}

枝e6-割集{e6,e2,e4,e8}

枝e7-割集{e7,e3,e4,e8}

枝e9-割集{e9,e1,e4}

枝e10-割集{e10,e1,e2}

枝e11-割集{e11,e2,e3}

枝e12-割集{e12,e3,e4}(4)弦e1-回路是（e1,e9,e5,e10）弦e2-回路是（e2,e10,e6,e11）弦e3-回路是（e3,e11,e7,e12）弦e4-回路是（e4,e9,e5,e6,e7,e12）弦e8-回路是（e8,e5,e6,e7）定理9.17

在連通無向圖G中，任一回路與任一割集均有偶數(shù)條公共邊。證設(shè)C為G的任一回路，S為G的任一割集，從G中刪除S的所有邊后得到兩個互不連通的子圖G1，G2(如圖)。若回路C上的所有頂點都在G1(或G2)中，則C和S無公共邊，得證。若回路C的一部分頂點在G1中，另一部分在G2中，那么C必定經(jīng)過S中偶數(shù)條邊(因C為回路)，故C與S有偶數(shù)條公共邊。9.4.2生成樹9.4樹

定理9.18

設(shè)G為一連通無向圖，T是G的生成樹，

S={e1,e2,e3,…,ek}為枝e1-割集，那么e1必在弦ei-回路中(i=2，3,…，k)，不在其它弦e-回路中。（e1與弦ei-回路恰有兩條公共邊e1和ei，而e1與其它弦e-回路無公共邊。）證設(shè)C為任一弦ei-回路（i=2，3,…，k），例如C為弦e2-回路，則

e2在S與C中。又據(jù)定理9.17，C與S有偶數(shù)條公共邊。由于S中只有e1為樹枝，其余各邊均為弦；而C中只有e2為弦，其它各邊均為樹枝，所以只能還有e1在S與C中。即S與C恰有兩條公共邊e1

和e2，因此e1在弦e2-回路中。由于證明過程對一切ei（i=2，3,…，k）均成立，因此定理的前半部分得證。9.4.2生成樹9.4樹

定理9.18

設(shè)G為一連通無向圖，T是G的生成樹，

S={e1,e2,e3,…,ek}為枝e1-割集，那么e1必在弦ei-回路中(i=2，3,…，k)，不在其它弦e-回路中。（e1與弦ei-回路恰有兩條公共邊e1和ei，而e1與其它弦e-回路無公共邊。）證定理后半部分：設(shè)C為弦e-回路，而e≠e2,e3,…,ek。而C中只有e為弦，S中e2,e3,…,ek為弦，故eS。由于S中只有e1為樹枝，其余各邊均為弦；而C中只有e為弦，其它各