第六章习题参考答案_第1页
第六章习题参考答案_第2页
第六章习题参考答案_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第六章习题参考答案基础习题1n个结点的有向完全图中，哪些是欧拉图？为什么？答:n个结点的有向完全图都是欧拉图，因为有向完全图中每个结点和其他n-1个结点之间都有两个方向相反的有向边，因此每个结点的出度和入度都等于n-1。2判断图能否一笔画出，本质上是判断该图是否有欧拉通路。由定理6.1及推论6.1知（a）不能一笔画出，（b）（c）（d）能一笔画出3本题答案很多，如4在第3题图中，把无向圈换成有向圈。56在第4题图中，把无向圈换成有向圈。7将a、b、c、d、e、f、g七个人看作7个结点，如果其中两个人能够交谈，就在对应字母之间连一条线，得到下图该图为二部图，其中b,d,f为一组，g,a,c,e为一组，同一组中没有两个人能互相交谈。8（a）是偶图，V1=（b）不是偶图，因为图中存在长度为3的回路。（c）是偶图，V1=（b）不是偶图，因为图中存在长度为3的回路。9（a）有2个面，如图所示，R0的边界为初级回路abcdafaea,degR0=8。R1的边界为初级回路abcda，（b）有2个面，如图所示，R0的边界为初级回路abefgfeca，degR0=8。R1的边界为初级回路abecdca，提升习题1由于Kn的所有结点的度数均为n-1，要使n-1为偶数，n必须为奇数，故当n≥1且为奇数时，无向完全图Kn是欧拉图。要使无向完全图中仅存在欧拉通路而不存在欧拉回路就必须使图中有且仅有两个奇度数结点，其他均为偶度数结点。由于Kn2除K2不是哈密顿图之外，Kn(n≥3)全是哈密顿图，当n3彼德森图每个结点的度数为3，要使其变成欧拉图，要求每个结点的度数为偶数，故至少添加5条边才能构成欧拉图。至少加两条边才能构成哈密顿图。4做无向图G=(V,E)，其中V={v1,v2,v3,v4,v5根据条件有，，从而根据欧拉定理有。6做无向图G=<V,E>，其中，V={a,b,c,d,e,f,g)E={(u,v)|u,v∈V且u与v会讲同一种语言}，则图G如图所示。于是，能否将这7个人排坐在圆桌周围使得每个人能与两

人人文库> 全部分类> 教育资料 > 考试试卷

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论