離散數(shù)學(xué)第6章

第六章圖論1圖論圖是一類非常廣泛的數(shù)學(xué)模型，在現(xiàn)實(shí)中的許多問(wèn)題，如電網(wǎng)絡(luò)問(wèn)題，交通網(wǎng)絡(luò)問(wèn)題，運(yùn)輸?shù)膬?yōu)化問(wèn)題，社會(huì)學(xué)中某類關(guān)系的研究，都可以用這類數(shù)學(xué)模型研究和處理。在計(jì)算機(jī)科學(xué)的許多領(lǐng)域中,如開關(guān)理論與邏輯設(shè)計(jì),人工智能,形式語(yǔ)言,計(jì)算機(jī)圖形,操作系統(tǒng),編譯程序,信息檢索等方面圖和圖的理論也有很多重要的應(yīng)用。26-1圖的基本概念無(wú)向圖與有向圖定義無(wú)向圖G=<V,E>,其中(1)V

為頂點(diǎn)集，元素稱為頂點(diǎn)(2)E為V

V的多重子集，其元素稱為無(wú)向邊，簡(jiǎn)稱邊.例如,G=<V,E>如圖所示,其中V={v1,v2,…,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}3無(wú)向圖與有向圖定義有向圖D=<V,E>,其中(1)V同無(wú)向圖的頂點(diǎn)集,元素也稱為頂點(diǎn)(2)E為V

V的多重子集，其元素稱為有向邊，簡(jiǎn)稱弧.用無(wú)向邊代替D的所有有向邊所得到的無(wú)向圖稱作D的基圖右圖是有向圖，試寫出它的V和E

4圖的基本概念邊又分為兩種：有向邊和無(wú)向邊。在有向邊的兩個(gè)端點(diǎn)中，一個(gè)是始點(diǎn)，另一個(gè)是終點(diǎn)，有向邊的箭頭方向自始點(diǎn)指向終點(diǎn)。如果圖中各邊都是有向邊，則稱此圖為有向圖。如果圖中各邊都是無(wú)向邊，則稱此圖為無(wú)向圖。如果圖中既有有向邊又有無(wú)向邊，則稱此圖為混合圖由于無(wú)向邊可以用兩條方向相反的有向邊來(lái)替代，所以混合圖可以轉(zhuǎn)化為有向圖。

5圖的基本概念

有向圖

無(wú)向圖

混合圖轉(zhuǎn)化為有向圖6無(wú)向圖與有向圖(續(xù))通常用G表示無(wú)向圖,D表示有向圖,也常用G泛指無(wú)向圖和有向圖,用ek表示無(wú)向邊或有向邊.V(G),E(G),V(D),E(D):G和D的頂點(diǎn)集,邊集.7頂點(diǎn)和邊的關(guān)聯(lián)與相鄰定義設(shè)ek=(vi,vj)是無(wú)向圖G=<V,E>的一條邊,稱vi,vj為ek的端點(diǎn),ek與vi(

vj)關(guān)聯(lián).

若vi

vj,則稱ek與vi(

vj)的關(guān)聯(lián)次數(shù)為1;

若vi=vj,則稱ek為環(huán),此時(shí)稱ek與vi的關(guān)聯(lián)次數(shù)為2;

若vi不是ek端點(diǎn),則稱ek與vi的關(guān)聯(lián)次數(shù)為0.

無(wú)邊關(guān)聯(lián)的頂點(diǎn)稱作孤立點(diǎn).8定義設(shè)無(wú)向圖G=<V,E>,邊e=(a,b)，則稱a,b為邊e的兩個(gè)端點(diǎn)，稱點(diǎn)a,b是鄰接的;關(guān)聯(lián)于同一頂點(diǎn)的邊是相鄰（鄰接）的.例如：若ek,el至少有一個(gè)公共端點(diǎn),則稱ek,el相鄰（鄰接）.對(duì)有向圖有類似定義.設(shè)ek=

vi,vj

是有向圖的一條邊,vi,vj是ek端點(diǎn),又稱vi是ek的始點(diǎn),vj是ek的終點(diǎn),vi鄰接到vj,vj鄰接于vi.9圖中結(jié)點(diǎn)的度數(shù)

bcadfe

無(wú)向圖中結(jié)點(diǎn)的次數(shù)定義：設(shè)圖G是無(wú)向圖，v是圖G中的頂點(diǎn)，與點(diǎn)v關(guān)聯(lián)的邊的條數(shù)(有環(huán)時(shí)，視為2)，稱為點(diǎn)v的度，記作deg(v)。10頂點(diǎn)的度數(shù)

設(shè)G=<V,E>為無(wú)向圖,v

V,

懸掛頂點(diǎn):度數(shù)為1的頂點(diǎn)

懸掛邊:與懸掛頂點(diǎn)關(guān)聯(lián)的邊

G的最大度

(G)=max{d(v)|v

V}

G的最小度

(G)=min{d(v)|v

V}

孤立點(diǎn)：度數(shù)為0的頂點(diǎn)例如d(v5)=3,d(v2)=4,d(v1)=4,

(G)=4,

(G)=1,

v4是懸掛頂點(diǎn),e7是懸掛邊,e1是環(huán)11無(wú)向圖中結(jié)點(diǎn)的度數(shù)定理

