《離散數學》第七章習題參考答案

第七章習題解答

1分析①計算總度數.幾階無向樹的邊數機=n-l,由握手定理可知

rf(Vj)=2m=2n-2；

②構造可能的度數歹|J.將2幾-2劃分成幾份，第地)為對應頂點巧的度

數d(u)1<d(vj<n-1,1<￡<n,且在這幾個數中奇數為偶數個：

③按每一個度數列畫樹.按不同的度數列畫出的樹都是不同構的，對同

一個度數列可能畫出多棵非同構的樹.

本題中：

(l)n=5,m=4,度數之和為8.將8劃分成3份的方案為：

①1,1,1,1,4;

②1,1,1,2,3;

③1,1,2,2,2.

每種方案都只有1棵非同構的樹.，共3棵非同構樹，如圖7-9.

圖7-9

(2)n=7,m=6,度數之和為12,將12劃分成7份的方案為:

①1,1,1,1,1,1,6;

②L1,1,1,1,2,5;

③1,1,1,1,1,3,4;

@1,1,1,1,2,2,4；

⑤1,1,1,1,2,33

@1,1,1,2,2,2,3;

⑦1,1,2,2,2,2,2.

在以上7種方案中，①、②、③、⑦各有1棵非同構的樹分別如圖7-

10(a)(b)(c)(g),④、⑤各有2棵非同構的樹分別如圖770(d)(e),而⑥有3

棵非同構的樹如圖7-10(f),共有11棵7階非同構的樹。例如④有唯一的4度

頂點必須與2度頂點相鄰。它與一個2度頂點相鄰，所得樹是非同構的，再沒

有其他情況，因而有2棵非同構的樹。

圖7-10

2分析設T有%個1度頂點(即樹葉),則T的頂點數兀=3+2+%=5+%,T的

邊數m=n-l=4+工由握手定理得方程

2m=2(4+%)=3x34-2x2+%=13+%

解得*=5.有5片樹葉,所求無向樹的度數序列1,1,1,1,1,2,2,3,3,3.由這個

度數序列可以畫多棵非同構的無向樹，圖7-11給出4棵這樣的樹。

圖7-11

3分析設3度頂點為%個，則階數幾=5+3+%=8+x,邊數m=7+%.由

握手定理

2m=14+2%=5x14-3x2+3%=11+3%

解得x=3,故幾=8+3=11.

4分析設T中有*個3度頂點，貝IT中的頂點數九=7+”,邊數由

握手定理得方程

2m=12+2x=3%+7

解得x=5,即丁中有5個3度頂點.T的度數序列為

1,1,1,1,1,1,1,3,3,3,3,3.由于丁中只有樹葉和3度頂點,因而3度頂點

可依次相鄰，如圖7T2所示。還有一棵與它非同構白樹，請讀者自己畫

出。

圖7-12

5分析幾階無向樹7有〃-1條邊，這是無向樹T的必要條件，但不是充分

條件。例如，九-1個頂點的初級回路和一個孤立點組成的九階無向簡單圖

有九-1條邊，但它顯然不是樹。即不一定。

6分析當A(T)=2時，即7的度數列為1,1,2,2,…,:2,2的情況，此時丁是一條長

度為n—1的路徑，故7中最長路徑的長度為九—1.

7分析圖7-1中有5個結點，因此要選取4條邊。期過程如圖7T3(a)-(d)所

示，IV(7)=22o

e

/\ae

V

Cd

ae弋ae

y

VV

d

d

圖7-13

8分析圖7-2中有6個結點，因此要選取5條邊。其過程如圖7T4(a)-(e)所

示，IV(7)=17。

a

2

1

d

bb

圖7-14

9分析圖7-3是5階圖，5階非同構的無向樹只有3棵，理由如下：5階無向

樹中，頂點數幾=5,邊數血=4,各頂點度數之和為8,度數分配方案有3種，分

別如下:

①1.1.1,1,4;

②1,1,1,2,3;

③1,1,2,22

每種方案只有一棵非同構的樹.圖7-9中頂點的最大度數是3,所以不可能

有度數序列為①的生成樹.于是，該圖最多有兩棵非同構的生成樹。在圖7-9

中是它的兩個非同構的生成樹，其中圖7-9(b)的度數序列為③，圖7-9(c)的度

數序列為②.

9分析圖7-4(a)

(l)c、d、g、h為弦，它們對應的基本回路為金=cab,Cd=dabf,Cg=

geabf,Ch=heab.基本回路系統為{%Cd，Cg,Cj

(2)a、b、c、f為樹枝,它們對應的基本割集系統為Sa={a,c,d,g,h},Sb=

{b,c,d,g,h},Se={e,g,h},Sf={f,d,g),基本本割集系統為{Sa，Sb，Se,Sf).

圖7-4(b)

(l)g、c、d、h、i為弦，它們對應的基本回路Cg=gfe,Cc=cbf,Cd=djaef,

6=用2已也。=12?1).基本回路系統為也8,Cc,Cd,Ch,C}.

