输入关键词搜索资料
分享
首 页
个人中心
意见反馈
帮助中心
首页 >
国防科学技术大学计算机学院离散数学课后习题答案——图论
国防科学技术大学计算机学院离散数学课后习题答案——图论
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,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
相关资料
Dream Vs Reality 演讲稿
手风琴教学总结(共9篇)
跆拳道段位制与武术段位制的比较与思考-第1篇
南京邮电大学论文任务书
高中英语听说课教学模式设计
高级烟叶分级工理论题库带答案
法律文本中any的译法研究
某城市别墅开盘营销计划
传承与演进——龚贤山水画中的现代性内涵及其对山水画创作的启示(可编辑)
曲线型桥梁支座脱空原因分析及改进措施计算
趣味保龄球中班教案
现行铁路技术标准、规范目录
各官能团的特征吸收峰
海洋生态学课后思考题答案全
小学生一年级可自己阅读带拼音小故事
刺客列传学案答案
电力安全工器具定期实验合同
CA锁(电子印章)办理流程及联系方式
5-2职称指导和培养青年教师证明表格书
公司员工宿舍管理制度(完整版)
热门搜索
沃尔玛物流 -----全球采购的案例分析
如何营造创造积极向上的和谐工作氛围【优质】
【推荐】丽娜拍摄脚本-可编辑
戴尔n5110笔记本一键U盘启动bios教程
牛生产技术练习题
柬埔寨蒙多基里省高西马林区踏查报告
松岭峪地质分析
人教版的配套练习册英语八年级下册
跆拳道学员档案
第十九届海南青少年科技创新大赛项目评审表-海南科学技术协会
读书笔记摘抄好词好句
科力达全站仪参数表及常见技术问题解答
[教学]Z3040摇臂钻床主轴变速箱的三维设计
海尔集团案例分析PPT课件
沃尔玛物流 -----全球采购的案例分析
如何营造创造积极向上的和谐工作氛围【优质】
【推荐】丽娜拍摄脚本-可编辑
戴尔n5110笔记本一键U盘启动bios教程
牛生产技术练习题
柬埔寨蒙多基里省高西马林区踏查报告
松岭峪地质分析
人教版的配套练习册英语八年级下册
跆拳道学员档案
第十九届海南青少年科技创新大赛项目评审表-海南科学技术协会
读书笔记摘抄好词好句
科力达全站仪参数表及常见技术问题解答
[教学]Z3040摇臂钻床主轴变速箱的三维设计
海尔集团案例分析PPT课件
你可能还喜欢
脊髓灰质炎
喉痹(咽炎)中医护理方案
康熙字典笔画-五行属火的字
职业暴露ppt课件
执业药师继续教育药学文献信息检索与技巧(90分)
完整word版20192020年整理民族学通论林耀华版考研复习材料汇编
各种岩石的爆破单位炸药单耗K值表
反思讲座课件
土地增值税纳税申报表三
北师大版四年级上册数学复习计划
金矿露天采矿与剥离工程合同
课件:生物对环境的适应(保护色、警戒色、拟态)
智慧政务云计算中心-存储资源池建设方案
市场营销章节练习题及答案第二章习题(市场营销管理哲学)
Case Analysis 2
呼和浩特抽水蓄能电站简介概要
招商引资试题 (13页)
招商引资试题 (13页)
招商引资试题 (13页)
招商引资试题 (13页)
最新资料
资料动态
专题动态
搜索
热门搜索
离婚协议书
入党申请书
房屋租赁合同
贫困申请书
历史搜索
清空历史搜索