2023年电大离散数学形成性考核册作业答案

离散数学形成性考核作业（二）

图论部分

本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第二

次作业，大家要认真及时地完毕图论部分旳形考作业，字迹工整，抄写题目，解答题有解答

过程。

第3章

图旳基本概念与性质

1．计算出下图2.1旳结点数与边数，并阐明其满足握手定理．

图2.1

习题1旳图

解：结点数为6，按逆时针给结点编号为v1,v2,v3,v4,v5,v6.

边数为6。

deg(v1)deg(v2)deg(v3)deg(v4)deg(v5)deg(v6)

满足握手定理。

3232201226

2．试分别画出下图2.2(a)、(b)、(c)旳补图．

图2.2

习题2旳图

由5个结点和新颜色的边构成的图就是它的补图。

由5个结点和新颜色的边构成的图就是它的补图。

解：(a)是5阶图，用另一种颜色把原图添加边成5阶完全图K5，

(b)是5阶图，用另一种颜色把原图添加边成5阶完全图K5，

(c)是4阶图，用另一种颜色把原图添加边成4阶完全图K4，

由4个结点和新颜色的边构成的图就是它的补图。

即可。

3．找出下图2.3中旳路、通路与圈．

上面给出的是求已知图的补图的方法。此题只要画出补图

图2.3

习题3旳图

解：书中定义的路就是路径，也就是通路。

此题应是求基本路径、基本回路（圈），并且指出哪两个点

之间的基本路径、基本回路（圈）。

要找出所有的基本路径、基本回路（圈），就要先将结点标号，

在根据定义找出。

[注意]：本题应对应书中P.114典型例题例4

4．设G为无向图，|G|=9，且G每个结点旳度数为5或6，试证明G中至少有5个6

度结点或至少有6个5度结点．

解：设G(n,m),知n9，如果设有x个6度的结点，则有

(9x)个5度的结点。由定理知，奇度数结点的个数应是偶数，

即(9x)是偶数。再由握手定理，

x6(9x)52m

x2m45,

x必为奇数。

当x3时，x)6；

(9

当x5时，x)4；

(9

当x7时，x)2。

(9

于是，G中至少有5个6度的结点或至少有6个5度的结点。

因此，有下述情况：当x1时，x)8；

(9

5．设有向图D=<V,E>如图2.4所示，

图2.4

习题5旳图

试问图中与否存在长度分别为3,4,5,6旳回路，如存在，试找出．

解：存在长度为3，，，的回路。

456

下面以边序列的形式各给出一个长度为3，，，的回路。

456

长度为3的回路：

长度为4的回路：

长度为5的回路：

长度为6的回路：

v1,v5,v5,v2,v2,v1;

v1,v5,v5,v3,v3,v2,v2,v1;

v1,v5,v5,v4,v4,v3,v3,v2,v2,v1;

v1,v5,v5,v2,v2,v1,v1,v5,v5,v2,v2,v1.

6．若无向图G有10条边，3度与4度结点均2个，其他结点旳度数均不不小于3，试

问G中至少有几种结点？若无向图G中有6条边，3度与5度结点均有一种，其他结点旳

度数均是2，试问G中有几种结点?

解：)设其余结点有x个，共有x22x4个结点，

(1

由握手定理知，(34)2x210

2

2x6

x3

x47

G中至少有7个结点。

(2)设其余结点有x个，共有x11x2个结点，

由握手定理知，3142x26

1

2x4

x2

x24

G中共有4个结点。

(图是什么样的呢？

)

7．试求图2.5中有向图旳强分图，单侧分图和弱分图．

图2.5

习题7旳图

解：从左上角开始逆时针将结点编号1，，，，，

23456

强分图为由结点集{1，，}，},{4},{5}导出的子图；

26{3

单向分图为原图：

弱分图就是原图。

8．试阐明图2.6中G1和G2同构．

G1

G2

图2.6

习题8旳图

解；满足两图同构旳必要条件，将两图结点分别标号，建立两图间旳一种

恰当旳双射即可。

9．试求图2.7中旳邻接矩阵与可达矩阵．

图2.7

习题9旳图

解：

0

1

A1

0

0

1100

0100

1010，

0100

0000

采用布尔乘法和布尔加法，

11110

10110

B5AA2A3A4A511010P。

11100

00000

也可以直接由图得到可达矩阵P。

10．有n个结点旳无向完全图旳边数为

．

应添1n(n1)

2

11．图中度数为奇数旳结点为

偶

数个．

12．已知图G旳邻接矩阵为

，

则G有（C

）

．

B．6点，7边

D．6点，8边

A．5点，8边

C．5点，7边

第4章几种特殊图

1．试分别构造满足下列条件旳无向欧拉图

（1）有偶数个结点，奇数条边．

（2）有偶数个结点，偶数条边．

（3）有奇数个结点，偶数条边．

（4）有奇数个结点，奇数条边．

解：见课堂答疑。

2．分别构造满足下列条件旳四个汉密尔顿图

（1）偶数个结点，奇数条边．

（2）有偶数个结点，偶数条边．

（3）有奇数个结点，偶数条边．

（4）有奇数个结点，奇数条边．

解：见课堂答疑。

3．试画出一种没有一条欧拉回路，但有一条汉密尔顿回路旳图．

解：见课堂答疑。

4．如图2.8与否为欧拉图？试阐明理由．

图2.8

判断与否为欧拉图

解：不是欧拉图。因为不满足欧拉图的充要条件，图中结点

的度数不都是偶数。

5．如图2.9与否为汉密尔顿图？试阐明理由．

图2.9

判断与否为汉密尔顿图

解：是汉密尔顿图。因为存在汉密尔顿路。如下，

v1(v1,v7)v7(v7,v2)v2(v2,v4)v4(v4,v8)v8(v8,v6)v6(v6,v5)v5(v5,v3)v3(v3,v1)v1.

6．试分别阐明图4.3（a）（b）与（c）与否为平面图．

、

图2.10

判断与否为平面图

解：)、b)、c)都是平面图。

