电子科技大学图论05-18年研究生考试

2005年研究生期末试题(120分钟)《图论及其应用》一、填空(15分，每空1分)1、已知图G有10条边，4个度数为3的顶点，其余顶点的度数均小于2，则G中至少有___8___个顶点.2、m条边的简单图G中所有不同的生成子图(包括G和空图)的个数为__2____.m3、4个顶点的非同构的简单图有__11___个.4、图G1的最小生成树各边权值之和为__28___.5、若W是图G中一条包含所有边的闭通道，则W在这样的闭通道中具有最短长度的充要条件是：(1)每一条边最多重复经过_1__次；(2)在G的每一个圈上，重复经过的边的数目不超过圈的长度的____.一半6、5阶度极大非哈密尔顿图族有5521__,_____CC.7、在图G2中，图的度序列为(44443322)，频序列为(422)，独立数为3，团数为4，点色数为4，边色数为4，直径为3.二、选择(15分)(1)下列序列中，能成为某简单图的度序列的是(C)(A)(54221)(B)(6654332)(C)(332222)（2）已知图G有13条边，2个5度顶点，4个3度顶点，其余顶点的的度数为2，则图G有(A)个2度点。56125109431674图G1图G2(A)2(B)4(C)8(3)图G如(a)所示，与G同构的图是(C)(4)下列图中为欧拉图的是(B),为H图的是(AB),为偶图的是(BC).5．下列图中可1-因子分解的是(B)三、设和分别是(,)nm图G的最大度与最小度，求证：2mn(10分).证明：()22().vVGmnmdvnn四、正整数序列12(,,,)nddd是一棵树的度序列的充分必要条件是12(1)niidn(10分).证明：结论显然设正整数序列12(,,,)nddd满足12(1)niidn，易知它是度序列。设G是这个度序列的图族中连通分支最少的一个图，知m=()1EGn.假设G不连通，则()2G，且至少有一个分支1G含有圈C，否则，G是森林，(A)(B)(C)(a)(A)(B)(C)(A)(B)(C)有m=()1EGnn矛盾！从C中任意取出一条边111euv。并在另一分支2G中任意取出一条边222euv，作图11221221,,GGuvuvuvuv则G的度序列仍然为12(,,,)nddd且()()1GG，这与G的选取矛盾！所以G是连通的，G是树。即12(,,,)nddd一棵树的度序列。五、求证：在简单连通平面图G中，至少存在一个度数小于或等于5的顶点(10分).证明：若不然，()2()661236,vVGmdvnnmn这与G是简单连通平面图矛盾。六、证明：(1)若G恰有两个奇度点u与v，则u与v必连通；(2)一棵树至多只有一个完美匹配(10分).证明；(1)因为任意一个图的奇度点个数必然为偶数个，若G恰有两个奇度点u与v，且它们不连通，那么就会得出一个连通图只有一个奇度点的矛盾结论。所以若G恰有两个奇度点u与v，则u与v必连通。(2)若树T有两个相异的完美匹配12,MM，则12MM且12[]TMM中的每个顶点的度数为2，则T中包含圈，这与T是数矛盾！七、求图G的色多项式()kPG(15分).解：图G的补图如图G，则23411234(,)hHxrxrxrxrx，其中，111()0rNH，221()2rNH331()4rNH，441()1rNH；2212(,)hHxrxrx，其中，112()1rNH，222()1rNH图GH1H2G22344365()()(24)56[]2[]kPGxxxxxkkkk。八、求图G中a到b的最短路(15分).解1.A1={a}，t(a)=0，T1=Φ2.113bv3.m1=1,a2=v3,t(v3)=t(a)+l(av3)=1(最小)，T2={av3}2.A2={a,v3},2)2(21)2(1,vbvb3.m2=1,a3=v1,t(v1)=t(a)+l(av1)=2(最小)，T3={av3,av1}2.A3={a,v3,v1},4)3(32)3(22)3(1,,vbvbvb3.m3=3,a4=v4,t(v4)=t(v1)+l(v1v4)=3(最小)，T4={av3,av1,v1v4}2.A4={a,v3,v1,v4}，b1(4)=v2，b2(4)=v2，b3(4)=v2,b4(4)=v53.m4=4,a5=v5,t(v5)=t(v4)+l(v4v5)=6(最小)，T5={av3,av1,v1v4,v4v5}2.A5={a,v3,v1,v4,v5}，b1(5)=v2，b2(5)=v2，b3(5)=v2,b4(5)=v2,b5(5)=v23.m5=4,t(v2)=t(v4)+l(v4v2)=7(最小)，T6={av3,av1,v1v4,v4v5,v4v2}2.A6={a,v3,v1,v4,v5,v2},b2(6)=v6,b4(6)=b，b5(6)=v6，b6(6)=v63.m6=6,a7=v6,t(v6)=t(v2)+l(v2v6)=9(最小)，T7={av3,av1,v1v4,v4v5,v4v2,v2v6}2.A7={a,v3,v1,v4,v5,v2,v6},b4(7)=b，b5(7)=b，b7(7)=b3.m7=7,a8=b,t(b)=t(v6)+l(v6b)=11(最小)，T8={av3,av1,v1v4,v4v5,v4v2,v2v6,v6b}于是知a与b的距离d(a,b)=t(b)=11由T8导出的树中a到b路1426avvvvb就是最短路。v11v463429a8v22v56b72412v3v6图G92006研究生图论期末试题(120分钟)一、填空题(15分，每空1分)1、若两个图的顶点与顶点之间，边与边之间都存在_________对应，而且它们的关联关系也保持其_________关系，则这两个图同构。2、完全图4K的生成树的数目为_________；阶为6的不同构的树有_________棵。3、设无向图G有12条边，已知G中度为3的结点有6个，其余结点的度数均小于3，则G中至少有_________个结点。4、具有5个结点的自补图的个数有_________。5、已知图G的邻接矩阵1111010101110101011101010)(GA，顶点集合54321,,,,)(vvvvvGV，则由2v到5v的途径长度为2的条数为_________。6、若nK为欧拉图，则n=_________；若nK仅存在欧拉迹而不存在欧拉回路，则n=_________。7、无向完全图nK(n为奇数)，共有_________条没有公共边的哈密尔顿圈。8、设G是具有二分类),(YX的偶图，则G包含饱和X的每个顶点的匹配当且仅当_________，对所有XS。9、在有6个点。12条边的简单连通平面图中，每个面均由_________条边组成。10、彼德森图的点色数为_________；边色数为_________；点独立数为_________。二、单选或多选题(15分，每题3分)1、设5,4,3,2,1V，,)1,5(),5,4(),4,3(),3,2(),2,1(E则图EVG,的补图是().12345A112345BC2345D12、在下列图中，既是欧拉图又是哈密尔顿图的是().3、下列图中的()图，2V到4V是可达的。4、下列图中，可1—因子分解的是().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分)。ABCDAV1V2V3V4BV1V2V3V4CV1V2V3V4DV1V2V3V4(C)(A)(B)(D)五、给出一个同构函数证明21GG(10分)六、若图G为自补图，那么，它的阶n一定能够表示为k4或者14k的形式，其中k为非负整数。而且，图G的边有4)1(nn条。(5分)七、设T为一棵非平凡树，度为i的顶点记为in，则knknnn)2(22431。(10分)八、证明：阶数为8的简单偶图至多有16条边(5分)九、设图G有10个4度顶点和8个5度顶点，其余顶点度数均为7。求7度顶点的最大数量，使得G保持其可平面性(10分)十、求图G的色多项式(10分）v11v463429a8v22v56b72422v3v6图G9G2345678912G1ifebghdca2345G1电子科技大学研究生试卷（考试时间：至，共_____小时）课程名称图论及其应用教师学时60学分教学方式讲授考核日期_2007__年___月____日成绩考核方式：（学生填写）一．填空题(每题2分，共12分)1．简单图G=(n,m)中所有不同的生成子图(包括G和空图)的个数是_____个；2．设无向图G=(n,m)中各顶点度数均为3，且2n=m+3,则n=_____;m=_____；3．一棵树有in个度数为i的结点，i=2,3,…,k,则它有____个度数为1的结点；4．下边赋权图中，最小生成树的权值之和为_______;5、某年级学生共选修9门课。期末考试时，必须提前将这9门课先考完，每天每人只在下午考一门课，则至少需要______天才能考完这9门课。学号姓名学院……………………密……………封……………线……………以……………内……………答……………题……………无……………效……………………v5v4v3v2v11v6234568107496二．单项选择(每题2分，共10分)1．下面给出的序列中，不是某简单图的度序列的是()(A)(11123);(B)(22222);(C)(3333);(D)(1333).2．下列图中，是欧拉图的是（）3．下列图中，不是哈密尔顿图的是（）4．下列图中，是可平面图的图的是（）5．下列图中，不是偶图的是（）ABCDABCDABCDABDC三、(8分)画出具有7个顶点的所有非同构的树四，用图论的方法证明：任何一个人群中至少有两个人认识的朋友数相同(10分)五．(10分)设G为n阶简单无向图，n2且n为奇数，G与G的补图G中度数为奇数的顶点个数是否相等？证明你的结论六．(10分)设G是具有n个顶点的无向简单图，其边数2)2)(1(21nnm，证明(1)证明G中任何两个不相邻顶点的度数之和大于等于n。(2)给出一个图，使它具有n个顶点，1)2)(1(21nnm条边，但不是哈密尔顿图。七、(10分)今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周都只熟悉数学和物理两门课程。问能否安排他们5人每人只上一门自己所熟悉的课程，使得每门课程都有人教，说明理由八、(10分)设G是具有n个顶点，m条边，p()2P个连通分支的平面图，G的每个面至少由k（3k）条边所围成，则2)1(kpnkm九．(10分)求下图G的色多项式Pk(G).十、(10分)(1)、在一个只有2个奇度点的边赋权图中，如何构造一个最优欧拉环游？说明理由；(2)、在一个边赋权的哈密尔顿图中，如何估计其最优哈密尔顿圈的权值之和的下界？电子科技大学研究生试卷（考试时间：至，共__2_小时）课程名称图论及其应用教师学时50学分教学方式讲授考核日期_2008__年___月____日成绩考核方式：（学生填写）一．填空题(每题2分，共20分)1．若n阶单图G的最大度是，则其补图的最小度()G=_____；2．若图111(,)Gnm，222(,)Gnm，则它们的联图