- 1、本文档共7页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
2015电子科技大学研究生试卷答案
一.填空题(每空3分,共15分)
1.不同构的3阶简单图的个数为__4___。
2.图1中的最小生成树的权值为__20____。
3.基于图2的最优欧拉环游的总权值为。
4.图3中块的个数为。
5.图4中强连通分支的个数为。
二.单项选择(每题3分,共15分)
1.关于图的度序列,下列命题错误的是( D )
(A) 同构的两个图的度序列相同;
(B) 非负整数序列是图的度序列当且仅当是偶数;
(C) 如果非负整数序列是一棵树的度序列,那么序列中至少有两个整数的值为1;
(D). 如果非负整数序列是简单图的度序列,那么在同构意义下只能确定一个图。
2.关于阶简单图的邻接矩阵,下列说法错误的是( C )
(A) 矩阵的行和等于该行对应顶点的度数;
(B) 矩阵所有元素之和等于该图边数的2倍;
(C) 不同构的两个图,它们的邻接矩阵特征谱一定不同;
(D) 非连通图的邻接矩阵一定可以表示为准对角矩阵形式。
3.关于欧拉图,下面说法正确的是( B )
(A) 欧拉图存在唯一的欧拉环游;
(B) 非平凡欧拉图中一定有圈;
(C) 欧拉图中一定没有割点;
(D) 度数为偶数的图一定是欧拉图。
4.关于哈密尔顿图,下列命题错误的是( B )
(A)设是的简单图,若其闭包是完全图,则是哈密尔顿图;
(B) 若阶单图的闭包不是完全图,则它一定是非哈密尔顿图;
(C)若G是哈密尔顿图,则对于的每个非空顶点子集,均有;
(D) 若G是的非H单图,则G度弱于某个图。
5.关于偶图,下列说法错误的是( B )
(A) 偶图中不存在奇圈;
(B) 非平凡偶图的最大匹配是唯一的;
(C) 正则偶图存在完美匹配;
(D) 偶图中,最大匹配包含的边数等于最小点覆盖包含的顶点数。
三、 (20分)在一个赋权完全图中找到一个具有最小权值的哈密尔顿圈,称这种圈为最优哈密尔顿圈。(1)、用边交换技术方法求出图5中基于初始圈的近似最优哈密尔顿圈;(2)、如何获取最优哈密尔顿圈权值的一个下界?以图5为例进行说明。
解:(1)
由此获得的一个近似最优解的权值为192.
(2)、假设是最优哈密尔顿圈,则对于赋权完全图中任意一点,必然是的一条哈密尔顿路,因此它也是的一棵生成树。由此,若是的一棵最小生成树,同时是中与点相关联的两条边,使得它们的权值之和尽可能小,则,即获得最优圈的一个下界。
例如,在图5中,取顶点,求出的一棵最小生成树为
而与Ny点相关联的两条权值之和尽可能小的边是LNy与LMc,其权值之和为35+21=56.由此获取最优解的一个下界为178.
四,(10分)。矩阵的一行或一列称为矩阵的一条线,利用哥尼定理证明:布尔矩阵中,包含了所有“1”的最少数目,等于具有性质“任意两个1都不在同一条线上的1的最大数目”。( 注:哥尼定理:在偶图中,最大匹配包含的边数等于最小点覆盖包含的顶点数)
证明:设布尔阵是n行m列矩阵,把它模型为一个偶图如下:每行每列分别用一个点表示,X表示行点集合,Y表示列点集合,两点连线。当且仅当该行该列元为1.
于是,包含了所有“1”的线的最少数目对应偶图中的最小点覆盖数。而具有性质“任意两个1都不在同一条线上的1的最大数目” 对应偶图的最大匹配包含的边数。由哥尼定理,命题得到证明。
五.(10分) 求证:设是n阶的具有m条边的简单连通平面图,则:。
证明:由于是n阶的具有m条边的简单连通平面图,所以每个面的次数。由得到:。
由连通平面图的欧拉公式:,将代入欧拉公式得到
。
六.(20分) 一家公司计划建造一个动物园,他们打算饲养下面这些动物:狒狒(b)、狐狸(f)、山羊(g)、土狼(h)、非洲大羚羊(k)、狮子(l)、豪猪(p)、兔子(r)、鼩鼱(s)、羚羊(w)和斑马(z)。根据经验,动物的饮食习惯为:狒狒喜欢吃山羊、非洲大羚羊(幼年)、兔子和鼩鼱;狐狸喜欢吃山羊、豪猪、兔子和鼩鼱;土狼喜欢吃山羊、非洲大羚羊、羚羊和斑马;狮子喜欢吃山羊、非洲大羚羊、羚羊和斑马;豪猪喜欢吃鼩鼱和兔子;而其余的则喜欢吃虫子、蚯蚓、草或其它植物。公司将饲养这些动物,希望它们能自由活动但不能相互捕食。求这些动物的一个分组,使得需要的围栏数最少。(要求用图论方法求解)
解:将动物模型为点,两点连线当且仅当两动物相克(有捕食关系),根据题目描述,所作图形如下:
问题转化为求出图的点色数,并用点色数种颜色对其正常点作色。
下面求点色数:一方面,图中存在,所以,另一方面,我们用3种颜色实现了对图的正常顶点作色:
所以,至少需要3个围栏。给出的一种最少分组方法为:
第一组:狒狒(b)、狐狸(f)、羚羊(w)和斑马
您可能关注的文档
- 2015年高中化学第一章关注营养平衡单元测试2新人教版选修1.doc
- 2015年高中历史专题五第二节外交关系的突破学案人民版必修1.doc
- 2015年高中化学第四章保护生存环境单元测试2新人教版选修1.doc
- 2015年高中历史第一单元农耕时代的商业与城市教案岳麓版必修2.doc
- 2015年高中历史人民版选修6学案专题三1新生代的曙光.doc
- 2015年高中语文第三单元单元测试1新人教版必修4.doc
- 2015年高中化学合金教案3新人教版选修1.doc
- 2015年高中历史专题六第一节民主政治的摇篮古代希腊学案人民版必修1.doc
- 2015年高一地理上期期末试题.doc
- 2015年高中语文第三单元单元测试3新人教版必修3.doc
- 5.3.1函数的单调性(教学课件)--高中数学人教A版(2019)选择性必修第二册.pptx
- 部编版道德与法治2024三年级上册 《科技提升国力》PPT课件.pptx
- 2.7.2 抛物线的几何性质(教学课件)-高中数学人教B版(2019)选择性必修第一册.pptx
- 人教部编统编版小学六年级上册道德与法治9 知法守法 依法维权(第一课时)课件.pptx
- 三年级上册品德道德与法治《学习伴我成长》.pptx
- 部编版小学道德与法治六年级上册6 人大代表为人民 课件.pptx
- 部编版小学道德与法治六年级上册1感受生活中的法律第一课时课件.pptx
- 2.5.2圆与圆的位置关系(教学课件)-高中数学人教A版(2019)选择性必修第一册.pptx
- 2.5.1直线与圆的位置关系-(教学课件)--高中数学人教A版(2019)选择性必修第一册.pptx
- 14.1.1 同底数幂的乘法(教学课件)-初中数学人教版八年级上册.pptx
文档评论(0)