离散数学形成性考核作业（二）
图论部分
本课程形成性考核作业共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=
因此，有下述情况：当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
解：(a)、(b)、(c)都是平面图。(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
解：由欧拉公式得，n?m?k?2,所以k?m?n?2
11．无向连通图 G 是欧拉图的充分必要条件是_________________． 应填：图中每个结点的度数都是偶度数。 12．设G是具有n个结点的简单图，若在G中每一对结点度数之和大于等于________，则在G中存在一条汉密尔顿路．
应填：n-1（即书中P.123定理4.2.2）
13．现有一个具有k个奇数度结点的图，若要使图中有一条欧拉回路，最少要向图中添加_________条边．
6
解：我们知道图中奇数度数的结点必有偶数个，故k为偶数， k要使图中有一条欧拉回路，最少要向图中添加条边。2
第5章 树及其应用
1．试指出图2.13中那些是树，那些是森林，并说明理由．
图2.13 习题1的图
解：(a)、(c)是树，因为它们分别为连通且无回路的图符合树的定义。(b)是森林，因为孤立结点是树，(b)是由两棵树组成的图。
2．试画出图2.14中的一个生成树，并说明其中的树枝、弦，以及对应生成树的补．
图2.14 习题2的图
解：见课堂答疑。
3．试画出如图2.15的完全图K5 的所有不同构的生成树．
图2.15 习题3的图 解：见课堂答疑。
K5不同构的生成树有。三棵4．试求出图2.16中的最小生成树及其权值．
它们的顶点度数序别列为分（4，1，1，1，1），（3，2，1，1，1），（2，2，2，1，1）
图2.16 习题4的图
7
解：见课堂答疑。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有（ ）个4度结点？
A．1 B．2 C．3 D．4
解：应填A。设T有n个结点，T共有n?1条边，7片树叶的度数都是1，度数为4的结点有(n?7?3)?(n?10)个，由握手定理知，1?7?3?3?4?(n?10)?2?(n?1)2n?22n?11?n?10?1
7．无向树T有3个3度结点,2个4度结点,其余的都是树叶，则T有（ ）片树叶？ A．3 B．7 C．9 D．11
解：应填C。设T有n个结点，T共有n?1条边，树叶的度数都是1，树叶有(n?3?2)个，由握手定理知，3?3?4?2?1?(n?3?2)?2?(n?1)n?9?8?5?2n?14?n?3?2?9共有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共有n?1条边，树叶的度数都是1，树叶有(n?1?3?4?1)?(n?9)个，由握手定理知，2?1?3?3?4?4?5?1?1?(n?9)?2?(n?1)n?2?9?16?5?9?2n?25?n?9?16共有16片树叶。
9．无向树T有9片树叶,5个3度结点,其余的都是4度结点，则T有几个4度结点？ A．0 B．1 C．2 D．3
8
解：答案是B。设T有n个结点，T共有n?1条边，树叶的度数都是1，4度结点共有(n?9?5)?(n?14)个，由握手定理知，1?9?3?5?4?(n?14)?2?(n?1)2n?30n?15
?n?14?1共有1个4度结点。 9
电大 离散数学 形成性考核册 作业（二）答案