設(shè)圖G是具有n個(gè)點(diǎn)，m條邊的無(wú)向圖，其中頂點(diǎn)構(gòu)成的集合，則（握手定理）證明因?yàn)樵跓o(wú)向圖中，每一條邊使其所關(guān)聯(lián)的兩點(diǎn)各增加1度，由此得證。由定理可知，無(wú)向圖中各頂點(diǎn)的度數(shù)之和為偶數(shù)，由此易得下列推論。推論在無(wú)向圖中，度數(shù)為奇數(shù)的頂點(diǎn)個(gè)數(shù)為偶數(shù)。12有向圖頂點(diǎn)的度數(shù)設(shè)D=<V,E>為有向圖,v

V,v的出度d+(v):v作為邊的始點(diǎn)的次數(shù)之和

v的入度d

(v):v作為邊的終點(diǎn)的次數(shù)之和

v的度數(shù)(度)d(v):v作為邊的端點(diǎn)次數(shù)之和

d(v)=d+(v)+d-(v)D的最大出度

+(D),最小出度

+(D)

最大入度

(D),最小入度

(D)

最大度

(D),最小度

(D)例如d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,

+(D)=4,

+(D)=0,

(D)=3,

(D)=1,

(D)=5,

(D)=3.13有向圖頂點(diǎn)的度數(shù)定理8.2

設(shè)圖G是具有n個(gè)點(diǎn)，m條邊的有向圖，其中頂點(diǎn)構(gòu)成的集合，則

證明因?yàn)槊恳粭l有向邊為始點(diǎn)提供1個(gè)出度，為終點(diǎn)提供1個(gè)入度，而所有各頂點(diǎn)的出度之和及入度之和均由m條有向邊提供，所以定理成立．所有頂點(diǎn)入度之和等于出度之和等于邊數(shù).度為奇數(shù)的頂點(diǎn)個(gè)數(shù)必為偶數(shù).14思考題：設(shè)有向簡(jiǎn)單圖D的度數(shù)為2，2，3，3，入度列0，0，2，3，試求D的出度列。2，2，1，015練習(xí)：給出下列各圖各點(diǎn)的度數(shù)：acdb16圖的度數(shù)列

設(shè)無(wú)向圖G的頂點(diǎn)集V={v1,v2,…,vn}G的度數(shù)序列:d(v1),d(v2),…,d(vn)如右圖度數(shù)序列:4,4,2,1,3設(shè)有向圖D的頂點(diǎn)集V={v1,v2,…,vn}D的度數(shù)序列:d(v1),d(v2),…,d(vn)D的出度序列:d+(v1),d+(v2),…,d+(vn)D的入度序列:d

(v1),d

(v2),…,d

(vn)如右圖度數(shù)序列:5,3,3,3

出度序列:4,0,2,1

入度序列:1,3,1,217握手定理的應(yīng)用例1(3,3,3,4),(2,3,4,6,8)能成為圖的度數(shù)序列嗎?解不可能.它們都有奇數(shù)個(gè)奇數(shù).例2已知圖G有10條邊,4個(gè)3度頂點(diǎn),其余頂點(diǎn)的度數(shù)均小于等于2,問(wèn)G至少有多少個(gè)頂點(diǎn)?解設(shè)G有n個(gè)頂點(diǎn).由握手定理,43+2(n-4)210解得n818握手定理的應(yīng)用(續(xù))例3給定下列各序列,哪組可以構(gòu)成無(wú)向圖的度數(shù)序列(2,2,2,2,2)(1,1,2,2,3)(1,1,2,2,2)(1,3,4,4,5)√√19思考題下面無(wú)向圖中有幾個(gè)頂點(diǎn)？（1）16條邊，每個(gè)頂點(diǎn)都是2度頂點(diǎn).（2）21條邊，3個(gè)4度頂點(diǎn)，其余的都是3度頂點(diǎn).（3）35條邊，每個(gè)頂點(diǎn)的度數(shù)至少為3的圖最多有幾個(gè)頂點(diǎn)?16132320圖的同構(gòu)定義

設(shè)圖G的點(diǎn)集為V，邊集為E，圖的點(diǎn)集為，邊集為。如果存在著V到的雙射函數(shù)f，使對(duì)任意的u,v∈V,(u,v)∈E，當(dāng)且僅當(dāng)(f(u),f(v))∈，則稱圖G和G′同構(gòu)，記為：上述定義說(shuō)明：如果兩個(gè)圖的點(diǎn)和邊能建立一一對(duì)應(yīng)關(guān)系，且點(diǎn)和邊的關(guān)聯(lián)關(guān)系也能保持一一對(duì)應(yīng)關(guān)系，則這兩個(gè)圖是同構(gòu)的。21圖的同構(gòu)幾點(diǎn)說(shuō)明：圖之間的同構(gòu)關(guān)系具有自反性、對(duì)稱性和傳遞性.能找到多條同構(gòu)的必要條件,但它們都不是充分條件:①邊數(shù)相同，頂點(diǎn)數(shù)相同②度數(shù)列相同③對(duì)應(yīng)頂點(diǎn)的關(guān)聯(lián)集及鄰域的元素個(gè)數(shù)相同，等等若破壞必要條件，則兩圖不同構(gòu)22圖的同構(gòu)a-A, b-B, c-C, d-D觀察點(diǎn)a:(a,b),(a,c),(a,d)

