最新电大 - 离散数学 - 形成性考核册 - 作业(二)答案.pdf

最新电大-离散数学-形成性考核册-作业（二）答案离散数学形成性考核作业（二）图论部分本课程形成性考核作业共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?.26．若无向图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同构．G1G2图2.6习题8的图解；满足两图同构的必要条件，将两图结点分别标号，建立两图间的一个恰当的双射即可。39．试求图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）偶数个结点，奇