《離散數(shù)學(xué)》課件第9章

9.1無向樹9.2根樹及其應(yīng)用9.3例題詳解習(xí)題九第四篇圖論基礎(chǔ)

定義9.1.1

連通無回路的無向圖稱為無向樹，簡稱樹，記作T。樹中的懸掛點稱為樹葉，其余頂點稱為分支點。每個連通分支均為樹的分離圖，稱為森林。平凡圖稱為平凡樹。

【例9.1.1】

圖9.1.1中(a)、(b)均是樹，圖(c)是森林。9.1無向樹圖9.1.1樹和森林由于樹無環(huán)且無重邊(否則有回路)，所以樹必是簡單圖。下面我們來討論樹的性質(zhì)。

定理9.1.1

無向圖T是樹，當(dāng)且僅當(dāng)以下五條之一成立。

(1)T中無回路且m=n-1，其中m為邊數(shù)，n為頂點數(shù)。

(2)T是連通圖且m=n-1。

(3)T中無回路，但增一條邊，則得到一條且僅一條初級回路。

(4)T連通且每條邊均是橋。

(5)T是簡單圖且每對頂點間有唯一的一條初級通路。

證明

①由樹的定義可得(1)。

施歸納于頂點數(shù)n。當(dāng)n=1時，m=0，則m=n-1成立。

假設(shè)當(dāng)n=k時，m=n-1成立。則當(dāng)n=k+1時，因為樹是連通的且無回路，所以至少有一個度數(shù)為1的頂點v，從樹中刪去v和與它關(guān)聯(lián)的邊，則得到k個頂點的樹T′。根

據(jù)假設(shè)它有k-1條邊，現(xiàn)將v和與它關(guān)聯(lián)的邊加到T′上還原成樹T，則T有k+1個頂點，k條邊，邊數(shù)比頂點數(shù)少1，故m=n-1成立。②由(1)可得(2)。

采用反證法，若圖T不連通，設(shè)T有k個連通分支T1，T2，…，Tk(k≥2)，其頂點數(shù)分別為n1，n2，…，nk，則有

ni=n

邊數(shù)分別為m1，m2，…，mk，則有

mi=m

因此，有

m=

mi=

(ni-1)=n-k＜n-1即m＜n-1，這與m=n-1矛盾，故T是連通的m=n-1圖。

③由(2)可得(3)。

若T是連通圖并有n-1條邊，施歸納于頂點數(shù)n。

當(dāng)n=2時，m=n-1=1，所以沒有回路，如果增加一條邊，只能得到唯一的一個回路。

假設(shè)n=k時，命題成立。則當(dāng)n=k+1時，因為T是連通的并有n-1條邊，所以每個頂點都有d(v)≥1，并且至少有一個頂點v0，滿足d(v0)=1。否則，如果每個頂點v都有d(v)≥2，那么必然會有總度數(shù)2m≥2n，即m≥n，這與條件m=n-1矛盾。因此至少有一個頂點v0，滿足d(v0)=1。刪去v0及其關(guān)聯(lián)的邊，得到圖T′，由假設(shè)知T′無回路，現(xiàn)將v0及其關(guān)聯(lián)的邊再加到T′，則還原成T，所以T沒有回路。

如果在連通圖T中增加一條新邊(vi，vj)，則(vi，vj)與T中從vi

到vj

的一條初級路徑構(gòu)成一個初級回路，且該回路必定是唯一的，否則當(dāng)刪去新邊(vi，vj)時，T中必有回路，產(chǎn)生矛盾。

④由(3)可得(4)。

若圖T不連通，則存在兩個頂點vi和vj

，在vi，vj

之間沒有路徑，如果增加邊(vi，vj)，不產(chǎn)生回路，這與(3)矛盾，因此T連通。

因為T中無回路，所以刪去任意一條邊，圖必不連通。故圖中每一條邊均是橋。⑤由(4)可得(5)。

由圖的連通性可知，任意兩個頂點之間都有一條通路，是初級通路。如果這條初級通路不唯一，則T中必有回路，刪去回路上的任意一條邊，圖仍連通，與(4)矛盾。故任意兩個頂點之間有唯一一條初級回路。

⑥由(5)可得樹的定義。

每對頂點之間有唯一一條初級通路，那么T必連通，若有回路，則回路上任意兩個頂點之間有兩條初級通路，與(5)矛盾。故圖連通且無回路，是樹。

證畢

定理9.1.2

任何一棵非平凡樹T至少有兩片樹葉。

