离散数学第11章答案(刘玉珍 刘永梅)

离散数学 答案 刘玉珍 刘永梅

习题11.1

1． 若n个顶点的简单无向图G中至少有2个孤立点，则结论自然成立；若G中只有一个孤立点，而n 2，则G中至少有3个顶点，其中至少有2个非孤立点，可不考虑孤立点；若G中无孤立点，则G中n个顶点度数均不小于1.现设G中n个顶点的度数均不小于1，又G为简单图，故所有顶点的度数均不大于n-1，即n个顶点的度数的取值只能是1，2， ，n-1,由鸽舍原理知，结论成立。 2． 设G有x个顶点，则2 12 deg(v) 6 3 (x 6) 2 x 9

v V

3． 2m deg(v) nk k (n nk) (k 1) nk (k 1)n 2m

v V

4． n min{deg(v)v V} 2m deg(v) n max{deg(v)v V}

v V

故所证不等式成立。

5.（1）非同构的4个顶点的自补图只有一个图有2个

；非同构的5个顶点的自补

G为自补图 G与G的边数相同，（2）设均为m，又G与G的边数之和为Kn的

边数

n(n 1)n(n 1)

，即=2m，亦即n(n 1)=4m，故n为4的倍数，即n=4k，或22

n-1为4的倍数，即n=4k+1，k I

6.（1）<0,1,1,2,3,3>,<3,3,3,3>均为可图解的，其对应图为

<1,3,3,3>非可图解，否则，设deg(v1) 1,deg(v2) deg(v3) deg(v4) 3，由于要构成无向简单图，故，v1，v2，v3，v4之间必定有边关联，这与deg(v1) 1矛盾，< 2，3，4，4，5>,<2,2,4>非可图解，以为简单图中所有顶点的度数多为n-1。

<1,2,2,3,4,5>z中有奇数个，故非可图解。

离散数学 答案 刘玉珍 刘永梅

（2）充分性：<d2 1,d3 1, , dd1 1,dd1 1 1,dd1 2, ,dn>可图解 添加度数为

d1的顶度，与度数为d2 1,d3 1, , dd1 1,dd1 1 1的顶点相邻 <d1,d2, , dn>可图解。

必要性：<d1,d2, , dn>可图解，设度数为d1的顶点与度数分别为d2， ，dd1 1的顶点相邻，删去度数为d1的顶点 <d2 1,d3 1, ,

dd1 1,dd1 1 1,dd1 2, ,dn>可图解。

7.设K6的顶点为V1，V2， ，V6，随意用红色和蓝色涂K6的边，则由V1引出的5条边中至少有3条同色边，不妨设存在3条红色边，且该3条边的另一端点分别为V2，V3，V4。若V2，V3，V4构成的K3中的边再有一条，比如（V2，V3）为红色边，则V1，V2，V4构成的K3为红色；若V2，V3，V4的边全为蓝色，则结论已成立。

离散数学 答案 刘玉珍 刘永梅

习题11.2

1. 强分图为：

单向分图为：

弱分图为：

2.（1）G弱连通 G对应的无向图连通 至少需要n-1条边连接n个顶点 n-1 m.

G为简单图 m E(Kn)=n(n-1),故n 1 m n(n 1)

（2）G强联通，由定理11.2.3知，G至少有n条边，故n m n(n 1) 3.若G非基本回路，又G连通，则G中必有顶点的度数不等于2，矛盾。

,

4．设e含于两个不同的基本回路v1ev2e2 ekv1，与v1ev2e2 ei,v1中，则e不含于

回路

,

ei,v1中，由推论11.2.2知，存在从v1到v1的基本回路，且e不含于v1ek ev2e2

该基本回路中。

5.设G不连通，且有k 2个连通分支，G1，G2， ，Gk，其中Gi有ni个顶点，

i=1，2， ，k。

n(n 1)n(n 1)n2(n2 1)(n 1)(n1 1)(n 1)(n2 1)

kk 则m 11

22222

(n 1)(nk 1)(n 1)(n k)(n 1)(n 2) 。

222

即2m (n 1)(n 2)，矛盾，故G连通。

离散数学 答案 刘玉珍 刘永梅

步骤依次对应为1，3，2，5，4，9，6，7，8，11，12，10，13

V0V2=1 V0V4=2 V0V1，V0V2V1=2 V0V1V6，V0V2V1V6=4

V0V2V3=3

V0V1V6V7V11，V0V2V1V6V7V11，V0V4V8V11=8 V0V1V6V7，V0V2V1V6V7=5

V0V4V8=5

V0V1V5，V0V2V1V5，V0V1V6V5，V0V2V1V5V6=6 V0V1V6V10，V0V2V1V6V10=9

离散数学 答案 刘玉珍 刘永梅

V0V4V8V12，V0V1V6V7V11V12，V0V4V8V11V12=9