觀察它對(duì)應(yīng)的映射點(diǎn)A：(A,B),(A,C),(A,D)其余的點(diǎn)都有這種點(diǎn)對(duì)點(diǎn)，邊對(duì)邊的映射關(guān)系。這兩個(gè)圖都表現(xiàn)出“圖中每一個(gè)頂點(diǎn)都與其他3個(gè)點(diǎn)鄰接”的結(jié)構(gòu)特點(diǎn)，稱這兩個(gè)圖是同構(gòu)的。dabcABCD23圖的同構(gòu)(續(xù))例1試畫出4階3條邊的非同構(gòu)的無(wú)向圖例2判斷下述每一對(duì)圖是否同構(gòu):(1)度數(shù)列不同不同構(gòu)24例2(續(xù))(2)不同構(gòu)入(出)度列不同(3)度數(shù)列相同但不同構(gòu)為什么?25圖的同構(gòu)

(a)(b)ABCAECFEDFBD(c)(d)

兩個(gè)同構(gòu)的圖，除了頂點(diǎn)所在的位置不同外，實(shí)際上代表了同樣的組合結(jié)構(gòu)。

26練習(xí)：1.確定下列各圖的出度、入度和度數(shù)。adbcabdc出：2,4,1,1入：2,3,2,1出：3,5,4,0入：3,1,2,627子圖

定義設(shè)G=<V,E>,G

=<V

,E

>是2個(gè)圖(1)若V

V且E

E,

則稱G

為G的子圖,G為G

的

母圖,記作G

G(2)若G

G且G

G（即V

V或E

E），稱G

為G的真子圖(3)若G

G且V

=V，則稱G

為G的生成子圖(4)設(shè)V

V且V,

以V

為頂點(diǎn)集,以兩端點(diǎn)都在

V

中的所有邊為邊集的G的子圖稱作V

的導(dǎo)出子圖，記作G[V

](5)設(shè)E

E且E,

以E

為邊集,以E

中邊關(guān)聯(lián)的所有頂點(diǎn)為頂點(diǎn)集的G的子圖稱作E

的導(dǎo)出子圖,記作G[E

]28常用的特殊子圖

真子圖生成子圖點(diǎn)集的導(dǎo)出子圖邊集的導(dǎo)出子圖

ccbdbaeae

ff(a)(b)cccbdbdbdaeeaef(c)(d)(e)

29圖的運(yùn)算1.刪除運(yùn)算刪邊：從G中刪去一邊的子圖，記為G-e刪點(diǎn)：從G中刪去一點(diǎn)及其關(guān)聯(lián)邊所得的子圖，記為G-vGG-eG-v30圖的運(yùn)算刪除邊集：從G中刪去邊集E的子集E’所得到的子圖，記為G-E’刪除點(diǎn)集：從G中刪去點(diǎn)集V的子集V’及它們的關(guān)聯(lián)邊所得的子圖，記為G-V’GG-E’G-V’31圖的運(yùn)算2.收縮運(yùn)算： 設(shè)圖G中邊e，它的端點(diǎn)為vi和vj，現(xiàn)刪去邊e，并把vi和vj合并為新的一點(diǎn)vi-j，使原來(lái)與vi或vj關(guān)聯(lián)的邊變?yōu)榕c新的點(diǎn)vi-j關(guān)聯(lián)，稱邊e被收縮。v1v2v3v4v5v1v2v3V4-5e32圖的運(yùn)算3.圖的并、交、環(huán)和設(shè)圖G1=(V1,E1),G2=(V2,E2)G1和G2的并：G1∪G2=(V1∪V2,E1∪E2)G1和G2的交：G1∩G2=(V1∩V2,E1∩E2)G1和G2的環(huán)和：G1G2=(V1∪V2,E1E2)33圖的運(yùn)算v1v2v4v6v5v3v7v4v5v8v3v2v1v2v7v4v6v5v8v3v2v3v4v5v1v2v7v4v6v5v8v3G1∪G2G1∩G2G1G234圖的運(yùn)算若V1∩V2=空集，說(shuō)明圖G1和G2沒有公共頂點(diǎn)，G1∩G2是空?qǐng)D。稱G1和G2不相交。若E1∩E2=空集，說(shuō)明圖G1和G2沒有公共邊，則G1G2=G1∪G2,G1∩G2是一個(gè)零圖(只有孤立點(diǎn)，沒有邊)35幾類特殊圖1.簡(jiǎn)單圖、多重圖與帶權(quán)圖(賦權(quán)圖)簡(jiǎn)單圖：不含有多重邊（平行邊）和環(huán)的圖多重圖：含平行邊的圖帶權(quán)圖：每條邊都附帶信息的圖.

8129101352542011

73賦權(quán)圖

36判斷下列圖是否為簡(jiǎn)單圖acdb簡(jiǎn)單圖簡(jiǎn)單圖多重圖37幾類特殊圖2.完全圖無(wú)向完全圖：

在n階無(wú)向圖中，如果任意兩個(gè)不同的頂點(diǎn)之間都有一條邊關(guān)聯(lián)，則稱此無(wú)向圖為無(wú)向完全圖，記為Kn。

有向完全圖：在n階有向圖中，如果任意兩點(diǎn)都有兩條方向相反的有向邊關(guān)聯(lián),則稱此有向圖為有向完全圖。38幾類特殊圖判斷下列各圖是否為完全圖K439完全圖無(wú)向完全圖：簡(jiǎn)單性質(zhì):邊數(shù)m=n(n-1)/2,

=

=n-1有向完全圖：簡(jiǎn)單性質(zhì):邊數(shù)m=n(n-1),

=

=2(n-1),

+=

+=

-=

-=n-140幾類特殊圖3.正側(cè)圖(正則圖)n階k正則圖:每個(gè)頂點(diǎn)度數(shù)都為k的無(wú)向簡(jiǎn)單圖。

