输入关键词搜索资料
分享
首 页
个人中心
意见反馈
帮助中心
首页 >
国防科学技术大学计算机学院离散数学课后习题答案——图论
国防科学技术大学计算机学院离散数学课后习题答案——图论
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. ...
国防科学技术大学计算机学院离散
数学
数学高考答题卡模板
高考数学答题卡模板
三年级数学混合运算测试卷
数学作业设计案例
新人教版八年级上数学教学计划
课后习题
答案
八年级地理上册填图题
岩土工程勘察试题
省略号的作用及举例
应急救援安全知识
车间5s试题及答案
——图论 第七章 图论 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,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
相关资料
钱律师解读新《婚姻法》第17条
初雪初晴作文
【精选资料】2015年安亭小学教育科研工作总结
潇洒走一回 叶倩文 ukulele谱 吉他谱 指弹谱
双褶贝母兰的重新发现及其植物地理学意义
凤凰古城被大雨洪水灌淹 水位很深灯杆被淹只留灯罩
柱纵向钢筋单排最大根数(史上最全、新规范、考虑净保护层厚度)
课题实施计划
初中物理教学案例
学生主动认错检讨书1000字
电大本科《公共部门人力资源管理》题库及答案
学生日常行为习惯星级评定表
笑对的近义词
忆儿时(初一期末记叙文阅读题)
霍夫曼主题演讲文字稿——以存在主义视角来看待苦难、丧失和转化
公司业务员人事变动通知函模版
高考志愿填报表样本
我们的节日(100字作文)
语言艺术幼儿基础教学说课
一年级练习题
热门搜索
巡视检查记录表-(塔吊加节安装)
麦当劳回归本源:汉堡加薯条(英汉)
氢氧化钠安全技术说明书
数字对象标识符系统在数字版权保护中的应用研究
云南初中学生物理化学生物学试验操作考试方案
直流稳压电源电路的设计实验报告
如棉如絮的朵朵白云作文300字
移动通信专业学生职业生涯规划
苏轼《水调歌头》复习课程
华为E9000刀片服务器培训
2011年最新款火力少年王之舞动火力 飞火流星 675611
作文那一天我真高兴
国内外变频器品牌、产地、特点
the virtual library - aegean
巡视检查记录表-(塔吊加节安装)
麦当劳回归本源:汉堡加薯条(英汉)
氢氧化钠安全技术说明书
数字对象标识符系统在数字版权保护中的应用研究
云南初中学生物理化学生物学试验操作考试方案
直流稳压电源电路的设计实验报告
如棉如絮的朵朵白云作文300字
移动通信专业学生职业生涯规划
苏轼《水调歌头》复习课程
华为E9000刀片服务器培训
2011年最新款火力少年王之舞动火力 飞火流星 675611
作文那一天我真高兴
国内外变频器品牌、产地、特点
the virtual library - aegean
你可能还喜欢
电厂脱硫石灰石用量计算公式
2023年上海市中考地理真题(含解析)
案例剖析材料油田公司发文
家装水电验收表
2017年江西省“三校生”对口升语文学考试说明
《电器柜设计规范》PPT课件模板
胞二磷胆碱钠注射液说明书
供应室预真空压力蒸汽灭菌器论文:供应室预真空压力蒸汽灭菌器的管理
我不怕鬼
【doc】营口地区盖州市万福镇贵子沟村赤山山城考察报告
县级部门、乡镇交办信息回复单
Bios设置全程图解
微机原理填空选择判断题库
河南省新乡市2014-2015学年高二下学期终结性评价考试语文试题(图片版)
JGJ130-2019建筑施工扣件式钢管脚手架安全技术规范10页word文档
河雍中心校教学常规检查通报.doc
坦陀罗(谭崔)的性艺术
坦陀罗(谭崔)的性艺术
坦陀罗(谭崔)的性艺术
坦陀罗(谭崔)的性艺术
最新资料
资料动态
专题动态
充电站使用安全管理指南
北工大 测量放大器
园林植物景观设计网上作业题
重庆方言神翻译对照表
六年级上册美术课件-《美术中的比例知识》-北京课改版共26张PPT
贵州省黔西南州2020年中考英语试题(原卷版)中考真题原题
购房合同表格
孟津县双语实验学校防溺水教育活动记录[1]
小学音乐_蓝色的雅特朗教学设计学情分析教材分析课后反思
公共洗衣机使用管理制度
小学科学新课程标准知识测试题
文件收发记录-表格
坚持就是胜利作文
教育课题研究中常用的理论依据
绝望主妇英语对白desperatehousewivesse第一季第一集所有英文对白
储气罐安装施工方案
2014-2018年中国房地产经纪行业投资前景及发展趋势分析报告
青岛版小学数学四年级上册口算题
崔国萍《成本管理会计》期末复习参考题及答案
优秀商户评选颁奖典礼活动方案
计划生育后遗症鉴定
搜索
热门搜索
离婚协议书
入党申请书
房屋租赁合同
贫困申请书
历史搜索
清空历史搜索