(图论B)重庆邮电大学研究生考卷.doc_第1页
(图论B)重庆邮电大学研究生考卷.doc_第2页
(图论B)重庆邮电大学研究生考卷.doc_第3页
全文预览已结束

下载本文档

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

文档简介

重庆邮电大学研究生考卷学号 姓名 考试方式 班级 2010级 考试课程名称 图论及其算法(B) 考试时间： 年 月 日题号一二三四五六七八九十十一十二总分得分一、解答题（每题10分，共60分）1、(10分)求有向图D=的可达矩阵, 其中V= v1,v2 ,v3 ,v4 ，E= (v1,v2),(v2,v3), (v2,v4),(v3,v2), (v3,v4), (v3,v1), (v4,v1) ，(vi,vj)表示vi是起点，vj是终点的有向边。并判定该图的类型。（图的类型有很多种，如简单图、非简单图和多重图等，连通图与非连通图，欧拉图与非欧拉图，哈密顿图与非哈密顿图等，这样考容易产生歧义，能否考具体点）2、（10分，每题5分）(1)画一个无向简单欧拉图(既是简单图,又是欧拉图)，使它具有偶数个顶点，偶数条边。 (2)证明 若二部图是哈密顿图，则必有.(5分)3、(10分)一个7阶简单连通图,其中一个顶点度数为6,其余顶点度数为4，试解决如下两个问题:(1)画出该图; (2)判断该图的平面性.4、（10分）已知一颗无向树有三个三度点，一个二度点，其余的皆为一度点。试求中的叶片数。5、（10分）求带权为1,2,3,3,5,7,8,11的最优二叉树。6、（10分）通过布尔变量的运算，求下图的极小点覆盖。v6v7v1v3v4v5v2G二、证明题（每题10分，共40分）7、证明在n（n2）个人的团体中，总有两个人在此团体中恰好有相同个数的朋友。8、(1)证明：一个平面图的对偶图是欧拉图当且仅当的每个面均由偶数条边围成.(5分)(2)证明:任意极大平面图是连通的.(5分)9、(10分)Floyd算法可以用来求一个加权连通图中任意两点间的最短距离。为介绍Floyd算法，先定义矩阵的两种运算.定义1 已知矩阵,规定,其中, 。定义2 已知矩阵,规定,其中,。Floyd算法：已知阶加权简单图，设是图的边权矩阵，即（若是有向图，则），若结点到结点无边相连时，则。依次算出，及，其中，.由定义可知，表示从结点到经边的路径中的长度最短者，就是结点到的所有路径中的长度最短者。证明 Floyd算法的时间复杂性
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

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

最新文档

评论

0/150

提交评论