=

=k

。簡(jiǎn)單性質(zhì):邊數(shù)m=nk/2Kn無(wú)向完全圖是n-1正則圖41幾類特殊圖4.二分圖定義：若圖G的頂點(diǎn)集能劃分為兩個(gè)子集V1,V2，使得每條邊都有一個(gè)端點(diǎn)在V1，另外一個(gè)端點(diǎn)在V2，那么圖G就能稱為二分圖，這種劃分(V1,V2)稱為圖G的一個(gè)二劃分。42路與回路1.邊序：在圖G中，邊組成一個(gè)有限序列(e1,e2,…em)，序列中，任意連接的兩邊相鄰或相同，此序列則稱為邊序。(e1,e2,e2,e3,e5)(e2,e3,e5,e7,e10)(e1,e2,e3,e6,e7)邊序邊序不是邊序邊序也可以使用端點(diǎn)表示，例如(e1,e2,e3)可以表示為：(v1,v2,v3,v4),這種邊序也稱為通道43路與回路邊序的長(zhǎng)度：邊序中邊的條數(shù)。兩個(gè)頂點(diǎn)間的距離：兩個(gè)頂點(diǎn)間長(zhǎng)度最短的邊序。跡：所有邊都不相同的邊序即為跡。例如：(e1,e2,e2,e3,e5)和(e1,e2,e3,e5)路：所有頂點(diǎn)都不相同的邊序即為路（通路）。(e4,e5,e6,e1,e10)->(v2,v4,v5,v2,v1,,v6)(e3,e5,e6,e1,e10)->(v3,v4,v5,v2,v1,,v6)跡路44路與回路在頂點(diǎn)序列中，將開始點(diǎn)記為v0，結(jié)束點(diǎn)記為vm。若v0=vm的跡，則稱此跡為閉跡，否則稱開跡。若v0=vm的路，則稱此跡為閉路，否則稱開路。至少包含一條邊的閉路稱為回路。以上討論的都是無(wú)向圖的情況，在有向圖中也是類似的45路與回路在圖G中，由弧組成的有限序列是弧序?；⌒虻拈_始點(diǎn)記為v0，結(jié)束點(diǎn)記為vm?；⌒蚩梢杂糜邢蜻呅蛄斜硎荆部梢杂庙旤c(diǎn)序列來(lái)表示。所有弧都不同的弧序即為有向跡，所有頂點(diǎn)都不同的弧序即為有向路。若v0=vm的有向跡，則稱為有向閉跡，否則稱有向開跡。若v0=vm的有向路，則稱為有向閉路，否則稱有向開路。46路與回路有向跡：(e9,e2,e3,e4,e1)有向路:(e3,e5,e7,e9)有向回路:(e2,e3,e5,e7,e9)不考慮有向圖的方向，將其看作無(wú)向圖時(shí)，可以找出路、回路。路：(e1,e4,e5,e7)回路：(e1,e6,e7,e10)47無(wú)向圖的連通性設(shè)無(wú)向圖G=<V,E>,定義設(shè)圖G是無(wú)向圖，u和v是圖G中的兩個(gè)頂點(diǎn)，如果u和v之間有通路相聯(lián)，則稱u，v是連通的，并規(guī)定u與自身是連通的。當(dāng)圖G中任意兩點(diǎn)都是連通的，則稱圖G為連通圖。48連通分支結(jié)點(diǎn)的連通性是等價(jià)關(guān)系。這個(gè)等價(jià)關(guān)系所對(duì)應(yīng)的劃分把圖G的結(jié)點(diǎn)集V分成若干個(gè)塊(即等價(jià)類)，其中每一個(gè)塊中的結(jié)點(diǎn)和G中以中的結(jié)點(diǎn)為端點(diǎn)的邊組成的G的子圖（即點(diǎn)集的導(dǎo)出子圖）稱為圖G的一個(gè)連通分支。G中連通分支個(gè)數(shù)記作P(G)連通圖G僅有一個(gè)連通分支(P(G)=1)，即圖G自身．49連通圖

連通圖不是連通圖

P(G)=1（含兩個(gè)連通分支，P(G)=2）圖1圖250【例１】設(shè)圖G是n階無(wú)向簡(jiǎn)單圖，且圖G中任意不同的兩個(gè)結(jié)點(diǎn)的度數(shù)之和大于等于n–1，證明圖G是連通圖。證明：假設(shè)圖G不是連通圖，則圖G是由多個(gè)連通分支構(gòu)成，不妨設(shè)有k個(gè)連通分支在連通分支中任取一點(diǎn)u

，在連通分支中任取一點(diǎn)v，

這和題設(shè)“圖G中任意不同的兩個(gè)結(jié)點(diǎn)的次數(shù)之和大于等于n–1矛盾，所以圖G是連通圖。512．有向圖的連通性定義：在有向圖中，如果存在著從結(jié)點(diǎn)到的通路，則稱從到是可達(dá)的。在有向圖中，如果從結(jié)點(diǎn)到是可達(dá)的，不一定表示它們間只有一條通路，也可能有若干條通路。從結(jié)點(diǎn)到間長(zhǎng)度最短的通路稱為短程線，而短程線的長(zhǎng)度稱為從結(jié)點(diǎn)到間的距離。522．有向圖的連通性有向圖的連通性分為強(qiáng)連通、單向連通和弱連通三種。強(qiáng)連通：如果有向圖G中任意兩結(jié)點(diǎn)，均是相互可達(dá)的，則稱此有向圖為強(qiáng)連通圖。單向連通：如果有向圖中任意兩結(jié)點(diǎn)，，至少存在一向是可達(dá)的，則稱此有向圖為單向連通圖。弱連通：如果忽略有向圖的邊的方向后其無(wú)向圖是連通的，則稱此有向圖為弱連通圖。強(qiáng)連通圖→單向連通圖→弱連通圖532．有向圖的連通性