V0V1V5V9，V0V2V1V5V9，V0V1V6V5V9，V0V2V1V6V5V9=9

V0V1V6V10V13，V0V2V1V6V10V13，V0V4V8V12V13，V0V1V6V7V11V12V13，

V0V4V8V11V12V13=10 长度分别为4，5，4，6，5

离散数学 答案 刘玉珍 刘永梅

习题11.3

1 1

1.（1）A

0 0 2 12

A

0 0 3 2A3

0 0 5 34

A

0 0

110021003200211043017410

10001 1 0 1 2 1 1 0 4 3 0 1

1101

0 0 1 0

11 7

234

令B A A A A

0 07147 495 022

022

（2）由A4知，V1到V4的长度为4的通路有4条。 （3）由A3知，V1到自身的长度为3的回路有3条。

（4）由B知，长度不超过4的通路条数为B中元素之和为72，其中回路的条数为B中对角线元素之和19。

01000 10100

2.（1）A 01000

00011 00010

离散数学 答案 刘玉珍 刘永梅

02000 A2

1

0100

00021

00011 02000 0200 A3

2 0

2000

00032

00021 20200 04000 A4

2

0200 00053

0

0032

4

337

令B A A1 A2 A3 A4

3

3 00 00

1

1100

1100 故可达矩阵P

1 1

1100

00011

00011

00001 10100 3（1）A

0

0001

10100

01010

01010 00002 A2

0

1010

00002

2

0200

30

0

300 400 0127

075

离散数学 答案 刘玉珍 刘永梅

2020 A3

0 2

0200 02020

00004 00004 40400 A4

0

0004

40400

0

4040

3

B A0 A1 A2 A3 A4

5 2

5 2

1213521312535255 2 1

15 P

2 1

1

5 1

111

111 111 111

111

111

11

离散数学 答案 刘玉珍 刘永梅

习题11.4

1.（1）如

（2）如

（3）如

（4）如

2.(a)

Euler通路为V1V2V3V4V6V3V5V6V7V2V8V1V7V8

(b)

Euler回路为V1V2V3V1V5V3V4V5V6V2V4V6V1

3.(a) 是Hamilton图，有一个Hamilton回路为

离散数学 答案 刘玉珍 刘永梅

V1V8V10V7V9V2V3V6V4V5V1

(b)

非Hamilton图，取S {V1,V4,V8,V10}则

P(G S) 5 S。

4.设G中存在Vi与Vj不相邻，且deg(Vi) deg(Vj) n 1，令G1 G {Vi,Vj}，则G1为

的简单图，且其边数

11

m1 (n 1)(n 2) 2 (n 1) (n 2)(n 3) 1，与G1为简单图矛盾，故G中任

22

意两个不相邻的顶点的度数之和均不小于n，因此，G为Hamilton

图。

n-2

个

顶

点

左图中有4个顶点，

(4 1)(4 2)

1 4条边，但非Hamilton图。 2

1

若G中有不相邻的两个顶点，则它们的度数之和不小于2

n G为Hamilton图。

5 v V,deg(v)

，左图中有3个顶点，且v V，deg(v)

6，（1）acbeda 18 (2)aedbca,acbdea,16

习题11.5

3

1，但非Hamilton图。 2

(n1 n2)2n2

1. 设1 n1,2 n2，则m E(Kn1,n2) n1n2 44

离散数学 答案 刘玉珍 刘永梅

2. 构造偶图G=<V1,V2,E>，其中V1 {P1,A2, ,A7}，V2 {A10} 1,P2, ,P

(Pi,Aj) E Aj适合Pi，则G如右图所示按照Pi中度数小的顶点，优先于Aj中度数小的顶点匹配的原则，得一匹配{P4A3,P2A7,P7A5,P5A10,P6A5,P1A9,P3A6}也是最大匹配和完备匹配。

习题11.6

1．若G不连通，则可适当添加边但不增加面，得连通图G1，设G1的顶点数、边数、面数分别为n1,m1,k1，G的边数为m，则n1=n, m1>m, k1=k。由Euler公式知n1-m1+k1=2 m<m1=n+k-2，由定理11.6.3知m1≤3n-6，故n+k-2≤3n-6，即k≤2n-4。若G连通，则n-m+k=2，又m≤3n-6，故k≤2n-4。

2．如G： ，则G： G,

G 均为平面图。

3．设G与G均为平面图，且均连通，G与G的边数分别为m与m，则m≤3n-6,m≤3n-6(若G与G不连通，则可适当添加边使之为连通平面图，不等式仍成立)。而

n(n 1)13 m m 6n 6 n2 13n 24 0 n 11，矛22

盾，故G或G非平面图。

4．不妨设G连通，否则，G的每个连通分支的边数均应小于30，则可对G的每