(2)a、b、e、f、/為樹枝,它們對應的基本割集為Sa={a,d,h,i},Sb=

{b,c,h,i},Se={e,g,d,i,h},Sf={f,g,c,d],S,={j,d,h},基本割集系統為

{Sa，Sb，Se,Sf,Sj}.

10分析用Kruskal算法求解，求出的圖7-5(a)的最小生成樹T如圖7T51)

所不，其權W(7)=14。圖7-5(b)的最小生成樹如圖7T5(b)所不，其權

IV(T)=llo

5

圖7-15

11分析8421碼是等長碼，每個數字的代碼長為4,因此在譯碼時把編碼劃分

為小段,每段4位,而應一個十進制數字。例如，把0101000110000111劃分成

0101,0001,1000,0111,分別對應5,1,&7,故原文是5187.

(1)據上可推算出7201的編碼是0111001000000001,1509的編碼是

0001010100001001.

(2)0101000110000111的原文是5187,0011010100100100的原文是3524.

12分析在G、G、品中任何符號串都不是另外符號串的前綴，因而他們都是

前綴碼.而在中，1是11、101的前綴.在中，。是aa、ac等的前綴，因而

和都不是前綴碼.

13分析一般地，由r叉樹產生r元前綴碼。由圖7-4(a)給出的二元前綴碼為

C[={00,0100,01010,011,11]

由圖7-4(b)給出的二元前綴碼為

C2={00,01,0200,0201,0202,022,1,2).

14分析這個二元前綴碼不是等長的.在譯碼時，從左到右發現一個代碼就把它

譯出來，然后繼續往下.如nooioioioo、1、11和iio都不是代碼，neo

是4的代碼，譯出4.繼續往下，1和10都不是代碼，101是3的代碼，譯

出3.再往下，01、00分別是1、0的代碼.于是，它的原文是4310.

(1)八進制數字的代碼如下：

0-001-012-1003-101

4-11005-11016-11107-1111

(2)6014的編碼是111000011100,1725的編碼是0111111001101.

(3)11001010100代表的八進制數是4310,01111100100代表的八進制數

是1702.

15分析將所有的頻率都乘100,所得結果按從小到大順序排序：

wg=5,Wf=5,we=10,wd=10,

wc=15,wb=20?wa=35

以上各數為權，用Huffman算法求一課最優二叉樹，圖7-16所示。

100

斗1X20354

55?畫叵

0000I0001|

圖7-16

對照各個權可知各字母的前綴碼如下：

a-10,b-01,c=111,d-110,

e-001,/-0001,g-0000

于是，。、匕的碼長為2,c、d、e的碼長為3,f、g的碼長為4.

IV(7)=255(各分支點的權之和)，W(T)是傳輸100個按給定頻率

出現的字母所用的二進制數字的個數，因而傳輸IO4個按上述頻率出現的

字母要用2.55x104=25500個二進制數字.

最后還應指出一點，在畫最優樹時，由于頂點位置的不同，可能得

到不同的前綴碼.事實上，交換相同碼長的代碼和交換頻率相同的字母的

代碼不會改變需要的二進制數字的期望個數.從而，只要它們中有一個是

最佳前綴碼，其他的也都是最佳前綴碼.

15.分析(1)用中序遍歷法訪問該樹，得到

(((a*b—c)+(d+e*/))*g)+((九*i)+0*(k—Z)))

省去一些圓括號，得到算式的表達式

((Q*b-c)+(d+e*/))*g+(九*i)+0*(攵―/))

