离散数学第五版答案.doc

离散数学第五版答案【篇一：离散数学第五章作业答案】,2,3 ，试求d 的出读列解：由于 ??+ v =d v ????(??), 故出度列为 2,2,1,0. 如图5.5 下面各无向图中有几个顶点？ （ 1） 16 条边，每个顶点都有 2度顶点 （2）21 条边， 3 个 4 度顶点，其余是 3 度顶点 （ 3） 24 条边，各顶点的度数相同的 解：设顶点个数为 n，则有握手定理知：(1)2?n=2?16 ??=16(2)3?4+ n?3 =2?21 ??=13(3) 设顶点的度数为 k ，则 nk=2*4=48 且 n,k 均为正整数， 则 ①n=1,k=48 ⑥ n=8,k=6 ② n=2,k=24 ⑦ n=12,k=4③ n=3,k=16 ⑧ n=16,k=3 ④ n=4,k=12 ⑨ n=24,k=2⑤ n=6,k=8 ⑩ n=48,k=15.11 k4 的生成子图中有几个非同构的自补图解：1个即5.12 画出 3 阶有向完全图所有非同构子图，问其中有几个是生成子图，生成子图中有几个是自补图 解： 顶点 个数边数123456123生成 子图其中生成子图是 16 个，子补图是画5.14 已知 n 阶无向图 g 中有 m 条边，各顶点的度数均为 3，又已知 2n-3=m ，问在同构的意义下， g 是唯一的吗？若 g 为简单图，是否唯一？解：由握手定理知 2m=3n ，又知 2n-3=m 则 g 不是唯一的，即使简单图也不唯一的如5.18 有向图 d 在定义意义下长度为 4 的通路总数，并指出有多少条是回路，又有 ???? 到 ???? 通得 d 的邻接矩阵为 v11??2= 0101100010010，111211 0201(4)1v2 v3??4= 1102110故长度为 4 的通路总数 15 ，回路数为 3，v3 到 v4 的通路有 ??34=2 5.19 求图中 b 到其余各定点的最短路径和距离解，用 dijkstra 算法得t 1 2 3 4 5 6 7a c d e f g 引入 b 引入 c 引入 a 引入 f 引入 e 引入 g(1,b)?(5,c) (5,c) (5,c)?(4,c) (4,c)?故 b 到其余各顶点的最短路径和距离为b→a：ba ，长度为4 b→c：bc ，长度为 1 b →d： bcegd ， 长度为 9 b →e： bce ，长度为 5 b →f：bcf ，长度为 4 b →g：bceg ，长度为 7 5.20 解：（ 1）画出项目网络图2 5【篇二： 2016 离散数学作业 5 答案】散数学图论部分形成性考核书面作业本课程形成性考核书面作业共 3 次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业要求：将此作业用 a4 纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求 2010 年 12 月 5 日前完成并上交任课教师（不收电子稿）并在 05 任务界面下方点击 “保存 ”和“交卷 ”按钮，以便教师评分一、填空题1．已知图 g 中有 1 个 1 度结点， 2 个 2 度结点， 3 个 3 度结点， 4个 4 度结点，则 g 的边数是 15 ．2．设给定图 g( 如右由图所示 )，则图 g 的点割集是 ．3．设 g 是一个图，结点集合为 v，边集合为 e，则 g 的结点 等于边数的两倍．4．无向图 g 存在欧拉回路，当且仅当 g 连通且． 5．设 g=v ， e 是具有 n 个结点的简单图，若在 g 中每一对结点度数之和大于等于 n-1 ，则在 g 中存在一条汉密尔顿回路．6．若图 g=v, e 中具有一条汉密尔顿回路，则对于结点集 v 的每个非空子集 s，在 g 中删除 s 中的所有结点得到的连通分支数为 w ，则 s 中结点数 |s| 与 w 满足的关系式为 w?s ．7．设完全图 kn 有 n 个结点 (n?2) ，m 条边，当 n 为奇数时， kn 中存在欧拉回路．8．结点数 v 与边数 e 满足关系的无向连通图就是树．有 6 个结点的连通图，结点的总度数为 18 ，则可从10 ．设正则 5 叉树的树叶数为 17，则分支数为 i9．设图g 中删去g 是二、判断说明题（判断下列各题，并说明理由．）1 ．如果图 g 是无向图，且其结点度数均为偶数，则图 g 存在一条欧拉回路．． 答：不正确，图 g 是无向图，当且仅当 g 是连通，且所有结点度数均为偶数，这里不能确定图 g 是否是连通的。