證明設(shè)T是(n，m)圖，n≥2，有k片樹葉，其余頂點度數(shù)均大于或等于2，則

d(vi)≥2(n-k)+k=2n-k

而

d(vi)=2m=2(n-1)=2n-2

所以2n-2≥2n-k，即k≥2。證畢

【例9.1.2】

T是一棵樹,有兩個頂點度數(shù)為2，一個頂點度數(shù)為3，三個頂點度數(shù)為4，T有幾片樹葉？

解設(shè)樹T有x片樹葉，則T的頂點數(shù)

n=2+1+3+x

T的邊數(shù)

m=n-1=5+x

又由握手定理

2m=

d(vi)

得

2·(5+x)=2·2+3·1+4·3+x

所以x=9，即樹T有9片樹葉。請讀者自己畫出兩棵具有上述度數(shù)列的非同構(gòu)的樹。

解設(shè)Ti是7階無向樹。因為n=7，所以m=6；又因為2m=

d(vi),所以7個頂點分配12度，且由樹是連通簡單圖知1≤d(v)≤6。則Ti的度數(shù)列必是下列情況之一。

(1)1，1，2，2，2，2，2

(2)1，1，1，2，2，2，3

(3)1，1，1，1，2.2，4

(4)1，1，1，1，2，3，3

(5)1，1，1，1，1，2，5

(6)1，1，1，1，1，3，4

(7)1，1，1，1，1，1，6

注意到，不同構(gòu)的度數(shù)列對應(yīng)不同的樹，但對應(yīng)同一度數(shù)列的非同構(gòu)的樹不一定唯一，所以對應(yīng)(1)有T1，對應(yīng)(2)有T2、T3和T4，對應(yīng)(3)有T5和T6，對應(yīng)(4)有T7和T8，對應(yīng)(5)有T9，對應(yīng)(6)有T10，對應(yīng)(7)有T11(見圖9.1.2)。圖9.1.2不同構(gòu)的七階無向樹

生成樹

有一些圖，本身不是樹，但它的某些子圖卻是樹，其中很重要的一類是生成樹。

定義9.1.2

若無向圖G的一個生成子圖T是樹，則稱T是G的一棵生成樹。

如果T是G的一棵生成樹，則稱G在T中的邊為T的樹枝，G不在T中的邊為T的弦，T的所有弦的集合的導(dǎo)出子圖稱為T的余樹。易知，余樹不一定是樹，更不一定是生成樹。

例如圖9.1.3中，T1和T2是圖G的兩棵生成樹，1和2是分別對應(yīng)于它們的余樹。圖9.1.3圖的生成樹和余樹由圖9.1.3可見，G與T1、T2的區(qū)別是G中有回路，而它的生成樹中無回路，因此要在一個連通圖G中找到一棵生成樹，只要不斷地從G的回路上刪去一條邊，最后所得無回路的子圖就是G的一棵生成樹。于是有如下定理。

定理9.1.3

無向圖G有生成樹的充分必要條件是G為連通圖。

證明必要性，反證法。

若G不連通，則它的任何生成子圖也不連通，因此不可能有生成樹，與G有生成樹矛盾，故G是連通圖。

充分性。

設(shè)G連通，則G必有連通的生成子圖，令T是G的含有邊數(shù)最少的連通的生成子圖，于是T中必?zé)o回路(否則刪去回路上的一條邊不影響連通性，與T含邊數(shù)最少矛盾)，故T是一棵樹，即生成樹。證畢

推論1

設(shè)G是(n，m)無向連通圖，則m≥n-1。

推論2

設(shè)G是(n，m)無向連通圖，T是G的一棵生成樹，則T的余樹中含m-n+1條邊。

推論3

設(shè)T是連通圖G的一棵生成樹，為T的余樹，C為G中任意一個圈，則E(

)∩E(C)≠。

證明若E(

)∩E(C)=，則E(C)E(T)，說明C是T中的一個圈，與T為樹矛盾。證畢一般情況，圖G的生成樹不是唯一的，這里的不唯一有兩個含義，一種是標(biāo)定圖的生成樹所含的樹枝不同，另一種是不考慮標(biāo)定的生成樹是不同構(gòu)的。但無論怎樣，一個連通的(n，m)圖，其任意一棵生成樹的樹枝數(shù)一定是n-1，從而弦數(shù)也是固定不變的m-n+1。

由樹的性質(zhì)可知，對于圖G的一棵生成樹T，每增加一條弦，便得到一條初級回路。

例如，在圖9.1.3所示的T1中：

