- 1、本文档共13页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
哈工大集合论习题课-第五章 图的基本概念习题课(学生)
第五章 图的基本概念
习 题 课 1
1. 画出具有 6、8、10、…、2n个顶点的三次图;是否有7个顶点的三次图?
2. 无向图有21条边,12个3度数顶点,其余顶点的度数均为2,求的顶点数。
解:设图的顶点为,根据握手定理:,有
,得。
3. 下列各无向图中有几个顶点?
(1)16条边,每个顶点的度为2;
(2)21条边,3个4度顶点,其余的都为3度数顶点;
(3)24条边,各顶点的度数相同。
解: 设图的顶点为,根据握手定理:
(1),即;所以,即有16个顶点。
(2),即,所以。
(3)各点的度数为,则,即,于是
① 若,; ② 若,;
③ 若,; ④ 若,;
⑤ 若,; ⑥ 若,;
⑦ 若,; ⑧ 若,;
⑨ 若,; ⑩ 若,。
4.设图中9个顶点,每个顶点的度不是5就是6。证明中至少有5个6度顶点或至少有6个5度顶点。
证:由握手定理的推论可知,中5度顶点数只能是0,2,6,8五种情况,此时6度顶点数分别为9,7,5,3,1个。以上五种情况都满足至少5个6度顶点或至少6个5度顶点的情况。
5.有个药箱,若每两个药箱里有一种相同的药,而每种药恰好放在两个药箱中,问药箱里共有多少种药?[就是求一个完全图的边数]
6.设是有个顶点,条边的无向图,各顶点的度数均为3。则
(1)若,证明同构意义下唯一,并求;
(2)若,证明在同构的意义下不唯一。
分析:在图论中,对于简单无向图和简单有向图,若涉及到边与顶点的问题,握手定理是十分有用的。
解:(1)由于各顶点的度数均为3,现在有个顶点,条边,所以由握手定理知:,即,故;
又,故,则。
即,,此时所得的无向图如图1所示,该图是4个顶点的简单无向图中边最多的图,即为无向完全图。
对于4个顶点的完全图,在同构意义下,4个顶点的完全图是唯一的。
(2)若,由握手定理:,即。
故,,且每个顶点的度数为3;此时对于简单无向图,6个顶点,9条边及每个度数为3的有如图2所示两个非同构的图;与是非同构的图,所以,度数为3的无向图在同构的意义下是不唯一的。
(a) (b)
图1 图2
7.已知阶简单图中有条边,各顶点的度数均为3,又,试画出满足条件的所有不同构的。
解:由握手定理:,又,即。故
,即,。
此时有,且每个顶点的度数都为3,则不同构的无向图有两个,如图3所示。
图3
8.9个学生,每个学生向其他学生中的3个学生各送一张贺年卡。确定能否使每个学生收到的卡均来自其送过卡的相同人?为什么?
解:否,因为不存在9(奇数)个顶点的3-正则图
习题课2
例3设为正整数,则
(1)为何值时,无向完全图是欧拉图?为何值时为半欧拉图?
(2)为何值时为欧拉图?
(3)为何值时为哈密整图?
(3)为何值时,轮图为欧拉图?
证:(1)一般情况下,不考虑无向图。因此
因为各顶点的度均为,若使为欧拉图,必为偶数,因而必为奇数。即为奇数时,完全图是欧拉图。
若或为奇数时,是半欧拉图。
(2)当均为偶数时,为欧拉图。
(3)当时,为哈密整图。
(4)设为轮图,在中,有个顶点的度为3,因而对于任意
取值,轮图都不是欧拉图。
例1 判断图5所示的图是否为哈密顿图,若是写出哈密顿回路,否则证明其不是哈密顿图。
(a) (b)
图3 图4
例2 给出一个10个顶点的非哈密顿图的例子,使得每一对不邻接的顶点和,均有。
例3 试求中不同的哈密顿回路的个数。
例4 (1) 证明具有奇数顶点的偶图不是哈密顿图;用此结论证明图8所示的图不是哈密顿图。
(2) 完全偶图为哈密顿图的充分必要条件是什么?
证:(1) 设是一个具有奇数顶点的偶图,则的顶点集有一个二划分,
即且有。
不妨设,则有。
由哈密顿图的必要条件可知:不是哈密顿图。
题中所给的图中无奇数长的回路,因而此图是偶图。而且此图中有13个顶
点,因此它不是哈密顿图。
(2) 若,有(1)可知不是哈密顿图;
若,同理有不是哈密顿图。
故是哈密顿图时只有,即。
若,则,由定理知:
是哈密顿图。
例5 菱形12面体的表面上有无哈密顿回路?
例6设是连通图且顶点数为,最小度数为,则中有一长至少为的路。
分析: 采用最长路法,设连通图的最长路为且。再看这条路的端点,端点只能与上的顶
您可能关注的文档
最近下载
- “双带头人”教师党支部书记工作室申报书.docx VIP
- DB37∕T 3452-2018 电梯使用安全风险分级管控和事故隐患排查治理体系建设实施指南.docx
- 2019年度广西优秀水利水电工程勘察设计奖候选项目表【模板】.pdf
- 11-034集控值班员(中级)第二版理论题库.docx VIP
- 传染病监测预警必修和选修答案-2024年全国疾控系统“大学习”活动.docx VIP
- 房地产营销策划 - 2020海南南丽湖度假项目推广方案.docx
- 食品经营许可证食品安全规章制度.docx
- 2016年中考英语一轮复习全册导学案.Doc
- SM-YK控制系统说明书.pdf
- 钱塘江河口水资源配置规划解决方案.doc
文档评论(0)