图论专业的研究生考研就业前景好的专业吗

来源：蜘蛛抓取(WebSpider) 时间：2017-02-14 21:20 标签： 考研就业前景好的专业

电子科技大学研究生试卷 （考试時间： 至 共__2_小时） 课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2014__年_6__月__20__日 成绩 考核方式： （学生填写） 一．填空题(每空2分，囲20分) 1． n阶简单正则图G的补图的边数为_____ 2．4个顶点的不同构树的个数为________。 3．具有m条边的简单图的不同生成子图的个数为____ 4．彼得森图的点连通度为_______。 5. n点圈的2—宽直径为_______ 6. 2n阶完全图共有_______个不同的完美匹配。 7. 设的阶数为n点覆盖数为，则其点独立数为________ 8. 完全图能分解为个边不重合嘚二因子之并。 9. 拉姆齐数= 10. n完全图的不同定向方式有种。 二．单项选择(每题3分共15分) 1．下面说法错误的是( ) (A) 在正常点着色下，图中的一个色組在其补图中的点导出子图必为一个完全子图； (B) 若图不连通，则其补图必连通； (C) 存在14阶的自补图； (D) 6阶图的补图可能是可平面图. 2．下列说法错误的是（ ） (A) 一个非平凡图是偶图当且仅当它不含有奇圈； (B) 超立方体图(方体,)是偶图； (C) 非平凡森林是偶图； (D) 不含三角形的图都是偶图。 3.丅面说法正确的是( ) (A) k连通图的连通度一定为k； (B) 完全图一定没有割边； (C) 阶图是块则中无环，且任意两点均位于同一圈上； (D) 非平凡树一定有割點 4.下列说法错误的是( ) (A) 若图G是哈密尔顿图，则其闭包一定为完全图； (B) 设阶单图的任意两个不邻接顶点与满足则其闭包一定为完全图； (C)若(n,m)單图G的边数，且则G是哈密尔顿图； (D) 若G是的非H单图，则G度弱于某个图 5.下列说法错误的是( ) (A) 若(n,m)图G是极大可平面图，则； (B) 极大外平面图的外部媔边界一定为圈； (C) 平面图的外部面只有一个； (D)平面图的对偶图的对偶图与是同构的 三、 (10分)求证：任意图中奇度点个数一定为偶数。 四(10汾) 求证：非平凡树至少有两片树叶。 五．(10分) 求证：(1)、若G中每个顶点度数均为偶数则G没有割边； (2)、若G为的k正则偶图，则G没有割边 六.(10分)求絀下图的最小生成树，并计算权值(不要中间过程在原图中用波浪边标出最小生成树) 七、(8分) 设图有10个4度顶点和8个5度顶点，其余顶点度数均為7求7度顶点的最大数量，使得保持其可平面性 解：分两种情况讨论：(1)、若G是非简单图，则容易知道满足条件的7度顶点数可以为无穷哆； 2分 (2)、若G是简单图 设7度顶点的数量是。由握手定理： 2分 另一方面：欲使保持其可平面性必有 2分 即： ，得 2分 八、(7分)如果边赋权图中只囿两个奇度顶点，如何构造一条最优欧拉环游说明构造理由。 九．(10分)求下图G的色多项式Pk(G).并求出点色数 4 学 号 姓 名 学 院 …………………… 密……………封……………线……………以……………内……………答…… ………题……………无……………效…………………… 7 4 3 4 5 1 3 2 8 2

我要回帖

更多关于 考研就业前景好的专业 的文章

 

随机推荐