加弦e5，得初級回路e2e3e5；

加弦e4，得初級回路e1e3e4；

加弦e9，得初級回路e6e8e9；

加弦e10，得初級回路e7e8e10。

同樣，在圖9.1.3所示的T2中，分別加弦e3，e5，e8，e10，則分別產(chǎn)生初級回路e1e3e4，e1e4e5e2，e6e8e9，e7e6e9e10。這些初級回路有一個共同特點：它們中均只含一條弦，其余的邊均是樹枝，我們稱這樣的回路為基本回路。對于G的每棵生成樹T，m-n+1條弦對應(yīng)著m-n+1個基本回路，這些基本回路構(gòu)成的集合稱為對應(yīng)T的基本回路系統(tǒng)。顯然不同的生成樹對應(yīng)不同的基本回路系統(tǒng)。如圖9.1.3中，G對應(yīng)T1的基本回路系統(tǒng)為{e2e3e5，e1e3e4，e6e8e9，e7e8e10}，G對應(yīng)T2的基本回路系統(tǒng)為{e1e3e4，e1e4e5e2，e6e8e9，e7e6e9e10}。但是它們所含的元素個數(shù)均是m-n+1=4。在電路網(wǎng)絡(luò)分析中，基本回路具有重要意義。另一方面，從樹T中刪去一邊，便將T分成兩棵樹，即兩個連通分支，圖G中連接這兩個連通分支的邊的集合，稱為對應(yīng)于這條邊的基本(邊)割集。

例如在圖9.1.3中的G和T1：

對應(yīng)樹枝e1，有基本割集{e1，e4}；

對應(yīng)樹枝e2，有基本割集{e2，e5}；

對應(yīng)樹枝e3，有基本割集{e3，e4，

e5}；

對應(yīng)樹枝e6，有基本割集{e6，e9}；

對應(yīng)樹枝e7，有基本割集{e7，e10}；

對應(yīng)樹枝e8，有基本割集{e8，e9，e10}。同樣對于圖9.1.3中的G和T2，對應(yīng)樹枝e1，e2，e4，e6，e7，e9，分別有基本割集：{e1，e3，e5}，{e2，e5}，{e4，

e3，e5}，{e6，e8，e10}，{e7，e10}，{e9，e8,e10}。

這些割集所具有的共同特點是：每個割集中均只含生成樹的一個樹枝，其余的均是弦。對于圖G的任何一棵生成樹T，對應(yīng)每個樹枝的基本割集所構(gòu)成的集合，稱為對應(yīng)T的基本割集系統(tǒng)。如圖9.1.3中，G對應(yīng)T2的基本割集系統(tǒng)為{{e1，e3，e5}，{e2，e5}，{e4，e3，e5}，{e6，e8，e10}，{e7，e10}，{e9，e8,e10}}，顯然不同的生成樹有不同的基本割集系統(tǒng)，但其元素個數(shù)均為n-1。

最小生成樹

帶權(quán)圖的生成樹是實際應(yīng)用較多的樹，所謂權(quán)就是附加在圖上的信息，通常是實數(shù)，權(quán)加在邊上的稱邊權(quán)圖，加在點上的稱點權(quán)圖，這里我們只涉及邊權(quán)圖。

定義9.1.3

對圖G的每條邊附加上一個實數(shù)ω(e)，稱ω(e)為邊e上的權(quán)，G連同附加在各邊上的權(quán)稱為帶權(quán)圖，常記作G=〈V,E,ω〉。設(shè)G1是G的任意子圖，稱

ω(e)為G1的權(quán)，記作ω(G1)。一個很實際的問題是：假設(shè)你是一個設(shè)計師，欲架設(shè)連接n個村鎮(zhèn)的電話線，每個村鎮(zhèn)設(shè)一個交換站。已知由i村到j(luò)村的線路e=(vi，vj)造價為ω(e)=wij，要保證任意兩個村鎮(zhèn)之間均可通話，請設(shè)計一個方案，使總造價最低。

這個問題的數(shù)學(xué)模型為：在已知的帶權(quán)圖上求權(quán)最小的生成樹。

定義9.1.4

設(shè)無向連通帶權(quán)圖G=〈V,E,ω〉，G中帶權(quán)最小的生成樹稱為G的最小生成樹(最優(yōu)樹)。

定理9.1.4

設(shè)連通圖G的各邊的權(quán)均不相同，則回路中權(quán)最大的邊必不在G的最小生成樹中。