(a((

(a)图中将左下结点和右上结点间的边从左斜上方拉到外面即可。

(b)图中将左下结点、右上结点以及内部两点对应的三边从左斜上方

拉到外面即可。

(c)图中将内部最下面结点及其关联的两条边由正上方拉到外边，

内部最上面结点及其关联的三条边向正下方拉到内部中间点下面，所有

的交叉点就没有了。

[注意]：回答此问题时，只需指出(a)、b)、c)是平面图，把(a)、b)、c)相

((

((

应的平面图画出即可，不必陈述上面文字。

7．试分别求出图2.11（a）（b）与（c）旳每个图旳面旳次数．

、

图2.11求面旳次数

解：因图中面没有标号，见课堂答疑。

8．试运用韦尔奇·鲍威尔算法分别对图2.12（a）（b）与（c）着色．

、

图2.12

图旳着色

解：见课堂答疑。

（先画成原则旳平面图，再着色，使相邻面不一样色，且只能少于或等于四种颜色。

）

9．若G是一种汉密尔顿图，则G一定是(C

)．

A．欧拉图

B．平面图

C．连通图

10．设G是有n个结点m条边旳连通平面图，且有k个面，则k等于(A

A．m-n+2

)．

B．n-m-2

C．n+m-2

D．m+n+2

解：由欧拉公式得，nmk2,所以kmn2

11．无向连通图G是欧拉图旳充足必要条件是_________________．

应填：图中每个结点旳度数都是偶度数。

12．G是具有n个结点旳简朴图，

设

若在G中每一对结点度数之和不小于等于________，

则在G中存在一条汉密尔顿路．

应填：n-1（即书中P.123定理4.2.2）

13．既有一种具有k个奇数度结点旳图，若要使图中有一条欧拉回路，至少要向图中添

加_________条边．

解：我们知道图中奇数度数的结点必有偶数个，故k为偶数，

要使图中有一条欧拉回路，最少要向图中添加k条边。

2

第5章树及其应用

1．试指出图2.13中那些是树，那些是森林，并阐明理由．

图2.13

习题1旳图

解：)、c)是树，因为它们分别为连通且无回路的图符合树的定义。

(a(

(b)是森林，因为孤立结点是树，)是由两棵树组成的图。

(b

2．试画出图2.14中旳一种生成树，并阐明其中旳树枝、弦，以及对应生成树旳补．

图2.14习题2旳图

解：见课堂答疑。

3．试画出如图2.15旳完全图K5旳所有不一样构旳生成树．

图2.15习题3旳图

解：见课堂答疑。

K5不同构的生成树有三棵。

它们的顶点度数序列分别为（4，1，1），（3，，1，

1，1，

21，1），（2，，，1）

221，

4．试求出图2.16中旳最小生成树及其权值．

图2.16习题4旳图

解：见课堂答疑。W(T)=1+1+1+1+1+2=7

5．给定一组权值为1，2，2，3，6，7，9，12，是求出对应旳一种最优树．

解：见课堂答疑。

6．无向树T有7片树叶,3个3度结点,其他旳都是4度结点，则T有（

结点？

A．1

B．2

C．3

D．4

）个4度

解：应填A。

设T有n个结点，T共有n1条边，片树叶的度数都是1，度数为4的结点有

7

(n73)(n10)个，

由握手定理知，

17334(n10)2(n1)

2n22

n11

n101

）片树叶？

7．无向树T有3个3度结点,2个4度结点,其他旳都是树叶，则T有（

A．3

B．7

C．9

D．11

解：应填C。

设T有n个结点，T共有n1条边，树叶的度数都是1，树叶有(n32)个，

由握手定理知，3421(n32)2(n1)

3

n9852

n14

n329

共有9片树叶。

8．

无向树T有1个2度结点,3个3度结点,4个4度结点,1个5度结点,其他旳都是树叶，

则T有（

A．12

）片树叶？

B．14

C．16

D．20

解：应填C。有16片树叶。

设T有n个结点，T共有n1条边，树叶的度数都是，树叶有(n1341)

1

(n9)个，

由握手定理知，13344511(n9)2(n1)

2

n2916592

n