




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
离散数学业
姓学得
名号分离数图部形性核面业本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业。一、填题1.已知图G中有个1结点,22度结点,3个3度结点,4个4结点,则的边数是
15
.2.设给定G如右由图所示,则图的点割集是{f}
.3.设G是一个图,结点集合为V,边集合为,则的结点
度数之和
等于边数的两倍.4.无向图G存在欧拉回路,当且仅当G连通且度.
等于出5.设G=<,E>是具有个结点的简单图,若在G每一对结点度数之和大于等于
,则在中存在一条汉密尔顿路.6.若图E>中有一条汉密尔顿回路,则对于结点集V每个非空子集S,在中删除S中的所有结点得到的连通分支数为,则中结点数S|与W满足的关系式为7.设完全K有个结点(n,条边,当
.n奇数
时,K
中存在欧拉回路.1/8.结点数与边数e足树.
e=v-1
关系的无向连通图就是9.设图G是有6个结点的连通图,结点的总度数为,则可从G中删去4
条边后使之变成树.10设正则5树的树叶数为,则分支数为i=
.二、判说明题(判断下列各题,并说明理由.)1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路..(1)不正确,缺了一个条件,图G应该是连通图,可以找出一个反例,比如图是一个有孤立结点的图。2.如下图示的图G在一条欧拉回路.(2)不正确,图中有奇数度结点,所以不存在是欧拉回路。3.如下图示的图G是欧拉图而是汉密尔顿图.解:正确因为图中结点,b,d,f的度数都为奇数,所以不是欧拉图。2/13451231345123234354512534如果我们沿着(a,d,g,f,e,b,c,a),这样除起点和终点是a,我们经过每个点一次仅一次,所以存在一条汉密尔顿回路,是汉密尔顿图4.设G是一个有个结点16边的连通图,则为平面图.解:(1)错误假设图是连通的平面图,根据定理,结点数v,边数为,应满足e小于等于,但现在小于等于3*7-6,显示不成立。所以假设错误。5.设G是一个连通平面图,且有个结点条边,则有7个面.(2)正确根据欧拉定理,有,边数,结点数e=6,代入公式求出面数r=7三、计题1.设=<,E>,V={v,v,,v,v}E={(,,,v),(,v),,v),,v),,v)}试(1)给出的图形表示;(3)求出每个结点的度数;解:(1)v
(2)写出其邻接矩阵;(4)画出其补图的图形.v
vv
v3/1253412534(2)邻接矩阵为
(3)
v结点度数为,v结度数为,结度数为3,结度数为2v结度数为212345(4)补图图形为vv
vv
v2.图GV,E>,其中={,b,,d,e,E={(,b),(a,ca,eb,d),(,e),c,e),(c,d),(,e)},对应边的权值依次为2、1、2、3、6、1、4及5,试(1)画出G的图形;(2)写出G的邻接矩阵;(3)求出G权最小的生成树及其权值.(1)G的图形如下:4/(2)写出G的邻接矩阵(3)G权最小的生成树及其权值3.已知带图G右图所示.(1)求图的最小生成树;
(2)计算该生成树的权值.解:(1)最小生成树为5/1
275
3(2)该生成树的权值为(1+2+3+5+7)=184.设有一权为2,5,7,31,试画出相应的最优二叉树,计算该最优二叉树的权.6/63
311
171
75
523权为
2*5+3*5+5*4+7*3+17*2+31=131四、证题1.设G是一个阶无向简单图,n大于等于3的奇数.证明图与它的补G中的奇数度顶点个数相等.证明:GEGEn无向完全K的边删去n所得到的.所以对于任意结u,在的度数之和等于uK中n的度数.由于n大于等于3的奇数,从而的每个结点都是偶数度的nn(2)),于是在中是奇数度结点,则它G中也是奇数度结点.故图与它的补中的奇数度结点个数相等.7/2.设连通Gk个奇数度的结点,证明在图G中至少要添加能使其成为欧拉图.
条边才证明:由定理,任何图中度数为奇数的结点必是偶数,可知k偶
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 光伏项目调试与验收管理
- 2025年区块链在跨境支付中的跨境支付跨境支付技术人才培养报告
- 生鲜供应链中的食品安全与损耗控制研究报告
- 2025年音频切换台项目合作计划书
- 基层医疗卫生机构信息化建设中的信息化与慢性病管理报告2025
- 绿色消费理念在2025年体育产业的传播与消费者行为分析报告
- 2025年电器附件真空断路器项目合作计划书
- 合理的论文写作计划设计
- 2025年超低频振动标准项目发展计划
- 2025年全国安全生产月活动《安全知识》培训考试题库及答案
- (2025)燃气调压器项目可行性研究报告写作范本(一)
- 《幕墙工程设计与施工技术》课件
- 网络安全态势建模-深度研究
- HY/T 0382-2023海岸带生态系统减灾功能评估技术导则红树林和盐沼
- 无人机基础知识
- 2025年上半年廉政工作总结(二篇)
- 【MOOC】大学英语1-华东交通大学 中国大学慕课MOOC答案
- 2024年患者用药指导知识技能竞赛(省选拔赛)参考试题库(含答案)
- 轿车运输合同模板
- 工程数据分析与应用
- 专业汽车维修工2024年OBD培训
评论
0/150
提交评论