电视大学_离散数学_形成性考核册_作业(二)答案.doc

离散数学形成性考核作业(二)图论部分本课程形成性考核作业共4次,内容由中央电大确定统一布置本次形考作业是第二次作业,大家要认真及时地完成图论部分的形考作业,字迹工整,抄写题目,解答题有解答过程第3章 图的基本概念与性质1.计算出下图2.1的结点数与边数,并说明其满足握手定理.图2.1 习题1的图2.试分别画出下列图2.2(a)(b)(c)的补图.图2.2 习题2的图3.找出下图2.3中的路通路与圈.图2.3 习题3的图4.设G为无向图,|G|=9,且G每个结点的度数为5或6,试证明G中至少有5个6度结点或至少有6个5度结点.5.设有向图D=如图2.4所示,图2.4 习题5的图试问图中是否存在长度分别为3, 4, 5, 6的回路,如存在,试找出.6.若无向图G有10条边,3度与4度结点均2个,其余结点的度数均小于3,试问G中至少有几个结点?若无向图G中有6条边,3度与5度结点均有一个,其余结点的度数均是2,试问G中有几个结点?7.试求图2.5中有向图的强分图,单侧分图和弱分图.图2.5 习题7的图8.试说明图2.6中G1和G2同构.图2.6 习题8的图解;满足两图同构的必要条件,将两图结点分别标号,建立两图间的一个恰当的双射即可9.试求图2.7中的邻接矩阵与可达矩阵.图2.7 习题9的图10.有n个结点的无向完全图的边数为 .11.图中度数为奇数的结点为 偶 数个.12.已知图G的邻接矩阵为 ,则G有( C ). A.5点,8边 B.6点,7边 C.5点,7边 D.6点,8边第4章 几种特殊图1.试分别构造满足下列条件的无向欧拉图(1)有偶数个结点,奇数条边.(2)有偶数个结点,偶数条边.(3)有奇数个结点,偶数条边.(4)有奇数个结点,奇数条边.解:见课堂答疑 2.分别构造满足下列条件的四个汉密尔顿图(1)偶数个结点,奇数条边.(2)有偶数个结点,偶数条边.(3)有奇数个结点,偶数条边.(4)有奇数个结点,奇数条边.解:见课堂答疑3.试画出一个没有一条欧拉回路,但有一条汉密尔顿回路的图.解:见课堂答疑4.如图2.8是否为欧拉图?试说明理由.图2.8 判断是否为欧拉图 5.如图2.9是否为汉密尔顿图?试说明理由.图2.9 判断是否为汉密尔顿图6.试分别说明图4.3(a)(b)与(c)是否为平面图.图2.10 判断是否为平面图 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+211.无向连通图 G 是欧拉图的充分必要条件是_.应填:图中每个结点的度数都是偶度数12.设G是具有n个结点的简单图,若在G中每一对结点度数之和大于等于_,则在G中存在一条汉密尔顿路.应填:n-1(即书中P.123定理4.2.2)13.现有一个具有个奇数度结点的图,若要使图中有一条欧拉回路,最少要向图中添加_条边.第5章 树及其应用1.试指出图2.13中那些是树,那些是森林,并说明理由.图2.13 习题1的图2.试画出图2.14中的一个生成树,并说明其中的树枝弦,以及对应生成树的补. 图2.14 习题2的图解:见课堂答疑3.试画出如图2.15的完全图K5 的所有不同构的生成树. 图2.15 习题3的图解:见课堂答疑 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有( )个4度结点? A.1 B.2 C.3 D.4 7.无向树T有3个3度结点,2个4度结点,其余的都是树叶,则T有( )片树叶? A.3 B.7 C.9 D.11 8.无向树T有1个2度结点,3个3度结点,4个4度结点,1个5度结点,其