強(qiáng)連通圖單向連通圖弱連通圖54強(qiáng)連通圖和單向連通圖的判別方法如果有向圖中存在一條通過(guò)圖中各個(gè)結(jié)點(diǎn)的回路，則此有向圖是強(qiáng)連通的。如果有向圖中存在一條通過(guò)圖中各個(gè)結(jié)點(diǎn)的通路，則此有向圖是單向連通的。55強(qiáng)連通分支1.互相可到達(dá)關(guān)系R對(duì)于有向圖D,u∈V,v∈V,u與v有關(guān)系R，當(dāng)且僅當(dāng)從u可以到達(dá)v，從v也可到達(dá)u?；ハ嗫傻竭_(dá)關(guān)系R是一個(gè)等價(jià)關(guān)系因此它對(duì)點(diǎn)集V進(jìn)行了劃分，可以將V劃分為非空的子集V1,V2,…Vw,使得兩個(gè)頂點(diǎn)如果互相可到達(dá)，則肯定位于同一子集中。56強(qiáng)連通分支根據(jù)互相可到達(dá)關(guān)系R，劃分出來(lái)的這若干個(gè)等價(jià)類V1,V2,…Vw

，由每個(gè)等價(jià)類Vi,導(dǎo)出對(duì)應(yīng)的子圖，就是一個(gè)強(qiáng)連通分支。57點(diǎn)割集定義：設(shè)無(wú)向圖G=<V,E>.若存在V’?V使得p(G-V’)>p(G),且對(duì)于任意的V’’?V’,均有p(G-V’’)=p(G),則稱V’是G的點(diǎn)割集。若V’={v},則稱v為割點(diǎn)。{v5}{v2,v4}{v3}{v1,v2}是否為點(diǎn)割集？YesYesYesNo割點(diǎn)？58邊割集定義：設(shè)無(wú)向圖G=<V,E>.若存在E’?E使得p(G-E’)>p(G),且對(duì)于任意的E’’?E’,均有p(G-E’’)=p(G),則稱E’是G的邊割集。若E’={e},則稱v為割邊或橋。{e5}{e2,e3}{e6}{e4}是否為邊割集？YesYesYesNo橋？59思考題：求出下圖的全部割點(diǎn)和橋60§6-2樹樹及其性質(zhì)：無(wú)向樹與外向樹1.無(wú)向樹：定義

設(shè)T是無(wú)向簡(jiǎn)單連通圖且T中不存在任何回路，則稱T為無(wú)向樹，或簡(jiǎn)稱為樹。在樹中，次數(shù)為1的結(jié)點(diǎn)稱為樹葉，次數(shù)大于1的結(jié)點(diǎn)稱為內(nèi)結(jié)點(diǎn)或分枝結(jié)點(diǎn)。森林:每個(gè)連通分支都是樹的非連通的無(wú)向圖61樹（a)

adadadcfefefbcbcc(b)(c)62樹的基本性質(zhì)性質(zhì)1

若樹有n個(gè)結(jié)點(diǎn)，m條邊，則

m=n–1性質(zhì)2

樹中任意兩點(diǎn)有且僅有一條通路相連性質(zhì)3

在樹中任意刪去一條邊，則變成不連通圖。性質(zhì)4

在樹中任意兩個(gè)不鄰接的頂點(diǎn)中添加一條邊，則構(gòu)成的圖包含惟一的回路。63性質(zhì)5

具有兩個(gè)結(jié)點(diǎn)以上的樹T至少有兩片樹葉。樹的基本性質(zhì)證明:因?yàn)闃銽=(n，m)是連通的，所以T中每個(gè)結(jié)點(diǎn)的次數(shù)都大于等于1，上式經(jīng)過(guò)整理得，說(shuō)明T至少有兩片樹葉。設(shè)T有k片樹葉，則有n-k個(gè)結(jié)點(diǎn)的次數(shù)大于等于2。從而有64例：設(shè)一棵樹T有2個(gè)度數(shù)為2的結(jié)點(diǎn)，1個(gè)度數(shù)為3的結(jié)點(diǎn)，3個(gè)度數(shù)為4的結(jié)點(diǎn)，求T有幾片樹葉。解：設(shè)T有x片樹葉，則T的邊數(shù)為6+x–1=5+x。2×2+1×3+3×4+x=2（5+x）結(jié)點(diǎn)數(shù)為2+1+3+x=6+x，根據(jù)握手定理，知19+x=10+2xx=19–10=9所以T有9片樹葉。65例題例2已知無(wú)向樹T有5片樹葉,2度與3度頂點(diǎn)各1個(gè),其余頂點(diǎn)的度數(shù)均為4.求T的階數(shù)n,解設(shè)T的階數(shù)為n,則邊數(shù)為n

1,4度頂點(diǎn)的個(gè)數(shù)為n

7.由握手定理得

2m=2(n

1)=5

1+2

1+3

1+4(n

7)解出n=8,4度頂點(diǎn)為1個(gè).T的度數(shù)列為1,1,1,1,1,2,3,4

