最新电大 - 离散数学 - 形成性考核册 - 作业（二）答案

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

图论部分

本课程形成性考核作业共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) ?3?2?3?2?2?0?12?2?6满足握手定理。2．试分别画出下列图2.2(a)、(b)、(c)的补图．

图2.2 习题2的图

解：(a)是5阶图，用另一种颜色把原图添加边成5阶完全图K5，由5个结点和新颜色的边构成的图就是它的补图。(b)是5阶图，用另一种颜色把原图添加边成5阶完全图K5，由5个结点和新颜色的边构成的图就是它的补图。由4个结点和新颜色的边构成的图就是它的补图。上面给出的是求已知图的补图的方法。此题只要画出补图即可。3．找出下图2.3中的路、通路与圈．

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

1

图2.3 习题3的图

解：书中定义的路就是路径，也就是通路。此题应是求基本路径、基本回路（圈），并且指出哪两个点之间的基本路径、基本回路（圈）。在根据定义找出。??[注意]：本题应对应书中P.114典型例题例44．设G为无向图，|G|=9，且G每个结点的度数为5或6，试证明G中至少有5个6

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

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

解：设G?(n,m),知n?9，如果设有x个6度的结点，则有(9?x)个5度的结点。由定理知，奇度数结点的个数应是偶数，即(9?x)是偶数。再由握手定理，x?6?(9?x)?5?2mx?2m?45,x必为奇数。当x?3时，(9?x)?6；当x?5时，(9?x)?4；当x?7时，(9?x)?2。于是，G中至少有5个6度的结点或至少有6个5度的结点。5．设有向图D=如图2.4所示，

因此，有下述情况：当x?1时，(9?x)?8；

图2.4 习题5的图

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

解：存在长度为3，4，5，6的回路。下面以边序列的形式各给出一个长度为3，4，5，6的回路。长度为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?.2

6．若无向图G有10条边，3度与4度结点均2个，其余结点的度数均小于3，试问G中至少有几个结点？若无向图G中有6条边，3度与5度结点均有一个，其余结点的度数均是2，试问G中有几个结点?

解：(1)设其余结点有x个，共有x?2?2?x?4个结点，由握手定理知，2?(3?4)?2x?2?102x?6x?3x?4?7G中至少有7个结点。由握手定理知，1?3?1?4?2x?2?62x?4x?2x?2?4G中共有4个结点。

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

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

(图是什么样的呢？)

图2.5 习题7的图

解：从左上角开始逆时针将结点编号1，2，3，4，5，6强分图为由结点集{1，2，6}，{3},{4},{5}导出的子图；单向分图为原图：弱分图就是原图。8．试说明图2.6中G1和G2同构．

G1 G2 图2.6 习题8的图

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

恰当的双射即可。

3

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

图2.7 习题9的图

解：?0??1A??1??0?0?1100??0100?1010?，?0100?0000??采用布尔乘法和布尔加法，?1??1B5?A?A2?A3?A4?A5??1??1?0?也可以直接由图得到可达矩阵P。1110??0110?1010??P。?1100?0000??

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

应添1n(n?1) 211．图中度数为奇数的结点为 偶 数个．

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

，

则G有（ C ）．

A．5点，8边 B．6点，7边 C．5点，7边 D．6点，8边

第4章 几种特殊图

1．试分别构造满足下列条件的无向欧拉图 （1）有偶数个结点，奇数条边． （2）有偶数个结点，偶数条边． （3）有奇数个结点，偶数条边． （4）有奇数个结点，奇数条边．

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 判断是否为平面图

5