输入关键词搜索资料
分享
首 页
个人中心
意见反馈
帮助中心
首页 >
国防科学技术大学计算机学院离散数学课后习题答案——图论
国防科学技术大学计算机学院离散数学课后习题答案——图论
2017-10-15
10页
doc
27KB
123阅读
is_266065
暂无简介
举报
国防科学技术大学计算机学院离散数学课后习题答案——图论国防科学技术大学计算机学院离散数学课后习题答案——图论 第七章 图论 7.1 1. a) 非简单图;(有自圈) b) 非简单图;(有自圈) c) 简单图。 3. 因为n个顶点的有向简单图中,每两个不同顶点之间最多有两条边,因此其边数最多 为:2。 2C,n(n,1)n 4. 利用定理7.1.3 因为任何图均有偶数个奇结点,而3度正则图的所有结点度数均为3,即均为偶结点。所以,3度正则图必有偶数个奇结点。 5. 利用定理7.1.3 1, 2, 1 5 3 6, 3, 6 2 4 5, 4, 6. ...
国防科学技术大学计算机学院离散数学课后习题答案——图论 第七章 图论 7.1 1. a) 非简单图;(有自圈) b) 非简单图;(有自圈) c) 简单图。 3. 因为n个顶点的有向简单图中,每两个不同顶点之间最多有两条边,因此其边数最多 为:2。 2C,n(n,1)n 4. 利用定理7.1.3 因为任何图均有偶数个奇结点,而3度正则图的所有结点度数均为3,即均为偶结点。所以,3度正则图必有偶数个奇结点。 5. 利用定理7.1.3 1, 2, 1 5 3 6, 3, 6 2 4 5, 4, 6. 证明:假设六个人分别为:a, b, c, d, e, f。则分两种情况讨论。 ? 若a认识的人大于等于3个,即b, c, d, e, f中至少有3个与a认识。不妨设c, d, e与a 认识,则c, d, e必定互相不认识。(否则,c, d, e中互相认识的两人与a就构成三个人互相都 认识。产生矛盾。) ? 若a认识的人小于3个,即b, c, d, e, f中至少有3个与a不认识。不妨设b, c, d与a均不 认识。则因为没有3个人彼此都认识,所以b, c, d中必有两个人互相不认识。假设c, d互相 不认识,则a, c, d三个人彼此都不认识。 8. a ) 图中有一个与两个度数为3的结点邻接的结点,其度数也为3。 而b ) 图中没有任何一个度数为3的结点与两个度数为3的结点邻接。 所以,a ) 与b ) 不同构。 - 1 - 第七章 图论 9. b ) 图的中心结点其入度为0,而a ) 图中没有入度为0 的结点。所以两图不同构。 10. n阶简单无向图的结点度数不可能超过n-1,即取值范围为:{0, 1, 2, … , n-1}。 证明n(n>1)阶图中必有两个结点度数相等,抽屉原则应该可以使用,但n个结点,n种度数可能,抽屉原则似乎用不上。但我们发现,若图中有孤立点,则所有结点的度数只可能从 0到n-2中取值,即只有n-1种可能性。于是分两种情况: ? 若G中无孤立点(度数为0的结点),则G中n个结点的度数只能从1到n-1中取值。n个结点,n-1种可能的度数取值,由抽屉原则,G中必有两个结点的度数相等。 ? 若G中有孤立点,则G中n个结点的度数只能从0到n-2中取值。n个结点,n-1种可能的度数取值,由抽屉原则,G中必有两个结点的度数相等。 11. 根据定理7.1.1可知无向图中所有结点的度数和是边数的两倍。所以, ,即。 kn,(k,1)(n,n),2mn,(k,1)n,2mkkk 7.2 2. 显然G[V,]重任意两点之间必定互有有向边,并且无自圈、无平行边。 4. (1) 自反的; (2) 反对称的、传递的; (3) 自反的、对称的、传递的; (4) 自反的、传递的; (5) 无; (6) 对称的; (7) 自反的、反对称的、传递的; (8) 对称的; (9) 对称的; (10) 反对称的; (11) 自反的、反对称的; (12) 反对称的、传递的。 4. a) A上共有2n,n2个不相同的自反关系; 2n,nb) A上共有2个不相同的反自反关系; 2n,n 2c) A上共有2个不相同的对称关系; - 2 - 第七章 图论 2n,nn2d) A上共有个不相同的反对称关系; 2,3 ne) A上共有2个不相同的既是对称的又是反对称的关系; 2.3 1. 最多能有n(A) 个元素为1。 2. 证明: -1i) R , R为A上包含R的最小对称关系 -1-1? R , R , R。所以,R,R包含R。 -1-1? 因为对于任意
, R , R,有
, R或
, R。 -1-1若
, R,则
, R;若
, R,则
, R。 -1-1因此,
, R , R。所以,R,R为A上的对称关系。 ? 设R,为任意的A上包含R的对称关系,则 -1-1对于任意
, R , R,有
, R或
, R。 若
, R,由于R,包含R,所以
, R,; -1若
, R,则
, R,由于R,包含R,所以
, R,,而R,对称,所以
, R,。 -1 因此,总有
, R,。所以,R , R, R,。 -1由???可知,R , R为A上包含R的最小对称关系。 -1ii) R , R为A上包含在R中的最大对称关系 -1-1? R , R , R。所以,R , R包含在R中。 -1-1? 因为对于任意
, R , R,有
, R且
, R。 -1-1
, R,所以
, R;
, R,所以
, R。 -1-1因此,
, R , R。所以,R , R为A上的对称关系。 ? 设R,为任意的A上包含在R中的对称关系,则 对于任意
, R,,由于R,包含在R中,所以
, R; -1又由于R,对称,所以
, R,,而R,包含在R中,所以
, R,因此,
, R; -1-1因此,总有
, R , R。所以,R , R,R。 -1由???可知,R , R为A上包含在R中的最大对称关系。 2.4 1. R , R = {
}; R , R = {
,
}; 2112 22R = {
,
,
}; R = {
,
}; 12 2. m = 1, n = 16。 - 3 - 第七章 图论 4. A = {1, 2, 3} 令R = {<1, 2>, <1, 3>};R = {<2, 2>};R = {<3, 2>};则 123 R , ( R , R) = ,;( R , R ) , ( R , R) = {<1, 3>}; 123 1213 所以,R , ( R , R) , ( R , R ) , ( R , R) 。 123 1213 令R = {<2, 2>};R = {<2, 3>};R = {<2, 1>, <3, 1>};则 234 ( R , R) , R= ,;( R , R ) , ( R , R) = {<2, 1>}; 23 4 2434 所以,( R , R) , R, ( R , R ) , ( R , R) ; 23 4 2434 5. a) 正确。 b) 不正确。令A = {1, 2},则R = {<1, 2>}, R = {<2, 1>}都是反自反的,但R , R={<1, 1>}1212 不是反自反的。 c) 不正确。令A = {1, 2, 3},则R = {<1, 2>, <2, 1>}, R = {<2, 3>, <3, 2>}都是对称的,但12 R , R= {<1, 3>}不是对称的。 12 d) 不正确。令A = {1, 2, 3},则R = {<1, 2>, <3, 1>}, R = {<2, 3>, <1, 1>}都是反对称的,12 但R , R= {<1, 3>, <3, 1>}不是反对称的。 12 e) 不正确。令A = {1, 2, 3},则R = {<1, 2>, <3, 1>, <3, 2>}, R = {<2, 3>, <1, 1>}都是传递12 的,但R , R= {<1, 3>, <3, 1>, <3, 3>}不是传递的。 12 7. 证明: st s+ksktkt+ka) 对于任意k , N,因为R = R,所以R = R ,R = R ,R = R 。 b) 用关于k的归纳法证明。 s+is+i i) 当k=0时,R = R。所以命题成立。 s + mp + is + i ii) 假设当k=m时命题成立,即R = R。 s + (m+1) p + is + p + mp+ it + mp + itmp+i smp+i s + mp + i 则当k=m+1时,因为R=R=R=R ,R=R ,R=R。 s + (m+1) p + is + mp + i s + i 由归纳假设,R = R= R。 s + kp + is + i 由i) ii)可知对于任意k, i , N,均有R = R 。 k01t-1d) 若k , t-1,则R , {R, R, …, R}; 若k , t,则k = s + (t-s)q + r,即k = s + pq + r;(其中,q, N, 0 , r < t-s = p) ks + pq + rs + r01t-1 此时,由b)可知R = R = R , {R, R, …, R}。 k01t-1 所以,若k , N,则R , {R, R, …, R}。 2.5 2. 使t (R , R) , t ( R ) , t ( R ) 的R 和R 的具体实例如下: 121212 A = {1, 2},R = {<1, 2>},R = {<2, 1>}; 11 则t ( R ) = R ,t ( R ) = R ,t (R , R) = {<1, 2>, <2, 1>, <1, 1>, <2, 2>}, 112212 故真包含。 4. b) 使s (R , R) , s ( R ) , s ( R ) 的R 和R 的具体实例如下: 121212 - 4 - 第七章 图论 A = {1, 2},R = {<1, 2>},R = {<2, 1>}; 11 则s ( R ) = s ( R ) = {<1, 2>, <2, 1>},s (R , R) = s(,) = ,。 1212故真包含:s (R , R) , s ( R ) , s ( R )。 1212 b) 使t (R , R) , t ( R ) , t ( R ) 的R 和R 的具体实例如下: 121212A = {1, 2, 3},R = {<1, 2>, <2, 1>},R = {<1, 3>, <3, 1>}; 11则t ( R ) = {<1, 2>, <2, 1>, <1, 1>, <2, 2>},t ( R ) = {<1, 3>, <3, 1>, <1, 1>, <3, 3>}, 12t (R , R) = s(,) = ,。 12 故真包含:t (R , R) , t ( R ) , t ( R )。 1212 6. 令A = {1, 2},R = {<1, 2>},则 ts(R) = t ({<1, 2>, <2, 1>}) = {<1, 2>, <2, 1>, <1, 1>, <2, 2>} st(R) = s ({<1, 2>}) = {<1, 2>, <2, 1>} 所以,st(R) , ts(R)。 2.6 1. a) 正确; b) 正确; c) 不正确;(不自反) d) 不正确;(不自反) e) 不正确;(不一定对称) f) 正确。 2. R的所有极大相容类为:{x, x, x},{x, x, x},{x, x, x},{x, x, x}。 123136345356 2n,n 23. A上共有2个不相同的相容关系。 2.7 1. a) 不正确;(不自反) b) 不正确;(不自反) c) 不正确;(不自反) d) 不正确;(不传递,< -1, 0 > , R, < 0, 1 > , R, 但<-1, 1> , R) e) 不正确;(不对称) f) 不正确;(不对称) g) 不正确;(不传递) h) 正确; i) 不正确。(不自反,i = 10k时,
, R) - 5 - 第七章 图论 2. 不对。 应加上条件:对于任意x,A,总存在y,A使得
, R。 3. 证明: ? 已知条件:若
, R,
, R,则
, R。 先证对称性:若
, R,则由于R自反,所以
, R,由上式有
, R。 所以R对称。 再证传递性:若
, R,
, R,则因为R对称,所以
, R。由已知条件,因为
, R且
, R,所以
, R。 所以R传递。 因此,R时等价关系。 ? 已知条件:R是等价关系。 若
, R,
, R,则因为R对称,所以
, R。又由于R传递,所以,
,R。 因此,若
, R,
, R,则
, R。 2.8 1. a) 半序; b) 半序、全序、良序; c) 无;(不是反对称的) d) 无;(不是传递的) e) 半序; f) 无;(不是传递的) g) 无;(不是传递的) h) 拟序。 4. 设R是集合A上的二元关系,证明: a) R是A上的半序,当且仅当R , R-1* = II且R = R。 A 自反、反对称 ___________ _______传递 -1+b) R是A上的拟序,当且仅当R , R = , 且R = R。 反自反 ___________ _______传递 6. a) 断言中为真的有:xRx, xRx。 4111 b) P的最小元:无;P的最大元:x; 1 P的极小元:x和x;P的极大元:x。 451 c) {x, x, x}的上界:x;下界:x;上确界:x;下确界:x。 2341414 {x, x, x}的上界:x, x;下界:无;上确界:x;下确界:无。 345133 {x, x, x}的上界:x;下界:x;上确界:x;下确界:x。 1231414 - 6 - 第七章 图论 7. a) < I, , >中的非空子集I无最小元。 b) < I, |>(“|”为整除关系)中的非空子集{x | x >4}无最大元。 + c)
中的非空子集(0, 1)由下确界0,但无最小元。 d) 书上例4中的非空子集{4}有上界8和12,但无上确界。 8. 归纳法。 9. 归纳法。 - 7 -
/
本文档为【国防科学技术大学计算机学院离散数学课后习题答案——图论】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
相关资料
电厂化学题库
电影著作权评估
FTA方法步骤及程序
一幅漫画的启示_五年级漫画作文400字
2018高考英语一轮总复习 第一部分 教材知识梳理 Unit 2 Cloning课件 新人教版选修
关于延期缴纳行政罚款的请示(1)
机务行车安全管理规则
2021盐城一小教育集团苏教版一年级数学下册期中试卷
一年级阅读答案
地方标准制修订计划任务书模板
学习动机策略问卷
引上光缆是光缆工作量的一种名称
因公司管理制度不严格导致公司倒闭的案例 (12页)
创意卡通风校园暴力课程PPT课件
欢天喜地歌词串词朗诵词
头孢唑啉对安装心脏起搏器并发感染的预防作用
中国签证邀请函模板
高分子材料加工厂设计(徐德增)化纤厂设计举例(复习
幼儿园语言教育专题(省)形考2答案
住宅小区物业投标文件
热门搜索
富士伺服驱动器参数设定及基本操作。
丰田陆地巡洋舰独有的AHC系统
管理会计学本量利分析案例(附答案)
校园安全隐患排查记录表模板
事情英语怎么说
浙江省温州市乐清市乐成镇2017-2018学年八年级数学上学期期中试题(实验B班) 浙教版
案情摘要
《天狗》教案 教案教学设计
环氧树脂柔性固化剂研究进展
水利水电建设施工合同示范文本
砂轮机安全操作规程
最新带电检测技术精品课件
(完整版)英语各种词性前后缀及习题
工厂精细化管理
富士伺服驱动器参数设定及基本操作。
丰田陆地巡洋舰独有的AHC系统
管理会计学本量利分析案例(附答案)
校园安全隐患排查记录表模板
事情英语怎么说
浙江省温州市乐清市乐成镇2017-2018学年八年级数学上学期期中试题(实验B班) 浙教版
案情摘要
《天狗》教案 教案教学设计
环氧树脂柔性固化剂研究进展
水利水电建设施工合同示范文本
砂轮机安全操作规程
最新带电检测技术精品课件
(完整版)英语各种词性前后缀及习题
工厂精细化管理
你可能还喜欢
国内异地遗体接运审批信息表
高考中考誓师方案(含解说词大量誓言49页)
应变片贴法注意事项
初一上册语文阅读题
华为集团总裁任正非致新员工的一封信
蒙娜丽莎之约教案(10篇)
SolidWorks安装时ToolBox不能修改安装位置的解决方案
2023年上海市青浦区金泽镇王港村社区工作人员考试模拟题含答案
外国语学院2017年暑期社会实践报告表格模版
MIDAS计算弯桥及汽车荷载方法
防水工技能试题
如何实现网络唤醒开机Wake+On+LAN
种子检验人员专业知识考试 试卷 (田间检验员)
农业银行银行电子卡交易提醒代码[常识]
2013长春大学 软件工程学院毕业设计选题参考表3
基于COMSOL软件下截锥体电阻的计算
监督考勤管理制度
监督考勤管理制度
监督考勤管理制度
监督考勤管理制度
最新资料
资料动态
专题动态
患者告知制度
洗罐安全操作规程
潘晓勇_温州“走路老板”潘晓勇-从数亿身家到欠债3亿
金属加工原理
2021小学寒假家庭劳动教育活动方案及清单(详细版)
富士康仓库管理作业表单
冒菜店策划书
眼科疾病医疗护理-PPT课件
机动翻斗车性能参数
钻井作业副防喷管线应急预案 --钻井现场施工作业文件
责任制整体护理工作规范及自查表
石灰消解技术交底【精选文档】
七年级上册英语第五单元全英语教案
钢丸化学成分表
患者告知制度
洗罐安全操作规程
潘晓勇_温州“走路老板”潘晓勇-从数亿身家到欠债3亿
金属加工原理
2021小学寒假家庭劳动教育活动方案及清单(详细版)
富士康仓库管理作业表单
冒菜店策划书
眼科疾病医疗护理-PPT课件
机动翻斗车性能参数
钻井作业副防喷管线应急预案 --钻井现场施工作业文件
责任制整体护理工作规范及自查表
石灰消解技术交底【精选文档】
七年级上册英语第五单元全英语教案
钢丸化学成分表
搜索
热门搜索
离婚协议书
入党申请书
房屋租赁合同
贫困申请书
历史搜索
清空历史搜索