證明略。定理的結(jié)論是顯然的，由此尋找?guī)?quán)圖G的最小生成樹，可以采用破圈法，即在圖G中不斷去掉回路中權(quán)最大的邊。

求最小生成樹的另一個更有效率的算法是克魯斯卡爾(Kruskal)的避圈法：

(1)選e1∈E(G)，使得ω(e1)=min。

(2)若e1，e2，…，ei已選好，則從E(G)-{e1，e2，…，ei}中選取ei+1，使得G［{e1，e2，…，ei}］中無圈，且ω(ei+1)=min。

(3)繼續(xù)進行到選得en-1為止。

【例9.1.4】

求如圖9.1.4(a)所示的帶權(quán)圖的最小生成樹。(它的實際背景是北京與巴黎、紐約、東京、倫敦、墨西哥城這六大城市間的航空路線距離圖，單位是百千米。)

解圖9.1.4(b)中實線是用破圈法得到的最小生成樹(虛線是去掉的回路上的邊)，圖9.1.4(c)中粗實線是用避圈法得到的最小生成樹。其權(quán)均為122。

事實上因為邊(L，B)與(P，B)的權(quán)相等，所以最小生成樹并不唯一(如圖9.1.4的(b)與(c))，但是它們的權(quán)是相等的。圖9.1.4用破圈法和避圈法得到的最小生成樹

有向樹在不考慮方向時為無向樹的有向圖。根樹是一種特殊的有向樹。

定義9.2.1

T是一棵有向樹，若T中恰有一個頂點入度為0，其余頂點的入度均為1，則稱T為根樹。入度為0的頂點稱樹根，出度為0的頂點稱樹葉，入度為1、出度不為0的頂點稱內(nèi)點，內(nèi)點和樹根統(tǒng)稱為分支點。

例如，圖9.2.1中的(a)、(b)、(c)均是有向樹，但只有圖(c)是根樹。9.2根樹及其應(yīng)用圖9.2.1有向樹和根樹由定義和例題易知，對于(n，m)根樹，同樣有m=n-1，且根樹一定是有向樹，但反之未必。

在根樹中，從樹根v0到每個頂點vi有唯一一條初級通路，該通路的長度稱為點vi的層數(shù)，記作l(vi)，其中最大的層數(shù)稱為樹高，記作h(T)。

例如圖9.2.1(c)中，l(v0)=0，l(v1)=1，l(v4)=2，l(v7)=3=h(T)。

習(xí)慣上將根樹畫成樹根在上，各邊箭頭均朝下的形狀(如圖9.2.1(c)所示)，并為方便起見，略去各邊上的箭頭，可以看出，根樹上的各個頂點有了層次關(guān)系。

一棵根樹常常被形象的比作一棵家族樹，如果頂點u鄰接到頂點v，則稱u為v的父親，v為u的兒子；共有同一個父親的頂點稱為兄弟；如果頂點u可達頂點v，則稱u是v

的祖先，v是u的后代。在根樹T中，所有的內(nèi)點、樹葉均是樹根的后代，由某個頂點vi及其所有的后代構(gòu)成的導(dǎo)出子圖T′稱為T的以vi為根的子根樹。例如，圖9.2.1(c)中，v3是v1的兒子，

v1是v3的父親；v4與v5是兄弟，T′=G［{v2，v4，v5，v6，v7，v8}］是以v2為根的T的子根樹。

定義9.2.2在根樹T中，如果每一層的頂點都按一定的次序排列，則稱T為有序樹。

在畫有序樹時，常假定每一層的頂點是按從左到右排序的。例如圖9.2.2中的(a)和(b)表示的是不同的有序樹。而如果不考慮同層頂點的次序，則圖9.2.2(a)和(b)表示的是同一棵根樹。

【例9.2.1】

英語句子“Thebigelephantatethepeanut”可以圖解為圖9.2.3，稱之為這個英語句子的語法樹。可見，句子的語法樹是一棵有序樹。圖9.2.2圖9.2.3語法樹

定義9.2.3

設(shè)T是一棵根樹。

(1)若T的每個頂點至多有m個兒子，則稱T為m元樹。

(2)若T的每個頂點都有m個或0個兒子，則稱T為m元正則樹。

(3)若T是m元樹，并且是有序的，則稱T為m元有序樹。

(4)若T是m元正則樹，并且是有序的，則稱T為m元有序正則樹。

(5)若T是m元正則樹，且所有樹葉的層數(shù)都等于樹高，則稱T為m元完全正則樹。

(6)若T是m元完全正則樹，且是有序的，則稱T為m元有序完全正則樹。

