2004图论复习题答案_第1页
2004图论复习题答案_第2页
2004图论复习题答案_第3页
2004图论复习题答案_第4页
全文预览已结束

下载本文档

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

文档简介

1、图论复习题答案一、 判断题，对打，错打1 无向完全图是正则图。( )2 零图是平凡图。( )3 连通图的补图是连通图. ( )4 非连通图的补图是非连通图。( )5 若连通无向简单图G中无圈，则每条边都是割边。( )6 若无向简单图G是（n，m）图，并且m=n-1，则G是树。( )7 任何树都至少有2片树叶。( )8 任何无向图G都至少有一个生成树。( )9 非平凡树是二分图 。( )10 所有树叶的级均相同的二元树是完全二元树。( )11任何一个位置二元树的树叶都对应唯一一个前缀码。( )12是欧拉图也是哈密顿图。( )13 二分图的对偶图是欧拉图。()14平面图的对偶图是连通图。( )15

2、设G*是平面图G的对偶图，则G*的面数等于G的顶点数。( )二、填空题1无向完全图K6有 15 条边。2有三个顶点的所有互不同构的简单无向图有 4 个。3设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有 10 片树叶。4若连通无向图G是（n，m）图，T是G的生成树，则基本割集有 n-1 个，基本圈有 m-n+1 个。5设连通无向图G有k个奇顶点，要使G变成欧拉图，在G中至少要加 k / 2 条边。6连通无向图G是（n，m）图，若G是平面图，则G有 m-n+2 个面。abcde图1三、解答题1有向图D如图1所示，利用D的邻接矩阵及其幂运算求解下列问题：（1） D中长度等于3的通

3、路和回路各有多少条。（2） 求D的可达性矩阵。（3） 求D的强分图。解： （1）abcde图1M= M2= M3= M4=由M3可知，D中长度等于3的通路有5条，长度等于3的回路有3条。（2）I+M+M2+M3+M4=+ + = D的可达性矩阵为R=B（I+M+M2+M3+M4）=（3）RT = RRT =由矩阵RRT可知，该有向图的强分图有：a， b，d，e， c2 画出有1个4次顶点，2个2次顶点，4个1次顶点的所有非同构的树。3 用Kruskal算法求图2所示带权图的最小生成树，并计算它的权。1294368571011C（T）=2512336227541394 试画出带权为1,2,3, 4,5,7,的最优二元树,并计算它的权。m（T）=（1+2）4+33+（7+4+5）2=535 出席某次国际学术报告会的六个成员被分在一组。他们的情况是：会讲汉语、法语和日语；会讲德语、日语和俄语；会讲英语和法语；会讲汉语和西班牙语；会讲英语和德语；会讲俄语和西班牙语。怎样把他们安排在一张圆桌旁坐下，使得每个人都能和他两旁的人交谈？解 构造无向图，其中，则得无向图如图所示。由该图得一条哈密顿回路：，即为满足要求的安排。四、证明题1 设T是完全二元树，T中有m条弧和t片树叶，证明：m = 2(t-1)。证明： 设完全二元树T有n个顶点。因为它有t片树叶，所以除树叶以外的顶点有个。由于完全二元

人人文库> 全部分类> 教育资料 > 中学教育

温馨提示

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

最新文档

评论

0/150

提交评论