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

2006研究生图论期末试题(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,的补图是().12345A12345BC2345D12、在下列图中，既是欧拉图又是哈密尔顿图的是().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分）v11v463429a8v22v56b72412v3v6图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).图G十、(10分)(1)、在一个只有2个奇度点的边赋权图中，如何构造一个最优欧拉环游？说明理由；(2)、在一个边赋权的哈密尔顿图中，如何估计其最优哈密尔顿圈的权值之和的下界？电子科技大学研究生试卷（考试时间：至，共__2_小时）课程名称图论及其应用教师学时50学分教学方式讲授考核日期_2008__年___月____日成绩考核方式：（学生填写）一．填空题(每题2分，共20分)1．若n阶单图G的最大度是∆，则其补图的最小度()Gδ=_____；2．若图111(,)Gnm=，222(,)Gnm=，则它们的联图12GGG=∨的顶点数=_____;边数=_____；3．G是一个完全l部图，in是第i部的的顶点数i=1，2,3,…,l。姓名学院………以……………内……………答……………题……………无……………效……………………则它的边数为____；4．下边赋权图中，最小生成树的权值之和为_______;5.若nGK=,则G的谱()specG=_______;6.5个顶点的不同构的树的棵数为_______;7.5阶度极大非哈密尔顿图族是_______;8.G为具有二分类(X,Y)的偶图，则G包含饱和X的每个顶点的匹配的充分必要条件是______9.3阶以上的极大平面图每个面的次数为_______;3阶以上的极大外平面图的每个内部面的次数为_______;10.n方体的点色数为_______;边色数为_______。二．单项选择(每题3分，共12分)1．下面给出的序列中，不是某图的度序列的是()(A)(33323);(B)(12222);(C)(5533);(D)(1333).2．设V(G)={}1,2,3,4,5，{}()(1,2),(2,3),(3,4),(4,5),(5,1)EG=则图(,)GVE=的补图是（）2732711153434266212345(A)12345(B)12345(C)1234(D)3.下列图中，既是欧拉图又是哈密尔顿图的是()4.下列说法中不正确的是()(A)每个连通图至少包含一棵生成树；(B)k正则偶图(k0)一定存在完美匹配；(C)平面图(*)*GG≅,其中*G表示G的对偶图；(D)完全图2nK可一因子分解。三、(10分)设图G的阶为14，边数为27，G中每个顶点的度只可能为3，4或5，且G有6个度为4的顶点。问G中有多少度为3的顶点？多少度为5的顶点？四，(10)证明：每棵非平凡树至少有两片树叶(10分)(A)(B)(C)(D)五．(10分)今有a,b,c,d,e,f,g七个人围圆桌开会，已知：a会讲英语，b会讲英语和汉语，c会讲英语、意大利语和俄语，d会讲日语和汉语，e会讲德语和意大利语，f会讲法语、日语和俄语，g会讲法语与德语。给出一种排座方法，使每个人能够和他身边的人交流（用图论方法求解）。六．(10分)设l是赋权完全偶图G=(V,E)的可行顶点标号，若标号对应的相等子图lG含完美匹配*M,则*M是G的最优匹配。七.(10分)求证：在n阶简单平面图G中有24nφ≤−，这里φ是G的面数。八、(10分)来自亚特兰大，波士顿，芝加哥，丹佛，路易维尔，迈阿密，以及纳什维尔的7支垒球队受邀请参加比赛，其中每支队都被安排与一些其它队比赛(安排如下所示)。每支队同一天最多进行一场比赛。建立一个具有最少天数的比赛时间表。亚特兰大：波士顿，芝加哥，迈阿密，纳什维尔波士顿：亚特兰大，芝加哥，纳什维尔芝加哥：亚特兰大，波士顿，丹佛，路易维尔丹佛：芝加哥，路易维尔，迈阿密，纳什维尔路易维尔：芝加哥，丹佛，迈阿密迈阿密：亚特兰大，丹佛，路易维尔，纳什维尔纳什维尔：亚特兰大，波士顿，丹佛，迈阿密(要求用图论方法求解)九．(8分)求下图G的色多项式Pk(G).图G电子科技大学研究生试卷（考试时间：至，共__2_小时）课程名称图论及其应用教师学时60学分教学方式讲授考核日期_2009__年___月____日成绩考核方式：（学生填写）一．填空题(每题2分，共20分)1．若自补图G的顶点数是10，则G的边数()mG=_____；2．若图111(,)Gnm=，222(,)Gnm=，则它们的积图12GGG=×的顶点数=_____;边数=_____；3．具有m条边的简单图的子图个数为____；4．设G=Kn,n,则其最大特征值为_______;5.设G是n阶的完全l等部图，则其边数m(G)=_______;6.下图G1中最小生成树的权值为_______;7.6阶度极大非哈密尔顿图族是_______;8.K9的2因子分解的数目是______；9.n（n≥3）阶极大外平面图内部面个数为_______;3阶以上的极大平面图的边数m和顶点数n的关系为_______;10.下图G2的点色数为_______;边色数为_______。二．单项选择(每题3分，共12分)1．下面给出的序列中，不是某图的图序列的是()(A)(11123);(B)(22222);(C)(3333);(D)(1333).2．下列有向图中是强连通图的是()图G1G213265233.关于n方体Qn(n≥3)，下面说法不正确的是()(A)Qn是正则图；(B)Qn是偶图；(C)Qn存在完美匹配；(D)Qn是欧拉图。4.关于平面图G和其几何对偶图G*的关系，下列说法中不正确的是()(A)平面图G的面数等于其对偶图的顶点数；(B)平面图G的边数等于其对偶图的边数；(C)平面图(*)*GG≅,其中*G表示G的对偶图；(D)平面图的对偶图是连通平面图。三、(10分)设根树T有17条边，12片树叶，4个4度内点，1个3度内点，求T的树根的度数。四，(10分)证明：若图G的每个顶点的度数为偶数，则G没有割边。(A)(B)(C)(D)五．(10分)设G是一个边赋权完全图。如何求出G的最优哈密尔顿圈的权值的一个下界？为什么？六．(10分)求证：偶图G存在完美匹配的充要条件是对任意的()SVG⊆，有()SNS≤七.(10分)求证：若G是连通平面图，且所有顶点度数不小于3，则G至少有一个面f，使得deg()5f≤。八、(10分)一家公司计划建造一个动物园，他们打算饲养下面这些动物：狒狒(b)、狐狸(f)、山羊(g)、土狼(h)、非洲大羚羊(k)、狮子(l)、豪猪(p)、兔子(r)、鼩鼱(s)、羚羊(w)和斑马(z)。根据经验，动物的饮食习惯为：狒狒喜欢吃山羊、非洲大羚羊(幼年)、兔子和鼩鼱；