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

第五章习题参考答案

基础习题

1(a)为多重图，平行边的重数分别为2和3。

(b)为多重图，平行边的重数分别为2和3。

(c)为线图，也为简单图。

(d)为线图，但不是简单图。

2图5-30的补图分别为

(a)(b)

3(b)为降的子图、真子图、为由｛%,外,内，畤｝导出的小的子图，不是降的生

成子图。

(C)为Ks的子图、真子图、为由｛%,-%以，%｝导出的K5的子图，是小的

生成子图。

(d)为《的子图、真子图、为由｛%小2，%，%｝导出的勺的子图，不是勺生

成子图。

4G=(V,E)=(…{v>,v吆%>(%%),(%，%)

<VpV3>，vVS,VS>))

5

(1)(2)

(4)

6(1)由握手定理知，该图有16个结点。

(2)设该图有a个结点,由握手定理知,2x4+2x3+2x(a-2-2)=10x2,解得a=7

(3)设该图有a个结点，由握手定理知，2x4+lx6+2x(a21)=10x2,解得a=6

(4)设该图有a个结点，每个结点的度数为b,ab=24x2,解得a=2；a=3；

a=4：a=6；a=8：a=12：a=24o

7(1)(2)(3)(5)能构成无向图的度数序列。

(1)(2)(3)能构成无向简单图的度数序列。

8由握手定理，有向图中，所有结点的入度之和等于所有结点的出度之和等于边

数。图G的入度序列能成为2,2,2,2。

9由握手定理，有向图中，所有结点的入度之和等于所有结点的出度之和等于边

数。图G的入度序列不能成为1,1,1,1。

10图5-7(a)的邻接矩阵为

0102

020

0201

010

图5-8(a)的邻接矩阵为

001

^5-3(3)=0

1

图5-9(a)的邻接矩阵为

0100

^5-9(a)=011

010

0110

11图5-7(a)的关联矩阵为

/I0001

1100

^5-7(3)=110

1110

\000119

图5-8(a)的关联矩阵为

/-I00

M5-8(a)=1-11

V01-1

图5-9(a)的关联矩阵为

100

M5_9®=110

011

001

12图5-8(a)的邻接矩阵为

/001\/001\

A=101A2=101

\110/\110/

长度为3的回路数为2的对角线元素之和3o

13图5-9(a)的邻接矩阵为

1

1

1

2

长度为2的回路数为A?的对角线元素之和1+3+2+2=8,

14冗的所有非同构的子图如下，其中8-18是生成子图，3、6、7、11、12、13、

14、16、17是连通图。

15

16

提升习题

1设无向图G有12条边，G中度数为3的结点有W个，其余结点的度数均小于或等

于3,问G中至少有多少个结点？为什么？

答：由握手定理知，G中各结点度数之和为24,6个3度结点占去18度，若其余全

是3度结点，还需要2个结点，所以至少有6+2=8个结点。

23阶有向完全图的所有非同构子图如下图所示，其中5-20是生成子图。

3图5-29(a)的邻接矩阵为

/012\/525\

2

A2-29(a)=1o1A=224

\212/\549/

Q1)=5,所以从结点％到结点%的长度为2的通路数目为5

Q埠二9,所以从结点心到自身的长度为2的回路数目为9

所有长度为2的通路数为A?的所有元素之和即38

4图5-25b的邻接矩阵为

/0000\/0000\

A=1020

looool岸=1。0。0。0。0/

\1010/\0000/

/I000\

\1011/

所以从%到％是可达的，从功到女、“2、”3是可达的，从内到内是可达的，

从“4到巧L、%、办是可达的，从%到〃2、%、%是不可达的，从“2到心是不可

达的，从%到%、〃2、「4是不可达的，从外到口2是不可达的。

=v

d(〃2,%)d(「4,%)=d(v4>3)=d(U2,%)=1

d(vpv2)=d(v1/v3)=dOi，“4)=d(v2,v4)=co

00

d(-i)=d(v3,v2)=d(v3,v4)=d(-2)=

5

%v

v24%u7%%

10(无)

2。(无)1%6(%)3(%)2(%)8(%)8(%)8(%)8(%)8(%)

36(%)3(%)2(%)1%8(%)12(%)8(%)8(%)8(%)

43(%)|%8(%)12(%)8(%)8(%)

5(V3)8(巧)

56(%)12⑺8(%)8(%)8(%)

66(>2)|%12(分)8(%)9(%)12(%)

712(%)8(%)|g9(%)11⑹

8皿加)9(%)磔11(%)

911(%)

101心7)1%

打到"2的最短路径为%%"2,距离为5；

%到内的最短路径为%%，距离为3:

%到%的最短路径为巧以，距离为2;

匕到打的最短路径为%%W%，距离为