(7)設(shè)T是m元樹，如果為T中每個頂點的兒子規(guī)定了確定的位置，則稱T為m元位置樹。例如，圖9.2.4中的(a)和(b)可看成相等的二元有序樹，但是不是相同的二元位置樹，圖(c)是二元正則樹，圖(d)是二元完全正則樹。圖9.2.4根樹的分類在所有的m元樹中，二元樹居重要地位，其中二元有序正則樹應(yīng)用最為廣泛。在二元有序正則樹中，以分支點的兩個兒子分別作為樹根的兩棵子樹通常稱為該分支點的左子樹和右子樹。

【例9.2.2】

用二元樹(見圖9.2.5)表示算術(shù)表達式：(a-b)÷(c×d+e)。圖9.2.5算式樹對計算機來說，二元位置樹最容易處理，因此常將有序樹轉(zhuǎn)化為二元位置樹，步驟如下：

(1)對于每個頂點只保留左兒子。

(2)兄弟間從左到右連接。

(3)對于每個分支點，保留的左兒子仍做左兒子，右邊鄰接的頂點做右兒子。

例如，圖9.2.6(a)是棵有序樹，圖(b)是表示圖(a)的一棵二元樹，圖(c)是相應(yīng)的二元位置樹。圖9.2.6有序樹轉(zhuǎn)化為二元位置樹此方法可以推廣到有序森林上去，只是將森林中每棵樹的根看作兄弟。

例如，圖9.2.7(a)是有序森林，圖(b)是表示圖(a)的一棵二元樹，圖(c)是相應(yīng)的二元位置樹。

顯然這種方法是可逆的，即任何一棵二元位置樹，也可以轉(zhuǎn)化為有序樹或有序森林。

最優(yōu)樹

下面提到的樹均是正則樹。圖9.2.7有序森林轉(zhuǎn)化為二元位置樹

定義9.2.4

設(shè)根樹T有t

片樹葉v1，v2，…，vt，

它們分別帶權(quán)w1，w2，…，wt，則稱T為(葉)帶權(quán)樹，稱W(T)=

wili為T的權(quán)，其中l(wèi)i是vi的層數(shù)。

【例9.2.3】

求4片樹葉分別帶權(quán)5,6,7,12的二元樹的權(quán)。

解根據(jù)題意，我們構(gòu)造出了四棵樹葉具有不同權(quán)的帶權(quán)二元樹，如圖9.2.8所示，其中圖(a)、(b)、(c)、(d)對應(yīng)的二元樹的權(quán)分別為

W(T1)=61，W(T2)=74，W(T3)=59，

W(T4)=60。圖9.2.8帶權(quán)二元樹由于樹葉的層數(shù)不同，葉權(quán)也大小各異，因此樹權(quán)是不同的，但其中必存在一棵權(quán)最小的二元樹。

定義9.2.5

在所有葉帶權(quán)w1，w2，…，wt的二元

樹中，權(quán)最小的二元樹稱最優(yōu)二元樹，簡稱最優(yōu)樹(又稱Huffman樹)。

如何尋求最優(yōu)二元樹？1952年哈夫曼(Huffman)給出了求最優(yōu)二元樹的算法。即Huffman算法：

令S={w1，w2，…，wt}，w1≤w2≤…≤wt，wi是樹葉vi所帶的權(quán)(i=1，2，…，t)。

(1)在S中選取兩個最小的權(quán)wi，wj，使它們對應(yīng)的頂點vi，vj

做兄弟，得一分支點vr，令其帶權(quán)wr=wi+wj。

(2)從S中去掉wi，wj，再加入wr。

(3)若S中只有一個元素，則停止，否則轉(zhuǎn)到(1)。

【例9.2.4】

構(gòu)造一棵帶權(quán)1,3,3,4,6,9,10的最優(yōu)二元樹，并求其權(quán)W(T)。

解構(gòu)造過程如圖9.2.9中的(a)～(g)?？傻肳(T)=93。圖9.2.9Huffman最優(yōu)樹的構(gòu)造過程一般來說，帶權(quán)w1，w2，…，wt的最優(yōu)二元樹并不唯一。

下面證明Huffman算法的正確性，先證下面的引理。

引理設(shè)T是一棵帶權(quán)w1≤w2≤…≤wt的最優(yōu)二元樹，則帶最小權(quán)w1，w2的樹葉v1和v2是兄弟，且以它們?yōu)閮鹤拥姆种c層數(shù)最大。