2．如下图所示的图 g 存在一条欧拉回路．答：错误因为图 g 为中包含度数为奇数的结点3．如下图所示的图 g 不是欧拉图而是汉密尔顿图．g答：错，既不是欧拉图也不是汉密尔顿图，欧拉图要求所有结点度数均为偶数，这里结点 bd 各有三个节点；汉密尔顿图要求每一对结点度数之和大于等于总结点数，这里不满足5．设 g 是一个连通平面图，且有 6 个结点 11 条边，则 g 有 7 个面．答：正确因为连通平面图满足欧拉公式即：v?e?r?2由此题条件知 6-11+7=2 成立三、计算题1．设 g=v ，e， 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） v1v2v3?00100??00110???（ 2） a(d)??11011? ??01101????00110??（ 3） deg(v1)?1 、deg(v2)?2 、 deg(v3)?4 、 deg(v4)?3 、 deg(v5)?22 ．图 g=v, e ，其中 v={ a, b, c, d, e} ，e={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) } ，对应边的权值依次为 2、1、2、3、6、 1、4 及 5，试（ 1）画出 g 的图形； （ 2）写出 g 的邻接矩阵； （3）求出 g 权最小的生成树及其权值． b c解：（ 1）。

ae5 d?0?1?（ 2） a(d)??1 ??0??1 1101? 0011?? 0011?? （3）bc 1101? 1110??2 1 3a 1 ed 其权值为： 7 3 ．已知带权图 g 如右图所示．(1) 求图 g 的最小生成树； (2)计算该生成树的权值．答： (1)1 275 3(2) 权值为 18 4．设有一组权为 2, 3, 5, 7, 17, 31 ，试画出相应的最优二叉树，计算该最优二叉树的权．解： 6517485 1217 312357权值为 65 四、证明题1．设 g 是一个 n 阶无向简单图， n 是大于等于 3 的奇数．证明图 g与它的补图 g 中的奇数度顶点个数相等．证明：设 a 为 g 中任意一个奇数度顶点，由 g 定义， a 仍为 g 顶点，为区分起见，记为 a’则, deg(a)+deg(a ’)=n-1, 而 n 为奇数，则 a’必为奇数度顶点由 a 的任意性，容易得知结论成立2．设连通图 g 有 k 个奇数度的结点，证明在图 g 中至少要添加使其成为欧拉图．证明：由定理推论知：在任何图中，度数为奇数的结点必是偶数个，则 k是k条边才能 2偶数。

又由欧拉图的充要条件是图g 中不含奇数度结点因此，只要在每对奇数度结点间各加一条边，使图g 的所有结点的度数变为偶数，成为欧拉图故k最少要加条边才能使其成为欧拉图25[答案 ]】【篇三：离散数学作业lass=txt>1 ．已知图 g 中有 1 个 1 度结点， 2 个 2 度结点， 3 个 3 度结点， 4 个 4 度结点，则 g 的边数是 15{f ， c} ．3．设 g 是一个图，结点集合为 v，边集合为 e，则g 的结点度数 等于边数的两倍．4．无向图 g 存在欧拉回路，当且仅当 g 连通且 所有结点的度数全为偶数．5．设 g=v ， e 是具有 n 个结点的简单图，若在 g 中每一对结点度数之和大于等于 ，则在 g 中存在一条汉密尔顿路．6．若图 g=v, e 中具有一条汉密尔顿回路，则对于结点集 v 的每个非空子集 s，在 g 中删除 s 中的所有结点得到的连通分支数为 w ，则 s 中结点数 |s| 与 w 满足的关系式为 w?|s| ．7．设完全图 kn 有 n 个结点 (n?2) ，m 条边，当 n 为奇数 时， kn 中存在欧拉回路．8．结点数 v 与边数 e 满足 e=v-1 关系的无向连通图就是树．9．设图 g 是有 6 个结点的连通图，结点的总度数为 18，则可从 g中删去 4 条边后使之变成树．10 ．设正则 5 叉树的树叶数为 17，则分支数为 i = 4 ．二、判断说明题（判断下列各题，并说明理由．）1．如果图 g 是无向图，且其结点度数均为偶数，则图 g 存在一条欧拉回路．． 不正确，图 g 是无向图，当且仅当 g 是连通，且所有结点度数均为偶数，这里不能确定图 g 是否是连通的。

2 ．如下图所示的图 g 存在一条欧拉回路．错误．因为图 g 为中包含度数为奇数的结点．3 ．如下图所示的图 g 不是欧拉图而是汉密尔顿图．1 g★ 形成性考核作业 5 答案 ★解： 错，既不是欧拉图也不是汉密尔顿图，欧拉图要求所有结点度数均为偶数，这里结点 bd 各有三个节点；汉密尔顿图要求每一对结点度数之和大于等于总结点数，这里不满足4 ．设 g 是一个有 7 个结点 16 条边的连通图，则 g 为平面图．。