有3棵非同構(gòu)的無(wú)向樹66生成樹

設(shè)G為無(wú)向連通圖G的生成樹:G的生成子圖并且是樹(生成樹的頂點(diǎn)集必須等于圖G的頂點(diǎn)集)生成樹T的樹枝:G在T中的邊生成樹T的弦:G不在T中的邊生成樹T的余樹:所有弦的集合的導(dǎo)出子圖注意：不一定連通,也不一定不含回路.右圖黑邊構(gòu)成生成樹紅邊構(gòu)成余樹67生成樹的存在性

定理

任何無(wú)向連通圖都有生成樹.證用破圈法.若圖中無(wú)圈,則圖本身就是自己的生成樹.

否則刪去圈上的任一條邊,這不破壞連通性,重復(fù)進(jìn)行直到無(wú)圈為止,剩下的圖是一棵生成樹.推論1

設(shè)n階無(wú)向連通圖有m條邊,則生成樹有n-1條枝.推論2

設(shè)n階無(wú)向連通圖有m條邊,則它的生成樹的余樹有m

n+1條邊.推論3

設(shè)為G的生成樹T的余樹，C為G中任意一個(gè)圈，則C與一定有公共邊.

68外向樹(根樹)定義

如果有且僅有一個(gè)結(jié)點(diǎn)的入度為0點(diǎn)，其他結(jié)點(diǎn)的入度均為1，則稱樹T為外向樹（根樹）。 入度為0的結(jié)點(diǎn)稱為T的根。所有出度為0的結(jié)點(diǎn)稱為T的樹葉或葉片，出度不為0的結(jié)點(diǎn)稱為分枝結(jié)點(diǎn)或內(nèi)結(jié)點(diǎn)。邊有方向性692.外向樹

aabcbcdefghdefghijij(a)(b)

70有關(guān)概念樹根:外向樹中入度為0的頂點(diǎn)樹葉:外向樹中入度為1,出度為0的頂點(diǎn)內(nèi)點(diǎn):外向樹中入度為1,出度大于0的頂點(diǎn)分支點(diǎn):樹根與內(nèi)點(diǎn)的總稱頂點(diǎn)v的層數(shù):從樹根到v的通路長(zhǎng)度樹高:外向樹中頂點(diǎn)的最大層數(shù)71根樹根樹的畫法:樹根放上方,省去所有有向邊上的箭頭如右圖所示

a是樹根

b,e,f,h,i是樹葉

c,d,g是內(nèi)點(diǎn)

a,c,d,g是分支點(diǎn)

a為0層;1層有b,c;2層有d,e,f;3層有g(shù),h;4層有i.

樹高為472家族樹定義把根樹看作一棵家族樹:(1)若頂點(diǎn)a鄰接到頂點(diǎn)b,則稱b是a的兒子,a是

b的父親;(2)若b和c為同一個(gè)頂點(diǎn)的兒子,則稱b和c是兄弟;(3)若a

b且a可達(dá)b,則稱a是b的祖先,b是a的后代.(4)在外向樹T中取某一結(jié)點(diǎn)a，由a以及a的所有子孫導(dǎo)出的子圖稱為外向樹T的子樹。73家族樹圖中，a是b,c的父親，d是g,h的父親。b,c是兄弟。c是d,g,i的祖先，d,g,i

是c的后代。子樹74有序樹

123123123

123123121212(a)(b)

圖1圖2定義

在根樹中，如果每一個(gè)結(jié)點(diǎn)的兒子都規(guī)定次序（一般采用自左至右），則稱此樹為有序樹。

如果兩棵樹是同構(gòu)的，但點(diǎn)的次序不同，則看做是兩個(gè)不同的有序樹。75二元樹

圖(a)

4元樹圖(b)完全3元樹定義

設(shè)T是根樹，如果T中各個(gè)分枝點(diǎn)的兒子數(shù)量最多為m，則稱外向樹T為m元樹(m叉樹)。定義

在有根樹中，如果每一個(gè)分枝點(diǎn)的兒子數(shù)都是

m，則稱此外向樹為m元完全樹(m叉完全樹)。(當(dāng)m=2時(shí)，分別稱為二元樹和二元完全樹)76二叉樹(最多有兩個(gè)兒子)

二叉樹是計(jì)算機(jī)技術(shù)中使用最廣泛的一類樹。在二叉樹中，常把分枝點(diǎn)的兩個(gè)兒子分別畫在分枝點(diǎn)的左下方和右下方，并分別稱為左兒子和右兒子。當(dāng)分枝點(diǎn)只有一個(gè)兒子時(shí)，將兒子畫在左下方或右下方也被認(rèn)為是不同的。77左子樹右子樹

a

bcbcdefgdefghijhij(a)(b)(c)

a的左子樹

a的右子樹78思考題：圖中的根樹中：是幾叉樹？樹高？幾個(gè)內(nèi)點(diǎn)？幾個(gè)分支點(diǎn)？445679思考題：圖存在是根樹的生成子圖嗎？共有3棵非同構(gòu)的80例:用二元樹表示算術(shù)表達(dá)式(a+b)×c-d/eabcde-×+/特點(diǎn)：

操作數(shù)為葉子結(jié)點(diǎn)