證明設(shè)v是T中離根最遠的分支點，它的兩個兒子va和vb都是樹葉，分別帶權(quán)wa和wb，而不是w1和w2。并且從根到va和vb的通路長度分別是la和lb，la=lb。故有

la≥l1，lb≥l2

現(xiàn)在將wa和wb分別與w1和w2交換，得一棵新的二元樹，記為T′，則

W(T)=w1l1+w2l2+…+wala+wblb+…

W(T′)=wal1+wbl2+…+w1la+w2lb+…于是

W(T)-W(T′)=(w1-wa)(l1-la)+(w2-wb)(l2-lb)≥0

即W(T)≥W(T′)，又T是帶權(quán)w1，w2，…，

wt的最優(yōu)樹，應(yīng)有W(T)≤W(T′)，因此W(T)=W(T′)。從而可知T′是將權(quán)w1，w2與wa，wb對調(diào)得到的最優(yōu)樹，故而la=l1，lb=l2，即帶權(quán)w1和w2的樹葉是兄弟，且以它們?yōu)閮鹤拥姆种c層數(shù)最大。

證畢

定理9.2.1

(Huffman定理)設(shè)T是帶權(quán)w1≤w2≤…≤

wt

的最優(yōu)二元樹，如果將T中帶權(quán)為w1和w2的樹葉去掉，并以它們的父親作樹葉，且?guī)?quán)w1+w2，記所得新樹為T∧，則T∧是帶權(quán)為w1+w2，w3，…，wt

的最優(yōu)樹。

證明由題意可知

W(T)=W(T∧)+w1+w2若不是最優(yōu)樹，則必有另一棵帶權(quán)w1+w2，w3…，wt

的最優(yōu)樹。令中帶權(quán)w1+w2的樹葉生出兩個兒子，分別帶權(quán)w1和w2，得到新樹T′，則

W(T′)=W(

)+w1+w2

因為是帶權(quán)為w1+w2，w3，…，wt

的最優(yōu)樹，所以

W(

)≤W(

)

如果W(

)＜W(

)，則必有W(T′)＜W(T)，與T是帶權(quán)w1≤w2≤…≤wt

的最優(yōu)二元樹矛盾，故是帶權(quán)為w1+w2，w3，…，wt

的最優(yōu)樹。證畢由Huffman定理易知Huffman算法的正確性。

最優(yōu)樹的一個直接用處是前綴碼的設(shè)計。

在遠程通訊中，通常的電報是用0和1組成的序列來表示英文字母和標(biāo)點符號的，英文有26個字母，所以只要用長度為5的等長字符串就可表達不同的字母了。發(fā)送端只要發(fā)送一條0和1組成的字符串，它正好是信息中字母對應(yīng)的字符序列。在接收端，將這一長串字符分成長度為5的序列就得到了相應(yīng)的信息。但是字母在信息中出現(xiàn)的頻繁程度是不一樣的，例如字母e和t在單詞中出現(xiàn)的頻率要遠遠大于字母q和z在單詞中出現(xiàn)的頻率。因此人們希望能用較短的字符串表示出現(xiàn)較頻繁的字母，這樣就可縮短信息字符串的總長度，顯然如能實現(xiàn)這一想法是很有價值的。對于發(fā)送端來說，發(fā)送長度不同的字符串并無困難，但在接收端，怎樣才能準(zhǔn)確無誤地將收到的一長串字符分割成長度不一的序列，即接收端如何譯碼呢？例如若用00表示t，用01表示e，用0001表示y，那么當(dāng)接收到字符串0001時，如何判斷信息是te還是y呢？為了解決這個問題，先引入前綴碼的概念。

定義9.2.6

設(shè)a1a2…an是長度為n的符號串，稱其子串

a1，a1a2，…，a1a2…an-1分別為該符號串的長度為1，

2，…，n-1的前綴。

設(shè)A={β1，β2，…，βn}為一個符號串集合，若A中任意兩個不同的符號串βi和βj互不為前綴，則稱A為一組前綴碼，若符號串中只出現(xiàn)兩個符號，則稱A為二元前綴碼。

如{0，10，110，1110，1111}是前綴碼，{00，001，011}不是前綴碼。

二元前綴碼與正則二元樹有一一對應(yīng)關(guān)系。在一棵正則二元樹中，將每個頂點和它的左兒子之間的邊標(biāo)記為0；和它的右兒子之間的邊標(biāo)記為1，如圖9.2.10(a)所示，把從根到每個樹葉所經(jīng)過的邊的標(biāo)記序列作為樹葉的標(biāo)記，由于每片樹葉的標(biāo)記的前綴是它的祖先的標(biāo)記，而不可能是任何其他樹葉的標(biāo)記，所以這些

