《电大离散数学形成性考核册作业答案.docx》由会员分享，可在线阅读，更多相关《电大离散数学形成性考核册作业答案.docx（11页珍藏版）》请在三一办公上搜索。
1、电大离散数学形成性考核册作业答案离散数学形成性考核作业 图论部分 本课程形成性考核作业共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=26满足握手定理。2试分别画出下列图2.2(a)、(b
2、)、(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的图 解：书中定义的路就是路径，也就是通路。此题应是求基本路径、基本回路，并且指出哪两个点之间的基本路径、基本回路。在根据定义找出。LL注
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)是偶数。再由握手定理，x6+(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时
4、，(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条边
5、，3度与5度结点均有一个，其余结点的度数均是2，试问G中有几个结点? 解：(1)设其余结点有x个，共有x+2+2=x+4个结点，由握手定理知，2(3+4)+2x2102x6x3x+47G中至少有7个结点。由握手定理知，13+14+2x=262x=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同构 G
6、1 G2 图2.6 习题8的图 解；满足两图同构的必要条件，将两图结点分别标号，建立两图间的一个 恰当的双射即可。 3 9试求图2.7中的邻接矩阵与可达矩阵 图2.7 习题9的图 解：01A=100110001001010，01000000采用布尔乘法和布尔加法，11B5=A+A2+A3+A4+A5=110也可以直接由图得到可达矩阵P。111001101010=P。1100000010有n个结点的无向完全图的边数为 应添1n(n-1) 211图中度数为奇数的结点为 偶 数个 12已知图G的邻接矩阵为 ， 则G有 A5点，8边 B6点，7边 C5点，7边 D6点，8边 第4章 几种特殊图 1试分
7、别构造满足下列条件的无向欧拉图 有偶数个结点，奇数条边 有偶数个结点，偶数条边 有奇数个结点，偶数条边 有奇数个结点，奇数条边 4 解：见课堂答疑。 2分别构造满足下列条件的四个汉密尔顿图 偶数个结点，奇数条边 有偶数个结点，偶数条边 有奇数个结点，偶数条边 有奇数个结点，奇数条边 解：见课堂答疑。 3试画出一个没有一条欧拉回路，但有一条汉密尔顿回路的图 解：见课堂答疑。 4如图2.8是否为欧拉图？试说明理由 图2.8 判断是否为欧拉图 解：不是欧拉图。因为不满足欧拉图的充要条件，图中结点的度数不都是偶数。 5如图2.9是否为汉密尔顿图？试说明理由 图2.9 判断是否为汉密尔顿图 解：是汉密尔
8、顿图。因为存在汉密尔顿路。如下，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、与是否为平面图 图2.10 判断是否为平面图 5 解：(a)、(b)、(c)都是平面图。(a)图中将左下结点和右上结点间的边从左斜上方拉到外面即可。(b)图中将左下结点、右上结点以及内部两点对应的三边从左斜上方拉到外面即可。(c)图中将内部最下面结点及其关联的两条边由正上方拉到外边，内部最上面结点及其关联的三条边向正下方拉到内部中间点下面，所有的交叉点就没有了。注意：回答此问题时，只需指出(a
9、)、(b)、(c)是平面图，(把a)、(b)、(c)相应的平面图画出即不可必，陈述上面文字。 7试分别求出图2.11、与的每个图的面的次数 图2.11 求面的次数 解：因图中面没有标号，见课堂答疑。 8试利用韦尔奇鲍威尔算法分别对图2.12、与着色 图2.12 图的着色 解：见课堂答疑。 9若G是一个汉密尔顿图，则G一定是( C ) A欧拉图 B平面图 C连通图 10设G是有n个结点m条边的连通平面图，且有k个面，则k等于( A ) Am-n+2 Bn-m-2 Cn+m-2 Dm+n+2 解：由欧拉公式得，n-m+k=2,所以k=m-n+2 11无向连通图 G 是欧拉图的充分必要条件是_ 应填
10、：图中每个结点的度数都是偶度数。 12设G是具有n个结点的简单图，若在G中每一对结点度数之和大于等于_，则在G中存在一条汉密尔顿路 应填：n-1 13现有一个具有k个奇数度结点的图，若要使图中有一条欧拉回路，最少要向图中添加_条边 6 解：我们知道图中奇数度数的结点必有偶数个，故k为偶数， k要使图中有一条欧拉回路，最少要向图中添加条边。2第5章 树及其应用 1试指出图2.13中那些是树，那些是森林，并说明理由 图2.13 习题1的图 解：(a)、(c)是树，因为它们分别为连通且无回路的图符合树的定义。(b)是森林，因为孤立结点是树，(b)是由两棵树组成的图。2试画出图2.14中的一个生成树，
11、并说明其中的树枝、弦，以及对应生成树的补 图2.14 习题2的图 解：见课堂答疑。 3试画出如图2.15的完全图K5 的所有不同构的生成树 图2.15 习题3的图 解：见课堂答疑。 K5不同构的生成树有。三棵4试求出图2.16中的最小生成树及其权值 它们的顶点度数序别列为分， 图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度结点？ A1 B2 C3 D4 解：应填A。设T有n个结点，T共有n-1条边，
12、7片树叶的度数都是1，度数为4的结点有(n-7-3)=(n-10)个，由握手定理知，17+33+4(n-10)=2(n-1)2n=22n=11n-10=1 7无向树T有3个3度结点,2个4度结点,其余的都是树叶，则T有片树叶？ A3 B7 C9 D11 解：应填C。设T有n个结点，T共有n-1条边，树叶的度数都是1，树叶有(n-3-2)个，由握手定理知，33+42+1(n-3-2)=2(n-1)n=9+8-5+2n=14n-3-2=9共有9片树叶。 8无向树T有1个2度结点,3个3度结点,4个4度结点,1个5度结点,其余的都是树叶，则T有片树叶？ A12 B14 C16 D20 解：应填C。有16片树叶。设T有n个结点，T共有n-1条边，树叶的度数都是1，树叶有(n-1-3-4-1)=(n-9)个，由握手定理知，21+33+44+51+1(n-9)=2(n-1)n=2+9+16+5-9+2n=25n-9=16共有16片树叶。 9无向树T有9片树叶,5个3度结点,其余的都是4度结点，则T有几个4度结点？ A0 B1 C2 D3 8 解：答案是B。设T有n个结点，T共有n-1条边，树叶的度数都是1，4度结点共有(n-9-5)=(n-14)个，由握手定理知，19+35+4(n-14)=2(n-1)2n=30n=15n-14=1共有1个4度结点。 9
