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

1、2005年研究生期末试题(120分钟)图论及其应用一、填空(15分，每空1分)1、 已知图G有10条边，4个度数为3的顶点，其余顶点的度数均小于2，则G中至少有个顶点 .2、 m条边的简单图G中所有不同的生成子图(包括G和空图)的个数为3、 4个顶点的非同构的简单图有个.4、 图G1的最小生成树各边权值之和为5、若W是图G中一条包含所有边的闭通道，则W在这样的闭通道中具有最短长度的充要条件是：(1) 每一条边最多重复经过次；(2) 在G的每一个圈上，重复经过的边的数目不超过圈的长度的6、5阶度极大非哈密尔顿图族有.7、在图G2 中，图的度序列为(44443322)，频序列为(422)，独立数为

2、3，团数为4，点色数为4，边色数为4，直径为3.图G2二、选择(15分)(1)下列序列中，能成为某简单图的度序列的是( C ) (A) (54221) (B) (6654332) (C) (332222)（2）已知图G有13条边，2个5度顶点，4个3度顶点，其余顶点的的度数为2，则图G有( A )个2度点。 (A) 2 ( B) 4 (C ) 8(3) 图G如(a)所示，与G同构的图是( C )(4) 下列图中为欧拉图的是( B ),为H图的是( AB ),为偶图的是( BC ).5下列图中可1-因子分解的是( B )三、设和分别是图G的最大度与最小度，求证：(10分).证明：四、正整数序列是

3、一棵树的度序列的充分必要条件是 (10分). 证明： 结论显然设正整数序列满足，易知它是度序列。设G是这个度序列的图族中连通分支最少的一个图，知m=.假设G不连通，则，且至少有一个分支含有圈C，否则，G是森林，有m=矛盾！从C中任意取出一条边。并在另一分支中任意取出一条边，作图则的度序列仍然为且，这与G的选取矛盾！所以G是连通的，G是树。即一棵树的度序列。五、求证：在简单连通平面图G中，至少存在一个度数小于或等于5的顶点 (10分).证明：若不然，这与G是简单连通平面图矛盾。六、证明：(1) 若G恰有两个奇度点u与v，则u与v必连通；(2) 一棵树至多只有一个完美匹配 (10分).证明；(1)

4、 因为任意一个图的奇度点个数必然为偶数个，若G恰有两个奇度点u与v，且它们不连通，那么就会得出一个连通图只有一个奇度点的矛盾结论。所以若G恰有两个奇度点u与v，则u与v必连通。(2) 若树有两个相异的完美匹配，则且中的每个顶点的度数为2，则中包含圈，这与是数矛盾！七、求图G的色多项式(15分).图G解：图G的补图如图，则，其中，；，其中，。八、求图G中a到b的最短路(15分).v1 1 v4 6 342 9 a 8 v2 2 v5 6 b 7 2 41 2 v3 v6 图G9解 1. A1= a，t(a) = 0，T1 = 2.3. m1 = 1, a2 = v3 , t(v3) = t(a)

5、 + l(av3) = 1 (最小)， T2 =av32. A2 =a, v3, 3. m2 = 1, a3 = v1 , t(v1) = t(a) + l(av1) = 2 (最小)， T3 =av3, av12. A3 =a, v3, v1, 3. m3 = 3, a4 = v4 , t(v4) = t(v1) + l(v1v4) = 3 (最小)， T4 =av3, av1, v1v42. 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) +

6、l(v4v5) = 6 (最小)， T5 =av3, av1, v1v4, v4v52. 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, v4v22. 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)

7、 = t(v2) + l(v2v6) = 9 (最小)， T7 =av3, av1, v1v4, v4v5, v4v2, v2v62. 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路就是最短路。2006研究生图论期末试题(120分钟)一、填空题(15分，每空

8、1分)1、若两个图的顶点与顶点之间，边与边之间都存在对应，而且它们的关联关系也保持其关系，则这两个图同构。2、完全图的生成树的数目为；阶为6的不同构的树有棵。3、设无向图有12条边，已知中度为3的结点有6个，其余结点的度数均小于3，则中至少有个结点。4、具有5个结点的自补图的个数有。5、已知图的邻接矩阵，顶点集合，则由到的途径长度为2的条数为。6、若为欧拉图，则n=；若仅存在欧拉迹而不存在欧拉回路，则n=。7、无向完全图(n为奇数)，共有条没有公共边的哈密尔顿圈。8、设是具有二分类的偶图，则包含饱和的每个顶点的匹配当且仅当，对所有。9、在有6个点。12条边的简单连通平面图中，每个面均由条边组成