樹葉的標(biāo)記就是前綴碼。由圖9.2.10(a)可看出前綴碼是{000，001，01，10，11}。

相反，如果給定前綴碼，也可找出對應(yīng)的二元樹。例如，前綴碼{000，001，01，1}對應(yīng)的二元樹如圖9.2.10(b)所示。圖9.2.10二元樹對應(yīng)的前綴碼當(dāng)知道了要傳輸?shù)姆柕念l率時，可用各個符號出現(xiàn)的頻率作權(quán)，用Huffman算法求一棵最優(yōu)樹T，由T產(chǎn)生的前綴碼稱為最佳前綴碼(又稱Huffman碼)，用這樣的前

綴碼傳輸對應(yīng)的符號可以使傳輸?shù)亩M制碼最省。

【例9.2.5】假設(shè)在通訊中，十進制數(shù)字出現(xiàn)的頻率Pi是

0：20%；1：15%；2：10%；3：10%；4：10%;

5：5%；6：10%；7：5%；8：10%；9：5%

(1)求傳輸它們的最佳前綴碼。

(2)用最佳前綴碼傳輸10000個按上述頻率出現(xiàn)的數(shù)字需要多少個二進制碼？

(3)它比用等長的二進制碼傳輸10000個數(shù)字節(jié)省多少個二進制碼？

解

(1)令i對應(yīng)葉權(quán)wi，wi=100Pi，則w0=20，w1=15，w2=10，w3=10，w4=10，w5=5，w6=10，w7=5，w8=10，w9=5。

構(gòu)造一棵帶權(quán)5,5,5,10,10,10,10,10,15,20的最優(yōu)二元樹(見圖9.2.11)，數(shù)字與前綴碼的對應(yīng)關(guān)系見圖右側(cè)。圖9.2.11最優(yōu)二元樹與最佳前綴碼即最佳前綴碼為：{10，010，111，110，001，0111，0001，0110，00000，00001}。

(2)(2×20%+3×(10%+15%+10%+10%)+4×

(5%+10%+10%)+5×(5%+5%))×10000=32500

即傳輸10000個數(shù)字需32500個二進制碼。

(3)因為用等長碼傳輸10個數(shù)字碼長為4，即用等長的碼傳10000個數(shù)字需40000個二進制碼，故用最佳前綴碼傳節(jié)省了7500個二進制碼。

【例9.3.1】

判斷下列命題是否為真。

(1)若n階無向簡單圖G的邊數(shù)m=n-1，則G一定是樹。

(2)若有向圖G僅有一個頂點的入度為0，其余頂點的入度都是1，則G一定是有向樹。

(3)任何樹T都至少有兩片樹葉。

(4)任何無向圖G都至少有一棵生成樹。

(5)根樹中最長初級通路的端點都是樹葉。9.3例題選解

(6)無向連通圖G中的任何一條邊都可以成為G的某棵生成樹的樹枝。

(7)(n，m)圖的每棵生成樹都有n-1條樹枝。

(8)以1，1，1，1，2，2，4為度數(shù)列的非同構(gòu)的樹有兩棵。

(9)任何無向樹的邊均是橋。

(10)G是(n，m)無向圖，若m≥n，則G中必有圈。

(11)G是(n，m)無向連通圖，若要求G的一棵生成樹，必刪去G中的m-n+1條邊。圖9.3.1解答與分析

(1)假命題。當(dāng)G是非連通無向圖時，頂點數(shù)和邊數(shù)可能滿足m=n-1，但G不是樹(如圖9.3.1所示)。

(2)假命題。當(dāng)G是非連通的有向圖時，各點入度可能滿足命題條件，但G不是有向樹(如圖9.3.2所示)。圖9.3.2

(3)假命題。在平凡樹中沒有兩片樹葉。

(4)假命題。當(dāng)且僅當(dāng)G是連通圖時，G中才有生成樹。例如圖9.3.1所示非連通圖沒有生成樹。

(5)假命題。根樹中最長初級通路的兩個端點，一個是樹葉，而另一個是樹根。

(6)假命題。無向連通圖G中若有環(huán)，則環(huán)永遠無法成為生成樹的樹枝，因為樹中無圈。

(7)真命題。因為(n，m)圖的每棵生成樹都是其生成子圖，必有n個頂點。