个分支进行讨论。若G中无回路，则G必为树，结论显然成立。若G中有回路，则简单图G中每个面至少由3条边围成，故G至少有3个顶点，从而m 3n 6。若G中所有顶点的度数均不小于5，则

离散数学 答案 刘玉珍 刘永梅

2m deg(V) 5n n

v V

26

m m 3n 6 m 6 m 30，与m 30矛55

盾，故结论成立。

5．（1）设G不连通，且有k 2个连通分支G1,G2, ,Gk，设Gi的顶点数为ni，边数为mi，i=1,2, ,k。若 nj 1，则k=2，因为此时G为一个平面图，并上一个K6才能使其边数为15，但K6含子图K5，故K6为非平面图，与G为平面图矛盾；若 nj 2，则简单图Gj中至多只有一条边，另外5个顶点构成K5时边数最多，但也只有10条边，与G有15条边矛盾。故

ni 3,i 1,2, ,k，从而mi 3ni 6,i 1,2, ,k m 3n 6k，将m=15,n=7代入，得k 1,与k 2矛盾，故G为连通图。

（2）简单图G的每个面至少由3条边围成，设G中至少有一个面由4条或4条以上的边围成，则2m>3m，即k<10，而由Euler公式知，n-m+k=2即k=10，矛盾，故G的每个面均由3条边围成。 6．（a）非平面图，因为含子图K3.3。（b）非平面图，因为含同胚于K3.3的子图（右图中删去V1即同构K3.3

）。

8．（1）如第7题（a）所示。

离散数学 答案 刘玉珍 刘永梅

（2）G为平面图，且G G* G*为平面图。G*连通 G连通，设G的面数

为k，则n=G*的顶点数=k。由Euler公式知，n-m+n=2,即m=2n-2。

9．（a）由第10题知，色数为2。

（b）中含长度为奇数的基本回路，该回路上的顶点需3种色，而3种色够用，

故色数为3。

（c）中含长度为奇数的基本回路，该回路上的顶点需3种色，而该基本回路

外另有一度数为5的顶点与该基本回路上每个顶点相邻，故至少需4种，而4种够用，故色数为4。 10．充分性：G中无奇数长度的基本回路G为偶图，记作G=<V1,V2,E>，给V1中

顶点着第一种色，V2中顶点着第二种色，则G为2——可着色的。 必要性：G为2——可着色的，第一种色的顶点集记为V1，第二种色的顶点集记为V2，则V1中顶点互不相邻，V2中顶点也互不相邻，故G=<V1,V2>为偶图。

习题11.7

1． 设有x个1度顶点，则2m=2(2+1+3+x-1)= deg(V)=x×1+2×2+1×3+3×

v V

4 x=9。

2． 当n=2时，d1,d2∈I ，且d1+d2=2×2-2，则d1=d2=1，存在一棵顶点度数11的树 ，结论成立。设n=k>2时，结论成立，则n=k+1时，

d1,d2, ,dk 1中至少有一个大于1。不妨设d1>1，否则d1=d2= =dk 1，则

d

i 1

k 1

i

=k+1≠2(k+1)-2，且d1,d2, ,dk 1中至少有2个为1。不妨设

k 1i 1

k 1i 1

dk=dk 1=1，否则 di≥2k+1，故 di≠2(k+1)-2。由归纳假设知，存在一棵顶点度数分别为d1-1, d2, ,dk 1,1的无向树。在该树上添加一个度数为1的顶点，它只与度数为D的顶点相邻，则得一棵顶点度数分别为d1,d2, ,

dk 1,1,1，即d1,d2, , dk 1,dk,dk 1的无向数。 3． 树中无回路 树中无奇数长度的基本回路 树为偶图。

4． 设G中有k棵树，其中第i棵树的顶点数为ni，边数为mi，则mi=ni-1，i=1， ，

离散数学 答案 刘玉珍 刘永梅

k，故m= mi= ni-k=n-k。

i 1

i 1

kk

5． 设G中无回路，则G的k≥1个连通分支也无回路，故连通分支均为树，由第4题知m=n-k<n，与m≥n矛盾，故G中必有回路。 6． （a）

（b）

7． 不一定，如右图

个顶点只有1顶点入度为0，其余顶点入度为1

8． 设T中顶点数为n，其中有k个分支点，由二元正则树的定义知，n=k+t,m=2k,m=n-1 m=2t-2。 9． （1）、（3）非前缀码，（2）为前缀码。 10．题目有误，“0.6”应改为“0.06”。

为使通信中出现的二进制数字尽可能少，应使用较短的符号串传输频率较高

的字符，因此构造最优二元树如下：

故0,1,2, ,6,7的编码分别为：01,11,001,100,101,0001,00001,00000。最

佳前缀码为{01,11,001,100,101,0001,00001,00000}。

本文来源：https://www.bwwdw.com/article/dlwe.html