电子科技大学研究生试题《图论及其应用》(参考答案)_第1页
电子科技大学研究生试题《图论及其应用》(参考答案)_第2页
电子科技大学研究生试题《图论及其应用》(参考答案)_第3页
电子科技大学研究生试题《图论及其应用》(参考答案)_第4页
全文预览已结束

下载本文档

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

文档简介

电子科技大学研究生试题《图论及其应用》(参考答案)考试时间：120分钟一．填空题(每题3分，共18分)1．4个顶点的不同构的简单图共有__11___个；2．设无向图G中有12条边，已知G中3度顶点有6个，其余顶点的度数均小于3。则G中顶点数至少有__9___个；3．设n阶无向图是由k(k?2)棵树构成的森林，则图G的边数m=_n-k____;4．下图G是否是平面图？答__是___;是否可1-因子分解？答__是_.5．下图G的点色数______,边色数__5____。图G二．单项选择(每题3分，共21分)1．下面给出的序列中，是某简单图的度序列的是(A)(A)(11123);(B)(233445);(C)(23445);(D)(1333).2．已知图G如图所示，则它的同构图是（D）3．下列图中，是欧拉图的是（D）4．下列图中，不是哈密尔顿图的是（B）5．下列图中，是可平面图的图的是（B）6．下列图中，不是偶图的是（B）7．下列图中，存在完美匹配的图是（B）三．作图(6分)1．画出一个有欧拉闭迹和哈密尔顿圈的图；2．画出一个有欧拉闭迹但没有哈密尔顿圈的图；3．画出一个没有欧拉闭迹但有哈密尔顿圈的图；解：四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。解：由克鲁斯克尔算法的其一最小生成树如下图：权和为：20.五．(8分)求下图G的色多项式Pk(G).解：用公式，可得G的色多项式：。六．(10分)一棵树有n2个顶点的度数为2，n3个顶点的度数为3，…，nk个顶点的度数为k，而其余顶点的度数为1，求1度顶点的个数。解：设该树有n1个1度顶点，树的边数为m.一方面：2m=n1+2n2+…+knk另一方面：m=n1+n2+…+nk-1由上面两式可得：n1=n2+2n3+…+(k-1)nk七．证明：(8分)设G是具有二分类(X,Y)的偶图，证明(1)G不含奇圈；（2）若|X|≠|Y|，则G是非哈密尔顿图。证明：(1)若不然，设C=v1v2…vmv1为G的一个奇圈，不妨设v1?X,则：vm?X,这样推出v1与vm邻接，与G是偶图矛盾。(2)若|X|≠|Y|，设|X|?|Y|，则?(G-Y)??Y?,由H图的必要条件，G为非哈密尔顿图。八．（8分）设G是边数m小于30的简单连通平面图，证明:G中存在顶点v，使d(v)?4.证明：若不然，则对任意的v?V(G),有d(v)?5，这样，一方面有：2m=?d(v)?5n(1)另一方面，G为简单连通平面图，有：m?3n-6(2)由(1),,把该式代入(2)得：m?30,与题设矛盾。九．(8分)证明：每个没有割边的3正则图都有完美匹配。证明：设G是没有割边的3正则图，S是V的真子集，用G1,G2,…,Gn表示G-S的奇分支，并设mi是一个顶点在Gi中，另一个端点在S中的那些边的条数。由于G是3正则图，所以1?i?n(1)且（2）由(1)式，是奇数。又由于G没有割边，所以mi?1

人人文库> 全部分类> 行业资料 > 各类标准

温馨提示

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

最新文档

评论

0/150

提交评论