(8)真命題。如圖9.3.3所示，在一棵中兩個2度頂點鄰接，在另一棵中兩個2度頂點不鄰接。圖9.3.3

(9)真命題。由樹的等價定義可知。

(10)真命題。若G是非簡單圖，則G中必有環(huán)或平行邊，故G中有圈。

若G是簡單連通圖，則G中必有圈，否則G是樹，m=n-1，這與m≥n矛盾。

若G是簡單非連通圖，設(shè)其有k個連通分支，若每個連通分支均無圈，則G是森林，必有m=n-k，與m≥n矛盾，故至少有一個連通分支不是樹，在此分支中有圈。

(11)真命題。因每棵生成樹必有n-1條邊。

【例9.3.2】

G是n(n≥3)階連通無向圖，只有一個一度頂點，證明G中必有圈。

分析n≥3說明G不是平凡圖，只有一個一度頂點，說明G不是樹，因此，無向圖為樹的兩個條件至少有一個不滿足。

證明因為非平凡圖G只有一個一度頂點，所以G不是樹，又因為G是連通圖，因此G中必有回路。結(jié)論成立。

證畢

【例9.3.3】

(1)若T是高度為k的二元樹，則T的樹葉數(shù)最多為2k。

(2)若T是高度為k的二元完全正則樹，則T的頂點數(shù)為2k+1-1。

分析

(1)在同樣高度的二元樹中，二元完全正則樹的樹葉最多，只需證明二元完全正則樹的樹葉數(shù)是2k片。

(2)利用(1)的結(jié)果。

(1)T是高度為k的二元完全正則樹，對k做歸納：

當(dāng)k=1時，樹葉數(shù)t=2=21，結(jié)論成立。

假設(shè)k=n時結(jié)論成立，t=2n。

當(dāng)k=n+1時，因為在原來2n片樹葉中，每片葉均增加了2個兒子變成分支點，所以有樹葉t=2×2n=2n+1，由于在同樣高度的二元樹中，二元完全正則樹的樹葉最多，故結(jié)論成立。

(2)利用(1)知，在二元完全正則樹中，樹葉數(shù)亦即高度為k的頂點有2k個，故樹高為k的頂點總數(shù)為

證畢

【例9.3.4】

若圖G=〈V，E〉連通且e∈E，證明：

(1)e屬于每一個生成樹的充要條件是e為G的割邊。

(2)e不屬于G的任一個生成樹的充要條件是e為G中的環(huán)。

分析本題(1)、(2)均需從充分和必要兩部分予以論證。在(1)中如e屬于每個生成樹，需證G中刪去e后必不連通，否則e必不屬于某個生成樹與題設(shè)矛盾。在(2)中要證明e是環(huán)，可證e是僅含其本身的一個回路，否則e必屬于某棵生成樹。證明

(1)充分性。設(shè)e屬于G中每個生成樹T，若e不是割邊，則G-e連通，因此在G-e中必存在生成樹T，因為V(G-e)=V(G)，所以T也是G中的生成樹。但T中不包含e，與題設(shè)矛盾。

必要性。設(shè)e是G的割邊，若有G的某個生成樹T不包含e，則T+e必包含回路C，且e∈C。在C中刪去e后仍連通，故與e是割邊的假設(shè)矛盾。

(2)充分性。因為G連通，必有生成樹T，設(shè)e

T，則T+e包含回路C，如果C中除e外另有邊e1∈G，構(gòu)造T′=T+e-e1，T′必仍連通，因為|E(Ｔ′)|=|E(T)|=m-1，故T′也是G的一棵生成樹，但T′包含e，與題設(shè)矛盾。故C中沒有異于e的邊，即e是G中的環(huán)。

必要性。若e是G中的環(huán)，則e不能屬于G的任一棵生成樹，因為樹是連通無回路的。證畢

【例9.3.5】證明：連通圖中任一回路C與任一邊割集S有偶數(shù)(包括0)條公共邊。

證明假設(shè)邊割集S將連通圖G分成兩個連通分支V1、V2，若回路C只在一個連通分支中(譬如只在V1中)，則C與S沒有公共邊；若回路C在V1∪V2中，則從V1中頂點到V2中頂點，從V2中頂點到V1中頂點，因為是回路，所以必偶數(shù)次經(jīng)過S中的邊，故連通圖中任一回路C與任一邊割集S有偶數(shù)(包括0)條公共邊。證畢

【例9.3.6】

設(shè)T是二元正則樹，i為T中的分支點數(shù)，t為T中的樹葉數(shù)。證明：i=t-1。

證明由正則樹定義可知，二