(电大复习)《离散数学》1-9作业答案--任务07答案VIP

形成性考核 作业 1 离散数学作业 7 离散数学 图论部分 形成性考核 书面 作业 本课程形成性考核 书面 作业共 3 次，内容 主要分别是图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型安排练习题目 ，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。 本次形考 书面 作业是第 二 次作业，大家要 认真及时地完成 图论部分的 综合练习 作业 。 要求： 将此作业用 A4 纸打印出来，手工书写答题， 字迹工整，解答题 要 有解答过程 ，完成并上交任课教师（不收电子稿）。 并在 07 任务界面下方点击“保存”和“交卷”按钮，以便 教师评分。 一、单项选择题 1设图 G 的邻接矩阵为0101010010000011100000100， 则 G 的边数为 ( D ) A 5 B 6 C 3 D 4 2设图 G ，则下列结论成立的是 ( C ) A deg(V)=2E B deg(V)=E CEvVv 2)deg( DEvVv )deg(3设有向图（ a）、（ b）、（ c）与（ d）如 下 图所示 ， 则下列结论成立的是 ( D ) A（ a） 是强连通的 B（ b） 是强连通的 C（ c） 是强连通的 D（ d） 是强连通的 4 给定无向图 G 如右图所示，下面给出的结 点集子集中，不是点割集的为（ B ） A b, d B d 姓 名： 学 号： 得 分： 教师签名： a b d c e 4 题图 形成性考核 作业 2 C a, c D b, e 5 图 G 如 右 图所示，以下说法正确的是 ( C ) A (a, c)是割边 B (a, c)是边割集 C (b, c)是边割集 D (a, c) ,(b, c)是边割集 6无向图 G 存在欧拉通路，当且仅当 (D ) A G 中所有结点的度数全为偶数 B G 中至多有两个奇数度结点 C G 连通且所有结点的度数全为偶数 D G 连通且至多有两个奇数度结点 7 若 G 是一个欧拉图，则 G 一定是 ( C ) A 平面图 B 汉密尔顿图 C 连通图 D 对偶图 8 设 G 是连通平面图，有 v 个结点， e 条边， r 个面，则 r= ( A ) A e v 2 B v e 2 C e v 2 D e v 2 9设 G 是有 n 个结点， m 条边的连通图，必须删去 G 的 ( A )条边，才能确定 G 的一棵生成树 A 1mn B mn C 1mn D 1nm 10 已知一棵无向 树 T 中有 8 个结点， 4 度， 3 度， 2 度的分支点各一个， T的树叶数为 （ D ） A 8 B 5 C 4 D 3 二、填空题 1已知图 G 中有 1 个 1 度结点， 2 个 2 度结点， 3 个 3 度结点， 4 个 4 度结点，则 G 的边数是 15 2 设给定图 G(如 右 由图所示 )，则图 G 的点 割 集 是 f,c 3 设 G 是一个图，结点集合为 V，边集合为 E，则 G 的 结点 度数 等于边数的两倍 4 设有向图 D 为欧拉图，则图 D 中每个结点的入度 等于出度 5 设 G=是具有 n 个结点的简单图，若在 G 中每一对结点度数之和大于等于 n-1 ，则在 G 中存在一条汉密尔顿路 6 设无向图 G 是 汉密尔 顿图，则 V 的任意非空子集 V1，都有 W(G-V1) V1 7 设完全图 Kn有 n 个结点 (n2)， m 条 边， 当 当 m=2n 时， Kn中存在欧拉回路 8 设图 GV,E，其中 Vn， Em则图 G 是树当且仅当 G 是连通的， a b c d e 5 题图 形成性考核 作业 3 且 m 2V-2 9 连通无向图 G 有 6 个顶点 9 条边，从 G 中删去 4 条边才有可能得到 G 的一棵生成树 T 10 设正则 5 叉树的树叶数为 17，则分支数为 i = 4 三 、判断说明题 （ 判断下列各题，并说明理由 ） 1 (1) 如果图 G 是无向图，且其结点度数均为偶数，则图 G 存在一条欧拉回路 (2) 图 G1， (如下图所示 ) 是 欧拉图 解： (1)错， 图 G 是无向图，当且仅当 G 是连通的，且所有结点度数均为偶数，这里不能确定 G 图是否是连通的。 (2)错，由欧拉图的定理“无向图 G 具有一条欧拉路，当且仅当 G 是连通的，且有零个或两个奇数度结点”得到这里任何一个结点都没有奇数度结点。 2图 G2（如下图所示） 不 是欧拉图 而是 汉密尔 顿图 解：错，既不是欧拉图也不是汉密尔图。欧拉图要求 所有结点度数均为偶数，这里结点 b,d 各有三个节点；汉密尔图要求每一对结点 度数之和大于等于总结点数，这里不满足。 形成性考核 作业 4 3 (1) 设 G 是一个有 7 个结点 16 条边的连通图，则 G 为平面图 (2) 设 G 是一个连通平面图， 且 有 6 个结点 11 条边，则 G 有 7 个面 解： (1)错，没有提到面。 (2)对，由欧拉定理得到：结点 -边 +面 =2，即为连通平面图，这里 6-11+7=2 4下图给出的树是否同构 的 解： (a)同构， (b),(c)同构。 因为由图的同构相关联，得到同构的必要条件： (1)结点数目相同。 (2)边数相同。 (3)度数相同的结点数 目相同 故 (a)不满足，即不同构。 四、 计算题 形成性考核 作业 5 1 设 G=， V= v1， v2， v3， v4， v5， E= (v1,v3)， (v2,v3)， (v2,v4)， (v3,v4)，(v3,v5)， (v4,v5) ，试 (1) 给出 G 的图形表示； (2) 写出其邻接矩阵； (3) 求出每个结点的度数； (4) 画出其补图的图形 解： (1) (2)G=0110010110110110110000100(3)v1 度数为 1， v2 度数为 2， v3 度数为 4， v4 度数为 3， v5 度数为 2 2图 G=，其中 V=a, b, c, d, e, f ， E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f), (e, f) ，对应边的权值依次为 5， 2， 1， 2， 6， 1， 9， 3 及 8 (1) 画出 G 的图形； (2) 写出 G 的邻接矩阵； (3) 求出 G 权最小的生成树 及其权值 v1 v2 v3 v4 v5 形成性考核 作业 6 解： (2)G=011000101011110010010001011001010110(3) 最小生成树是 (a,e),(e,c),(b,d),(d,f)权值为 3已知带权图 G 如右图所示 (1) 求图 G 的最小生成树； (2)计算该生成树的权 值 解： (1)最小生成树为 1,4,3,2,7,5 (2)权值为 22 4设有一组权为 2, 3, 5, 7, 17, 31， 试画出相应的最优二叉树 ， 计算 该 最优二叉树 的 权 形成性考核 作业 7 解： (1)图画在材料纸上 (2)由图得到最优二叉树的权为： 65 五 、 证明 题 1 设 G 是一个 n 阶无向简单图， n 是大于等于 3 的奇数证明图 G 与它的补图 G 中的奇数度顶点个数相等 证明：因为 G 是 n阶无向简单图，且 n 是大于等于 3 的奇数，故无向图的结点数为奇数，又对于任何图有奇数度数和偶数度数之和是结点数的 2 倍，故 G图的度数为偶数，故 G 中 需要的是奇数的结点，偶数度数，故 G 和 G 的奇数度数相同，顶点个数也是相同的。即证。 2 设连通图 G 有 k 个奇数