9、。10、彼德森图的点色数为；边色数为；点独立数为。二、单选或多选题(15分，每题3分)1、设，则图的补图是( ).2、在下列图中，既是欧拉图又是哈密尔顿图的是( ).3、下列图中的( )图，到是可达的。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、出它的权值之和(10分)。v1 1 v4 6 342 9 a 8 v2 2 v5 6 b 7 2 42 2 v3 v6 图G9五、给出一个同构函数证明(10分) 六、若图为自补图，那么，它的阶一定能够表示为或者的形式，其中为非负整数。而且，图的边有条。(5分)七、设T为一棵非平凡树，度为的顶点记为，则。(10分)八、证明：阶数为8的简单偶图至多有16条边(5分)九、设图有10个4度顶点和8个5度顶点，其余顶点度数均为7。求7度顶点的最大数量，使得保持其可平面性(10分)十、求图的色多项式(10分）学 号 姓 名 学 院 密封线以内答 题无效 电子科技大学研究生试卷 （考试时间： 至 ，共_小时

11、）课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2007_年_月_日 成绩 考核方式： （学生填写） 一填空题(每题2分，共12分)1简单图G=(n,m)中所有不同的生成子图(包括G和空图)的个数是_个；2设无向图G=(n,m)中各顶点度数均为3，且2n=m+3,则n=_; m=_；3一棵树有个度数为i的结点，i=2,3,k,则它有_个度数为1的结点； 4下边赋权图中，最小生成树的权值之和为_; 5、某年级学生共选修9门课。期末考试时，必须提前将这9门课先考完，每天每人只在下午考一门课，则至少需要_天才能考完这9门课。二单项选择(每题2分，共10分)1下面给出的序列

12、中，不是某简单图的度序列的是( ) (A) (11123); (B) (22222); (C) (3333); (D) (1333).2 下列图中，是欧拉图的是（ ）3 下列图中，不是哈密尔顿图的是（ ）4 下列图中，是可平面图的图的是（ ）5下列图中，不是偶图的是（ ）三、 (8分)画出具有7个顶点的所有非同构的树四， 用图论的方法证明：任何一个人群中至少有两个人认识的朋友数相同(10分)五(10分) 设G为n 阶简单无向图，n>2且n为奇数，G与G的补图中度数为奇数的顶点个数是否相等？证明你的结论 六(10分)设G是具有n个顶点的无向简单图，其边数，证明(1) 证明G中任何两个不相邻

13、顶点的度数之和大于等于n。(2)给出一个图，使它具有n个顶点，条边，但不是哈密尔顿图。 七、(10分)今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周都只熟悉数学和物理两门课程。问能否安排他们5人每人只上一门自己所熟悉的课程，使得每门课程都有人教，说明理由八、(10分)设G是具有n个顶点，m条边，p(个连通分支的平面图，G的每个面至少由k（）条边所围成，则九(10分)求下图G的色多项式Pk(G).十、(10分) (1)、在一个只有2个奇度点的边赋权图中，如何构造一个最优欧拉环游？说明

14、理由；(2)、在一个边赋权的哈密尔顿图中，如何估计其最优哈密尔顿圈的权值之和的下界？学 号 姓 名 学 院 密封线以内答 题无效 电子科技大学研究生试卷 （考试时间： 至 ，共_2_小时）课程名称 图论及其应用 教师 学时 50 学分 教学方式 讲授 考核日期_2008_年_月_日 成绩 考核方式： （学生填写） 一填空题(每题2分，共20分)1若n阶单图G的最大度是，则其补图的最小度=_；2若图，则它们的联图的顶点数=_;边数=_；3G是一个完全部图，是第i部的的顶点数i=1，2,3,。则它的边数为_； 4下边赋权图中，最小生成树的权值之和为_; 5. 若,则G的谱_; 6. 5个顶点的不同

15、构的树的棵数为_; 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)=，则图的补图是（ ）3.下列图中，既是欧拉图又是哈密尔顿图的是( )4.下列说法中不正确的是( )(A)每个连通图至少包含一棵生成树；

16、(B)k正则偶图(k>0)一定存在完美匹配；(C)平面图,其中表示G的对偶图；(D)完全图可一因子分解。三、 (10分)设图G的阶为14，边数为27，G中每个顶点的度只可能为3，4或5，且G有6个度为4的顶点。问G中有多少度为3的顶点？多少度为5的顶点？四，(10)证明：每棵非平凡树至少有两片树叶(10分)五(10分) 今有a,b,c,d,e,f,g七个人围圆桌开会，已知：a会讲英语，b会讲英语和汉语，c会讲英语、意大利语和俄语，d会讲日语和汉语，e会讲德语和意大利语，f会讲法语、日语和俄语，g会讲法语与德语。给出一种排座方法，使每个人能够和他身边的人交流（用图论方法求解）。六(10分)

17、设是赋权完全偶图G=(V,E)的可行顶点标号，若标号对应的相等子图含完美匹配,则是G的最优匹配。七.(10分) 求证：在n阶简单平面图G中有，这里是G的面数。八、(10分)来自亚特兰大，波士顿，芝加哥，丹佛，路易维尔，迈阿密，以及纳什维尔的7支垒球队受邀请参加比赛，其中每支队都被安排与一些其它队比赛(安排如下所示)。每支队同一天最多进行一场比赛。建立一个具有最少天数的比赛时间表。亚特兰大：波士顿，芝加哥，迈阿密，纳什维尔波士顿：亚特兰大，芝加哥，纳什维尔芝加哥：亚特兰大，波士顿，丹佛，路易维尔丹佛：芝加哥，路易维尔，迈阿密，纳什维尔路易维尔：芝加哥，丹佛，迈阿密迈阿密：亚特兰大，丹佛，路易维尔

18、，纳什维尔纳什维尔：亚特兰大，波士顿，丹佛，迈阿密(要求用图论方法求解)九(8分)求下图G的色多项式Pk(G).学 号 姓 名 学 院 密封线以内答 题无效 电子科技大学研究生试卷 （考试时间： 至 ，共_2_小时）课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2009_年_月_日 成绩 考核方式： （学生填写） 一填空题(每题2分，共20分)1若自补图G的顶点数是10，则G的边数=_；2若图，则它们的积图的顶点数=_;边数=_；3具有m条边的简单图的子图个数为_； 4设G=Kn,n,则其最大特征值为_; 5. 设G是n阶的完全l等部图，则其边数m(G)=_; 6.

19、 下图G1中最小生成树的权值为_;1326523图G1 7. 6阶度极大非哈密尔顿图族是_; 8. K9的2因子分解的数目是_；9. n（n3）阶极大外平面图内部面个数为_;3阶以上的极大平面图的边数m和顶点数n的关系为_;10. 下图G2的点色数为_;边色数为_。G2二单项选择(每题3分，共12分)1下面给出的序列中，不是某图的图序列的是( ) (A) (11123); (B) (22222); (C) (3333); (D) (1333).2下列有向图中是强连通图的是( )3.关于n方体Qn(n3)，下面说法不正确的是( )(A) Qn是正则图； (B) Qn是偶图；(C) Qn存在完美匹

20、配；(D) Qn是欧拉图。4.关于平面图G和其几何对偶图G*的关系，下列说法中不正确的是( )(A)平面图G的面数等于其对偶图的顶点数；(B)平面图G的边数等于其对偶图的边数；(C)平面图,其中表示G的对偶图；(D)平面图的对偶图是连通平面图。三、 (10分)设根树T有17条边，12片树叶，4个4度内点，1个3度内点，求T的树根的度数。四，(10分)证明：若图G的每个顶点的度数为偶数，则G没有割边。五(10分) 设G是一个边赋权完全图。如何求出G的最优哈密尔顿圈的权值的一个下界？为什么？六(10分)求证：偶图G存在完美匹配的充要条件是对任意的，有七.(10分) 求证：若G是连通平面图，且所有顶

21、点度数不小于3，则G至少有一个面 ，使得。八、(10分)一家公司计划建造一个动物园，他们打算饲养下面这些动物：狒狒(b)、狐狸(f)、山羊(g)、土狼(h)、非洲大羚羊(k)、狮子(l)、豪猪(p)、兔子(r)、鼩鼱(s)、羚羊(w)和斑马(z)。根据经验，动物的饮食习惯为：狒狒喜欢吃山羊、非洲大羚羊(幼年)、兔子和鼩鼱；狐狸喜欢吃山羊、豪猪、兔子和鼩鼱；土狼喜欢吃山羊、非洲大羚羊、羚羊和斑马；狮子喜欢吃山羊、非洲大羚羊、羚羊和斑马；豪猪喜欢吃鼩鼱和兔子；而其余的则喜欢吃虫子、蚯蚓、草或其它植物。公司将饲养这些动物，希望它们能自由活动但不能相互捕食。求这些动物的一个分组，使得需要的围栏数最少。

22、(要求用图论方法求解)九(8分)求下图G的色多项式Pk(G).学 号 姓 名 学 院 密封线以内答 题无效 电子科技大学研究生试卷 （考试时间： 至 ，共_2_小时）课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2010_年_月_日 成绩 考核方式： （学生填写） 一填空题(每题2分，共20分)1若自补图G的顶点数是，则G的边数=_；2若图，则它们的联图的顶点数=_;边数=_；145213623uvG13下图G1中u与v间的最短路的长度为_；2 4设是图G的推广的邻接矩阵,则(k是正整数) 的表示的意义为_； 5. 设，则G的谱=_; 6. 设8阶图G中没有三角形，

23、则G能够含有的最多边数为_; 7. 三角形图的生成树的棵数为_;8. G2的点连通度与边连通度分别为_；G29.n=5的度极大非H图族为_;10. n方体()的点色数为_;边色数为_。二单项选择(每题3分，共12分)1下面命题正确的是( ) (A) 任意一个非负整数序列均是某图的度序列；(B) 设非负整数序列，则是图序列当且仅当为偶数; (C) 若非负整数序列是图序列，则对应的不同构的图一定唯一;(D) n阶图G和它的补图有相同的频序列.2下列有向图中是强连通图的是( )3.关于欧拉图与哈密尔顿图的关系，下面说法正确的是( )(A) 欧拉图一定是哈密尔顿图； (B) 哈密尔顿图一定是欧拉图；(

24、C) 存在既不是欧拉图又不是哈密尔顿图的图；(D) 欧拉图与哈密尔顿图都可以进行圈分解。4.下列说法中正确的是( )(A) 任意一个图均存在完美匹配；(B) k(正则偶图一定存在完美匹配；(C) 匈牙利算法不能求出偶图的最大匹配，只能用它求偶图的完美匹配；(D) 图G的一个完美匹配实际上就是它的一个1因子。三、 (10分)若阶为25且边数为62的图G的每个顶点的度只可能为3，4，5或6，且有两个度为4的顶点，11个度为6的顶点，求G中5度顶点的个数。四，(8分)求下图的最小生成树（不要求中间过程，只要求画出最小生成树, 并给出T的权和）。113114311567438五(8分)求下图的k色多项

25、式。G六(8分) 设G是一个边赋权完全图。如何求出G的最优哈密尔顿圈的权值的一个下界？为什么？七(8分)求证：设是赋权完全偶图的可行顶点标号对应的相等子图，若是的完美匹配，则它必为G的最优匹配。八.(8分) 求证：若n为偶数，且，则G中存在3因子。九、(10分)一家公司计划建造一个动物园，他们打算饲养下面这些动物：狒狒(b)、狐狸(f)、山羊(g)、土狼(h)、非洲大羚羊(k)、狮子(l)、豪猪(p)、兔子(r)、鼩鼱(s)、羚羊(w)和斑马(z)。根据经验，动物的饮食习惯为：狒狒喜欢吃山羊、非洲大羚羊(幼年)、兔子和鼩鼱；狐狸喜欢吃山羊、豪猪、兔子和鼩鼱；土狼喜欢吃山羊、非洲大羚羊、羚羊和斑

26、马；狮子喜欢吃山羊、非洲大羚羊、羚羊和斑马；豪猪喜欢吃鼩鼱和兔子；而其余的则喜欢吃虫子、蚯蚓、草或其它植物。公司将饲养这些动物，希望它们能自由活动但不能相互捕食。求这些动物的一个分组，使得需要的围栏数最少。(要求用图论方法求解)十(8分) 求证，每个5连通简单可平面图至少有12个顶点。 学 号 姓 名 学 院 密封线以内答 题无效 电子科技大学研究生试卷 （考试时间： 至 ，共_2_小时）课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2011_年_月_日 成绩 考核方式： （学生填写） 一填空题(每空1分，共22分)1若n阶单图G的最小度是，则其补图的最大度=_。2

27、若图，则它们的积图的顶点数=_; 边数=_。3设是图的推广邻接矩阵，则的行列元等于由中顶点到顶点的长度为_的途径数目。 4完全图的邻接矩阵的最大特征值为_。 5. 不同构的3阶单图共有_个。 6. 设阶图是具有个分支的森林，则其边数_。 7. 阶树()的点连通度为_；边连通度为_；点色数为_； 若其最大度为，则边色数为_。 8. 图是连通的，则中任意点对间至少有_条内点不交路。9. 5阶度极大非哈密尔顿图族为_和_。10. 完全图能够分解为_个边不相交的一因子之并。11. 设连通平面图具有5个顶点，9条边，则其面数为_； ()阶极大平面图的面数等于_；()阶极大外平面图的顶点都在外部面边界上时

28、，其内部面共有_个。12. 完全偶图的点独立数等于_,点覆盖数等于_。13. 完全元根树有片树叶，个分支点，则其总度数为_。14对具有条边的单图定向，能得到_个不同的定向图。二单项选择(每题3分，共15分)1下面给出的序列中，不是某图的度序列的是( ) (A) (1,3,5,4,7); (B) (2,2,2,2,2); (C) (3,2,3,3); (D) (1,5,7,1).2下列无向图一定是树的是（ ） (A) 连通图；(B)无回路但添加一条边后有回路的图； (C) 每对结点间都有路的图； (D) 连通且。3.以下必为欧拉图的是( )(A) 顶点度数全为偶数的连通图；(B) 奇数顶点只有2

29、个的图；(C) 存在欧拉迹的图； (D) 没有回路的连通图。4.设是()阶单图，则其最小度是为哈密尔顿图的( )(A) 必要条件；(B)充分条件；(C)充分必要条件。5.下列说法正确的是( ) (A) 非平凡树和方体都是偶图； (B) 任何一个3正则图都可1-因子分解； (C) 可1-因子分解的3正则图中一定存在哈密尔顿圈； (D) 平面图的对偶图的对偶图与是同构的。三、 (10分)设无向图有12条边，且度数为3的结点有6个，其余结点的度数小于3，求G的最少结点个数。 四，(12分) 在下面边赋权图中求：(1)每个顶点到点的距离(只需要把距离结果标在相应顶点处，不需要写出过程); (2) 在该

30、图中求出一棵最小生成树，并给出最小生成树权值(不需要中间过程，用波浪线在图中标出即可).五(10分) 今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周都只熟悉数学、物理两门课程。问能否安排他们都只上他们熟悉的一门课程，使得每门课程都有人教（用图论方法求解）。六(6分)设是赋权完全偶图G=(V,E)的可行顶点标号，若标号对应的相等子图含完美匹配,则是G的最优匹配。七.(6分) 求证：在n阶简单平面图G中有，这里是G的最小度。八、(10分) 课程安排问题：某大学数学系要为这个夏季安排课程

31、表。所要开设的课程为：图论(GT), 统计学(S),线性代数(LA), 高等微积分(AC), 几何学(G), 和近世代数( MA )。现有10名学生(学生用Ai表示，如下所示）需要选修这些课程。根据这些信息，确定开设这些课程所需要的最少时间段数，使得学生选课不会发生冲突。 (要求用图论方法求解)A1 : LA, S ; A2 : MA, LA, G ; A3: MA, G, LA ;A4: G, LA, AC ; A5: AC, LA, S ; A6: G, AC;A7: GT, MA, LA ; A8: LA,GT, S ; A9: AC, S, LA;A10: GT, S。九(9分)求下图

32、G的色多项式Pk(G).G学 号 姓 名 学 院 密封线以内答 题无效2154学 号 姓 名 学 院 密封线以内答 题无效 电子科技大学研究生试卷 （考试时间： 至 ，共_2_小时）课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2012_年_月_日 成绩 考核方式： （学生填写） 一、填空题（填表题每空1分，其余每题2分，共30分)1阶正则图G的边数=；23个顶点的不同构的简单图共有个；3边数为的简单图的不同生成子图的个数有个； 4. 图与图的积图的边数为；5. 在下图中，点到点的最短路长度为；6. 设简单图的邻接矩阵为，且，则图的边数为；7. 设是n阶简单图，且不

33、含完全子图，则其边数一定不会超过；8的生成树的棵数为; 9. 任意图的点连通度、边连通度、最小度之间的关系为 ；10. 对下列图，试填下表（是类图的打 ，否则打 ）。 能一笔画的图Hamilton图偶图可平面图二、单项选择(每题2分，共10分)1下面命题正确的是 ( B ) 对于序列，下列说法正确的是：(A) 是简单图的度序列；(B) 是非简单图的度序列; (C) 不是任意图的度序列;(D) 是图的唯一度序列.2对于有向图，下列说法不正确的是 ( D )(A) 有向图中任意一顶点只能处于的某一个强连通分支中；(B) 有向图中顶点可能处于的不同的单向分支中; (C) 强连通图中的所有顶点必然处于

34、强连通图的某一有向回路中;(D) 有向连通图中顶点间的单向连通关系是等价关系。3.下列无向图可能不是偶图的是 ( D )(A) 非平凡的树； (B) 无奇圈的非平凡图；(C) 方体；(D) 平面图。4.下列说法中正确的是 ( C )(A) 连通3正则图必存在完美匹配；(B) 有割边的连通3正则图一定不存在完美匹配；(C) 存在哈密尔顿圈的3正则图必能1因子分解；(D) 所有完全图都能作2因子分解。5. 关于平面图，下列说法错误的是( B )(A) 简单连通平面图中至少有一个度数不超过5的顶点；(B) 极大外平面图的内部面是三角形，外部面也是三角形；(C) 存在一种方法，总可以把平面图的任意一个

35、内部面转化为外部面；(D) 平面图的对偶图也是平面图。三、 (10分) 设与其补图的边数分别为，求的阶数。解：设的阶数为。因4分所以：.2分得：.4分四、(10分) 求下图的最小生成树（不要求中间过程，只要求画出最1 2 3v7v6v1v2v6V7小生成树, 并给出T的权和）。2 44 3 5 1 66 5v4v3v4v5V7v6v5v4v3v2v1v4v6v76 54 3 5 1 62 41 2 3五、(10分) (1). 求下图的k色多项式； (2). 求出的点色数 ；(3). 给出一种使用种颜色的着色方法。解：(1)、图G的补图为：(2分).1分对于：，所以，其伴随多项式为：.1分 所以

36、：1分 于是色多项式= k (k-1) (k-2)2+4(k-3) +(k-3) (k-4) = k(k-1)2 (k-2)2 2分解法2 2分 + = (k-1) 3分= (k-1) k(k-1) (k-2)2= k(k-1)2 (k-2)2 2分 (2)、由于，所以，点色数=3；.2分(3)、点着色：(1分)六、(10分) 5个人被邀请参加桥牌比赛。桥牌比赛规则是每一场比赛由两个2人组进行对决。要求每个2人组都要与其它2人组（W,Z ÏX,Y）进行对决。若每个人都要与其他任意一个人组成一个2人组，且每个组在同一天不能有多余一次的比赛，则最少安排多少天比赛（每一天可以有多场比赛）？

37、请给出相应的一个时间安排表。(用图论方法求解)解：(1)、建模：5个人能够组成10个2人组：AB, AC, AD, AE, BD, BC, BE, CD , CE, DE。 以每个2人组作为顶点，因要求每个2人组都与其它2人组比赛，所以，得到比赛状态图如下： 4分(2)、最少安排多少天比赛转化为求状态图的边色数。因为彼得森图不可1因子分解，于是可推出，又可用4种色对其正常边着色(见下图)，所以：。所以：。 2分111222122333444(3)、安排时间表：第一天：AB-DE, AE-BC, AC-BE, AD-CE; 第二天：AB-CE, AC-DE, AE-BD, AD-BC, BE-C

38、D ;第三天：AB-CD, BC-DE, BD-CE;第四天：AC-BD, AD-BE, AE-CD。 4分七、(10分 ) 由于在考试中获得好成绩，6名学生将获得下列书籍的奖励，分别是：代数学(a)，微积分(c)，微分方程(d)，几何学(g)，数学史(h)，规划学(p)，拓扑学(t)。每门科目只有1本书，而每名学生对书的喜好是：A：d, h, t ；B： h, t ；C：d, h ；D：d, t ；E：a, c, d ； F:：c, d, p, g 。每名学生是否都可以得到他喜欢的书？为什么？(用图论方法求解)解：由题意,得模型图：(4分)问题转化为是否存在饱和A,B,C,D,E,F的匹配存

39、在。 2分取顶点子集合，因，所以由霍尔定理知：不存在饱和A,B,C,D,E,F的匹配。故每名学生不能都得到他喜欢的书。 4分八、(10分) 若为偶数，且单图G满足：，求证：中有3因子。证明：因单图G满足：，所以中存在哈密尔顿圈。 2分又因为偶数，所以，可分解为两个1因子，它们显然也是图G的两个1因子。 3分 考虑，则，于是，中存在哈密尔顿圈。 2分 作，则为G的一个3因子。 3分学 号 姓 名 学 院 密封线以内答 题无效 电子科技大学研究生试卷 （考试时间： 至 ，共_2_小时）课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2013_年_6_月_20_日 成绩 考

40、核方式： （学生填写） 一填空题(每空2分，共20分)1 n阶正则图G的边数=_。24个顶点的不同构单图的个数为_。3完全偶图(且为偶数)，则在其欧拉环游中共含_条边。 4高为的完全2元树至少有_片树叶。 5. 由3个连通分支组成的平面图，则其共有_个面。 6. 设图与同胚，则至少从中删掉_条边，才可能使其成为可平面图。 7. 设为偶图，其最小点覆盖数为，则其最大匹配包含的边数为_。 8. 完全图能分解为个边不重合的一因子之并。9. 奇圈的边色数为。10. 彼得森图的点色数为。二单项选择(每题3分，共15分)1下面说法错误的是( ) (A) 图中的一个点独立集，在其补图中的点导出子图必为一个完

41、全子图；(B) 若图连通，则其补图必连通； (C) 存在5阶的自补图； (D) 4阶图的补图全是可平面图.2下列说法错误的是（ ） (A) 非平凡树是偶图；(B) 超立方体图(方体,)是偶图； (C) 存在完美匹配的圈是偶图； (D) 偶图至少包含一条边。3.下面说法正确的是( )(A) 2连通图的连通度一定为2；(B) 没有割点的图一定没有割边；(C) 阶图是块，则中无环，且任意两点均位于同一圈上； (D) 有环的图一定不是块。4.下列说法错误的是( )(A) 设阶单图的最小度满足，则其闭包一定为完全图；(B) 设阶单图的任意两个不邻接顶点与满足，则其闭包一定为完全图；(C)有割点的图一定是

42、非哈密尔顿图；(D) 一个简单图是哈密尔顿图的充要条件是它的闭包是哈密尔顿图。5.下列说法错误的是( ) (A) 极大平面图的每个面均是三角形； (B) 极大外平面图的每个面均是三角形； (C) 可以把平面图的任意一个内部面转化为外部面； (D) 连通平面图的对偶图的对偶图与是同构的。三、 (10分)设是个不同的正整数，求证：序列不能是简单图的度序列。 四，(15分) 在下面边赋权图中求：(1)每个顶点到点的距离(只需要把距离结果标在相应顶点处，不需要写出过程); (2) 在该图中求出一棵最小生成树，并给出最小生成树权值(不需要中间过程，用波浪线在图中标出即可)；(3)，构造一条最优欧拉环游。五(10分) 设是完全元树，是分支点数，是树叶数，求证：六.(10分) 某大型公司7个不同部门有些公开职位，分别是(a):广告设计，(b)：营销，(c ):计算师，(d)规划师，(e):实验师，(f)：财政主管，(g):客户接待。有6名应聘者前来申请这些职位，分别是：Alvin(A):