運(yùn)算符為分支結(jié)點(diǎn)81完全二叉樹和滿二叉樹不含(出)度數(shù)為1的二叉樹就是完全二叉數(shù)。只含(出)度數(shù)為0，或2的結(jié)點(diǎn)，且度數(shù)為0的結(jié)點(diǎn)只出現(xiàn)在最后一層的二叉樹就是滿二叉數(shù)M元樹中：所講度數(shù)為：出度82完全二叉樹和滿二叉樹圖1圖283遍歷算法遍訪2元有序樹的每一個(gè)頂點(diǎn)的算法有3種：前序、中序、后序遍歷算法。1．前序遍歷算法設(shè)需要遍歷的2元樹為T，其左子樹為，右子樹為，則前序遍歷算法的遞歸定義為（1）處理T的根；（2）處理左子樹，在處理左子樹時(shí)，用前序周游算法；（3）處理右子樹，在處理左子樹時(shí)，用前序周游算法。根→左子樹→右子樹84前序遍歷算法

a

bcbcdefgdefghijhij(a)(b)(c)

用前序算法，2元樹T中各頂點(diǎn)的訪問(wèn)順序?yàn)?/p>

a→b→d→e→h→c→f→g→i→j852．中序遍歷算法其遞歸定義如下：（1）處理T的左子樹，在處理左子樹時(shí)，用中序遍歷算法；（2）處理T的根；（3）處理T的右子樹，在處理右子樹時(shí)，用中序遍歷算法。左子樹→根→右子樹86中序遍歷算法

a

bcbc

defgdefghijhij(a)(b)(c)

由中序算法可知，T中各個(gè)頂點(diǎn)的訪問(wèn)順序?yàn)閐→b→h→e→a→f→c→i→g→j873．后序遍歷算法其遞歸定義如下：（1）處理T的左子樹，在處理左子樹時(shí)，用后序遍歷算法；（2）處理T的右子樹，在處理右子樹時(shí)，用后序遍歷算法；（3）處理T的根。左子樹→右子樹→根88后序遍歷算法

abcbcdefgdefghijhij(a)(b)(c)

由后序算法可知，T中各個(gè)頂點(diǎn)的訪問(wèn)順序?yàn)?/p>

d→h→e→b→f→i→j→g→c→a89層序遍歷算法其定義如下：逐層從上至下遍歷，從左向右遍歷。90層序遍歷算法

abcdefghij(a)

T中各個(gè)頂點(diǎn)的訪問(wèn)順序?yàn)?/p>

a→b→c→d→e→f→g→h→i→j91樹的遍歷前序：abdheIjcfklmg中序：hdbIejalkmfcg后序：hdIjeblmkfgca92M叉樹與二叉樹之間的轉(zhuǎn)換與普通的m叉樹相比，二叉樹的表示與計(jì)算都比較簡(jiǎn)單。如果能夠?qū)叉樹轉(zhuǎn)化為二叉樹，二叉樹又能還原為m叉樹，則我們只需轉(zhuǎn)而研究二叉樹的處理即可。93M叉樹與二叉樹之間的轉(zhuǎn)換M叉樹轉(zhuǎn)換為二叉樹：方法：對(duì)每個(gè)樹結(jié)點(diǎn)，他的第1個(gè)兒子作為他在二叉樹中的左兒子，第2個(gè)兒子作為第1個(gè)兒子的右兒子，第3個(gè)兒子作為第2個(gè)兒子的右兒子，依次類推。94把m元有序樹轉(zhuǎn)化為二元有序樹的方法

12345678910(a)12637458910(b)

95M叉樹與二叉樹之間的轉(zhuǎn)換二叉樹轉(zhuǎn)換為M叉樹：方法：對(duì)任一個(gè)二叉樹結(jié)點(diǎn)，他的左兒子作為第1個(gè)兒子，將左兒子的右分枝上各結(jié)點(diǎn)依次作為他的第2，3…個(gè)兒子。96把m元有序樹轉(zhuǎn)化為二元有序樹的方法

12345678910(a)12637458910(b)

97練習(xí)：將下列樹轉(zhuǎn)換為2叉樹98練習(xí)：將下列2叉樹轉(zhuǎn)換為樹99“前綴式”波蘭表示法在算術(shù)表達(dá)式中，乘方是最優(yōu)先的運(yùn)算，其次是乘和除，最后是加和減。但圓括號(hào)可以改變運(yùn)算的優(yōu)先規(guī)則，從而給計(jì)算機(jī)處理帶來(lái)很大的不便。波蘭數(shù)學(xué)家魯加實(shí)維支提出了算術(shù)表達(dá)式的“前綴式”表示（常稱為波蘭表示法），即。例如a+b寫成+ab，a–b寫–ab，a×b寫成×ab，a/b寫成/ab等．100“前綴式”波蘭表示法例如，(a+b)c用波蘭表示法可寫成

×+abc。又如，(a+3b)c–4d，用波蘭表示法可寫成

–×+a×3bc×4d。若把運(yùn)算符寫在運(yùn)算對(duì)象的后面稱之為“后綴式”表示（例如a+b寫成ab+，a×b寫成ab×）。這種記法也稱為：逆波蘭表達(dá)式。101【例5.11】寫出下列算術(shù)表達(dá)式的“前綴式”波蘭表示。

((a–4b)c–(7d+b))/(c+5a)解其波蘭表示為

利用2元樹的前序遍歷算法能方便地得到算術(shù)表達(dá)式的波蘭表示。用2元樹來(lái)表示算術(shù)表達(dá)式的方法：把樹中的分枝點(diǎn)表示運(yùn)算符，葉片表示運(yùn)算對(duì)象。4b×a-c×7d×b+-c5a×+/102例5.11中算術(shù)表達(dá)式的波蘭表示

