电子科大研究生图论06-14年图论期末试题.pdf

《电子科大研究生图论06-14年图论期末试题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2006研究生图论期末试题(120分钟)一、填空题(15分，每空1分)1、若两个图的顶点与顶点之间，边与边之间都存在_________对应，而且它们的关联关系也保持其_________关系，则这两个图同构。2、完全图K的生成树的数目为_________；阶为6的不同构的树有_________棵。43、设无向图G有12条边，已知G中度为3的结点有6个，其余结点的度数均小于3，则G中至少有_________个结点。4、具有5个结点的自补图的个数有_________。01010111015、已知图G的邻接矩阵A(G

2、)=01011，顶点集合V(G)={v,v,v,v,v}，123451010101111则由v到v的途径长度为2的条数为_________。256、若K为欧拉图，则n=_________；若K仅存在欧拉迹而不存在欧拉回路，则nnn=_________。7、无向完全图K(n为奇数)，共有_________条没有公共边的哈密尔顿圈。n8、设G是具有二分类(X,Y)的偶图，则G包含饱和X的每个顶点的匹配当且仅当_________，对所有S⊆X。9、在有6个点。12条边的简单连通平面图中，每个面均由_________

3、条边组成。10、彼德森图的点色数为_________；边色数为_________；点独立数为_________。二、单选或多选题(15分，每题3分)1、设V={1,2,3,4,5}，E={(1,2),(2,3),(3,4),(4,5),(5,1)},则图G=的补图是().111552252343344CABD2、在下列图中，既是欧拉图又是哈密尔顿图的是().CDAB3、下列图中的()图，V到V是可达的。24V1V4V1V4V1V4V1V4V2V3V2V2V2V3V3V3ABCD4、下列图中，可1—因子分解的是().

4、(A)(C)(B)(D)5、下列优化问题中，存在好算法的是()(A)最短路问题；(B)最小生成树问题；(C)TSP问题；(D)最优匹配问题.三、作图题(10分)1、分别作出满足下列条件的图(1)、E图但非H图；(2)H图但非E图；(3)既非H图又非E图；(4)既是H图又是E图2、画出度序列为(3,2,2,1,1,1)的两个非同构的简单图。四、求下图的最小生成树，并给出它的权值之和(10分)。v11v429463a8v22v56b724129v3v6图G五、给出一个同构函数证明G≅G(10分)12a12i5fg3b8e64hd

5、c97G1G2六、若图G为自补图，那么，它的阶n一定能够表示为4k或者4k+1的形式，其中k为非n(n−1)负整数。而且，图G的边有条。(5分)4七、设T为一棵非平凡树，度为i的顶点记为n，则n=2+n+2n++(k−2)n。(10i134k分)八、证明：阶数为8的简单偶图至多有16条边(5分)九、设图G有10个4度顶点和8个5度顶点，其余顶点度数均为7。求7度顶点的最大数量，使得G保持其可平面性(10分)十、求图G的色多项式(10分）15243G电子科技大学研究生试卷（考试时间：至，共_____小时）课程名称图论及其应用

6、教师学时60学分教学方式讲授考核日期_2007__年___月____日成绩考核方式：（学生填写）一．填空题(每题2分，共12分)………题……………无……………效……………………1．简单图G=(n,m)中所有不同的生成子图(包括G和空图)的个数院学是_____个；2．设无向图G=(n,m)中各顶点度数均为3，且2n=m+3,则n=_____;m=_____；3．一棵树有n个度数为i的结点，i=2,3,…,k,则它有____个度i名数为1的结点；姓4．下边赋权图中，最小生成树的权值之和为_______;v1176v2v62435

7、810v39v564v4号5、某年级学生共选修9门课。期末考试时，必须提前将这9门学密……………封……………线……………以……………内……………答……课先考完，每天每人只在下午考一门课，则至少需要______天才能考完这9门课。……………………二．单项选择(每题2分，共10分)1．下面给出的序列中，不是某简单图的度序列的是()(A)(11123);(B)(22222);(C)(3333);(D)(1333).2．下列图中，是欧拉图的是（）ABCD3．下列图中，不是哈密尔顿图的是（）ABCD4．下列图中，是可平面图的图的是（）

8、ABCD5．下列图中，不是偶图的是（）ABCD三、(8分)画出具有7个顶点的所有非同构的树四，用图论的方法证明：任何一个人群中至少有两个人认识的朋友数相同(10分)五．(10分)设G为n阶简单无向图，n>2且n为奇数，G与G的补图G中度数为奇数的顶点个数是否相等？证明你的结论六．(10分)