《离散数学》第七章习题参考答案

第七章习题解答

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=