((a–4b)c–(7d+b))/(c+5a)例5.11對(duì)應(yīng)的2元樹經(jīng)前序遍歷算法后，即得

/–×–a×4bc+×7db+c×5a103練習(xí)：試將下列算術(shù)式轉(zhuǎn)化為波蘭表達(dá)式，并畫出對(duì)應(yīng)的二叉樹：1.((x+y)/2)+((x-4)×3)2.試根據(jù)下列波蘭式計(jì)算出式子的值1.－×2/8432.↑－×33×4253.+－↑32↑23/6－424.×+3+3↑3+333104答案：1((x+y)/2)+((x-4)×3)+/+xy2×-43第2題答案：105【例5.11】寫出下列算術(shù)表達(dá)式的“后綴式”波蘭表示(逆波蘭表達(dá)式)。

((a–4b)c–(7d+b))/(c+5a)解其逆波蘭表達(dá)式為

a4b×–

c×7d×b+–

c5a×+/

逆波蘭表達(dá)式可以通過(guò)樹的后序遍歷來(lái)獲得。106例5.11中算術(shù)表達(dá)式的逆波蘭表示

((a–4b)c–(7d+b))/(c+5a)

例5.11對(duì)應(yīng)的2元樹經(jīng)后序遍歷算法后，即得

a4b×–

c×7d×b+–

c5a×+/

107練習(xí)：試將下列算術(shù)式轉(zhuǎn)化為逆波蘭表達(dá)式：1.(2+a)3×(y-(3+a))-52.試根據(jù)下列逆波蘭式計(jì)算出式子的值1.521－－314++×2.93/5+72－×3.32×2↑53－84/×－108二叉排序樹二叉排序樹是一類特殊的二叉樹。二叉排序樹的結(jié)點(diǎn)，按照結(jié)點(diǎn)中關(guān)鍵字的次序進(jìn)行排列。是一種結(jié)點(diǎn)內(nèi)容受限的二叉樹。109二叉排序樹定義：1.每個(gè)結(jié)點(diǎn)表示一個(gè)關(guān)鍵字2.二叉排序樹或者為空，或者滿足下列情況：1)若左子樹不空，則左子樹上所有結(jié)點(diǎn)關(guān)鍵字均分別小于它的根結(jié)點(diǎn)關(guān)鍵字。2)右子樹不空，則右子樹上所有結(jié)點(diǎn)關(guān)鍵字均分別大于它的根結(jié)點(diǎn)關(guān)鍵字。3)左右子樹也分別是二叉排序樹110二叉排序樹例如圖所示，就是一棵二叉排序樹。111例：把下面的單詞構(gòu)造出二叉排序樹。mathematics,physics,geography,zoology,meteorology,geology,psychology,chemistry.112mathematics,physics,geography,zoology,meteorology,geology,psychology,chemistry.

1211334mathematics,physics,geography,zoology,meteorology,geology,psychology,chemistry.11456mathematics,physics,geography,zoology,meteorology,geology,psychology,chemistry.

115mathematics,physics,geography,zoology,meteorology,geology,psychology,chemistry.

116最優(yōu)樹定義

設(shè)T是具有n片樹葉的完全2元樹，且各片樹葉所含的權(quán)為令其中是完全2元樹T的根到樹葉的通路長(zhǎng)度，則稱W(T)為完全2元樹T的權(quán)。當(dāng)樹葉的權(quán)確定后，權(quán)最小的樹稱為最優(yōu)樹。由此可見，對(duì)于英文字母的最佳編碼問(wèn)題就是求最優(yōu)樹的問(wèn)題。117求最優(yōu)樹的算法－霍夫曼算法霍夫曼（Huffman)算法的基本思想是：從一棵樹葉權(quán)為的最優(yōu)樹可得到一棵樹葉權(quán)為的最優(yōu)樹

。因此，求一個(gè)有n片樹葉的最優(yōu)樹可轉(zhuǎn)化為求有n–1片樹葉的最優(yōu)樹，求一個(gè)有n–1片樹葉的最優(yōu)樹又可轉(zhuǎn)化為求有n–2片樹葉的最優(yōu)樹，…，依次類推，最后可轉(zhuǎn)化為求有兩片樹葉的最優(yōu)樹。由于僅有兩片樹葉的完全2元樹是惟一的，所以它一定是最優(yōu)樹。

118Huffman算法：給定實(shí)數(shù)且（1）連接為權(quán)的兩片樹葉，得一分支點(diǎn)，其權(quán)為；（2）在中選出兩個(gè)最小的權(quán)，連接它們對(duì)應(yīng)的頂點(diǎn)（不一定都是樹葉），得分支點(diǎn)及所帶的權(quán)；（3）重復(fù)（2），直到形成t–1個(gè)分支點(diǎn)，t片樹葉為止。119【例】求樹葉權(quán)為4，2，3，5，1的最優(yōu)樹。

6333123.4.5.124.5.(a)(b)6969334533451212(c)(d)

圖5.3.18120例：6個(gè)英文字母的編碼問(wèn)題，其最優(yōu)樹如圖5.3.23(e)所示。

260110110150c50601502002403005060200240300abcdefabdef(a)(b)

圖5.3.23121例：6個(gè)英文字母的編碼問(wèn)題，其最優(yōu)樹如圖5.3.23(e)所示。

01260440560440

0101110150200240260300200240cdefdefde110150603001500cabfc01506