您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 综合/其它 > 2014电子科技大学图论研究生试卷
1电子科技大学研究生试卷(考试时间:至,共__2_小时)课程名称图论及其应用教师学时60学分教学方式讲授考核日期_2014__年_6__月__20__日成绩考核方式:(学生填写)一.填空题(每空2分,共20分)1.n阶简单k正则图G的补图的边数为_____。2.4个顶点的不同构树的个数为________。3.具有m条边的简单图的不同生成子图的个数为____。4.彼得森图的点连通度为_______。5.n点圈的2—宽直径为_______。6.2n阶完全图共有_______个不同的完美匹配。7.设G的阶数为n,点覆盖数为,则其点独立数为________。8.完全图21nK能分解为________个边不重合的二因子之并。9.拉姆齐数(3,3)R=______。10.n完全图的不同定向方式有_______种。二.单项选择(每题3分,共15分)1.下面说法错误的是()(A)在正常点着色下,图G中的一个色组,在其补图中的点导出子图必为一个完全子图;学号姓名学院……………………密……………封……………线……………以……………内……………答……………题……………无……………效……………………2(B)若图G不连通,则其补图必连通;(C)存在14阶的自补图;(D)6阶图的补图可能是可平面图.2.下列说法错误的是()(A)一个非平凡图是偶图,当且仅当它不含有奇圈;(B)超立方体图(n方体,1n)是偶图;(C)非平凡森林是偶图;(D)不含三角形的图都是偶图。3.下面说法正确的是()(A)k连通图的连通度一定为k;(B)完全图一定没有割边;(C)(3)nn阶图G是块,则G中无环,且任意两点均位于同一圈上;(D)非平凡树一定有割点。4.下列说法错误的是()(A)若图G是哈密尔顿图,则其闭包一定为完全图;(B)设(3)nn阶单图的任意两个不邻接顶点u与v满足()()dudvn,则其闭包一定为完全图;(C)若(n,m)单图G的边数112nm,且3n,则G是哈密尔顿图;(D)若G是3n的非H单图,则G度弱于某个,mnC图。5.下列说法错误的是()(A)若(n,m)图G是极大可平面图,则36mn;3(B)极大外平面图的外部面边界一定为圈;(C)平面图的外部面只有一个;(D)平面图G的对偶图的对偶图与G是同构的。三、(10分)求证:任意图中奇度点个数一定为偶数。四,(10分)求证:非平凡树至少有两片树叶。五.(10分)求证:(1)、若G中每个顶点度数均为偶数,则G没有割边;(2)、若G为2k的k正则偶图,则G没有割边。4六.(10分)求出下图的最小生成树,并计算权值(不要中间过程,在原图中用波浪边标出最小生成树)七、(8分)设图G有10个4度顶点和8个5度顶点,其余顶点度数均为7。求7度顶点的最大数量,使得G保持其可平面性。解:分两种情况讨论:(1)、若G是非简单图,则容易知道,满足条件的7度顶点数可以为无穷多;2分(2)、若G是简单图设7度顶点的数量是x。由握手定理:xGm758410)(22分另一方面:欲使G保持其可平面性,必有63)(nGm2分即:6)810(3)785410(21xx,得16x。2分15437482325八、(7分)如果边赋权图中只有两个奇度顶点,如何构造一条最优欧拉环游?说明构造理由。九.(10分)求下图G的色多项式Pk(G).并求出点色数。图G
本文标题:2014电子科技大学图论研究生试卷
链接地址:https://www.777doc.com/doc-3013399 .html