⑵用前序遍歷法訪問這棵樹并刪去所有的圓括號，得到算式的波蘭符號

法表達式

4-*-：■—*abc+d*e/g**M*j—kl

(3)用后序遍歷法訪問這棵樹并刪去所有的圓括號，得到算式的逆波蘭符

號法表達式

ab*c-def*++g*hi*jk，一*++

提升習題

1分析(1)用中序行遍法訪問這棵樹，得到

(((a+(b*c))*d—e)+(/+g))+((/i*i)*J)

省去一些圓括號，得到算式的表達式

((a+(b*c))*d—e)+(/+g))+九*i*j

⑵用前序行遍法訪問這棵樹并刪去所有的圓括號，得到算式的波蘭符號法表達

式

++-*+0*bcde+fg**hij

⑶用后序行遍法訪問這棵樹并刪去所有的圓括號，得到算式的逆波蘭符號法表

達式

abc*+d*e—fg++hi*j*+

(3)將變量的值代入波蘭符號法表達式

+—*+4*3133+12**321

計算如下：

++_*+4*3133+12**321

++—*+4*3133+12-61

+—*+4*3133+126

++-*+4*313336

+—*+433336

++-*73336

+-：—(21)336

++(18)36

+66

(12)

在上面為了區分一位數和二位數，用括號把二位數括起來.

將變量的值代入逆波蘭符號法表達式

431*+3*3—12++32*1*4-

計算如下：

431*4-3*3-1232*1*4-

43+3*3—12++32*1*+

73*3—12++32*1*+

(21)3—12++32*1*+

(18)12++32*1*+

(18)3+32*1*+

632*1*4-

661*+

66+

(12)

2分析邏輯運算中有一元運算符「，因此表示命題公式的二叉樹不是正則的.

由于「的運算對象跟在它的后面，所以為了用中序行遍法訪問能恢復原式，「所

在頂點的兒子應為右兒子.不過抱著對用前序行遍法訪問和用后序行遍法訪問的

結果沒有影響.

表示命題公式的二叉樹如圖7-17所示.用前序行遍法訪問該樹并刪去所有

圓括號，得到命題公式的前綴符號法表達式

tAVpq-ir—ApqVqr

用后序行遍法訪問該樹并刪去所有圓括號，得到命題公式的后綴符號法表達式

pqV丁一iAp-yqAqr

圖7-17

3分析(1)設計思路

輸入：賦權連通圖G=VV,E>。

輸出：G的一個最小生成樹。

實現語言：C語言。

基本思路：使用Prim算法。

在G中任意選取一個結點Vi，置％={vi},ET=,k=lo

在V—VT中選取與某個%￡%鄰接的結點使得邊(v“Vj)的權最小，置

VP=VyU{Vj},ET=ETU{(Vj,Vj)],k=k+l。

重復(b)，直到k=|V|。

(2)參考代碼

/*Prim算法求賦權圖的最小生成樹*/

#include<stdi.h>

#defineN7〃圖的階數

^defineINF1000〃不相鄰的點，距離設為一個極大數字

structedge

(

intstart;

Tntend;

intweight;

}；

//w為圖的權值矩陣

intw[N][N]={{0}12,INF,INF,INF,16,14},

{12,0,10,INF,INF,7,INF},

{INF,10,0,3,5,6,INF),

{INF,INF,3,0,4,INF,INF},

{INF,INF,5,4,0,2,8},

{14,INF,INF,INF,8,9,0}};

intverteces[N}={0};〃點加入生成樹的順序，node中的點屬U,不在

node中的屬于V-U

structedgeedges[N];//U中頂點到V-L'中頂點的最小權值的邊

inttree[N][N]={0};〃存儲最小生成樹

intsum=0;

/本從所有的u屬丁U,v屬丁V-U(V-U表示除去U的所有頂點)的邊中選取

權值最小的邊(u,V),

*將頂點v加入集合U中，將邊(u,v)加入集合T中

*/

intmain()

(

〃將權值數組初始化為“第1個頂點”到“該頂點”的權值。

for(intk=0;k〈N;k++)

edges[k).start=0;

edges[k].end=k;

edges[k].weight=w[O][k];

}

〃第一個點加入node,此為起點

vertexes[0]=1;

//Prim

for(intk=