1 5 2 5
1 2
1 2
4 (A)
3
4 (B)
3
4 (C)
3
4 (D)
3
3.下列图中，既是欧拉图又是哈密尔顿图的是(
)
(A)
(B)
(C)
(D)
4.下列说法中不正确的是(
)
(A)每个连通图至少包含一棵生成树； (B)k 正则偶图(k>0)一定存在完美匹配； (C)平面图 G ≅ (G*) * ,其中 G * 表示 G 的对偶图； (D)完全图 K 2 n 可一因子分解。
(A) (33323); (B) (12222); (C) (5533); (D) (1333). 2． 设 V(G)= {1, 2,3, 4,5} ，E (G ) = {(1, 2), (2,3), (3, 4), (4,5), (5,1)} 则图 G = (V , E ) 的 补图是（ ）
1 5 2
姓 名
学 院
则它的边数为____； 4．下边赋权图中，最小生成树的权值之和为_______;
7 1 2 1 4 2 3 3 6 2 5 7 4 2 1 3 6
5. 若 G = K n ,则 G 的谱 spec(G ) = _______; 6. 5 个顶点的不同构的树的棵数为_______; 7. 5 阶度极大非哈密尔顿图族是_______; 8. G 为具有二分类(X,Y)的偶图，则 G 包含饱和 X 的每个顶点的匹 配的充分必要条件是______ 9. 3 阶以上的极大平面图每个面的次数为_______;3 阶以上的极大外 平面图的每个内部面的次数为_______; 10. n 方体的点色数为_______;边色数为_______。 二．单项选择(每题 3 分，共 12 分) 1．下面给出的序列中，不是某图的度序列的是( )
n(n − 1) 条。(5 分) 4
七、 设 T 为一棵非平凡树， 度为 i 的顶点记为 ni ， 则 n1 = 2 + n3 + 2n 4 + + (k − 2)n k 。 (10 分) 八、证明：阶数为 8 的简单偶图至多有 16 条边(5 分) 九、设图 G 有 10 个 4 度顶点和 8 个 5 度顶点，其余顶点度数均为 7。求 7 度顶点的最大数 量，使得 G 保持其可平面性(10 分) 十、求图 G 的色多项式(10 分）
1 证明(1) 证明 G 中任何两个不相邻顶点的度数之 (n − 1)(n − 2) + 2 ， 2 1 和大于等于 n。 (2)给出一个图， 使它具有 n 个顶点， m = (n − 1)(n − 2) + 1 2 m=
条边，但不是哈密尔顿图。
七、(10 分)今有赵、钱、孙、李、周五位教师，要承担语文、数学、 物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程， 钱熟悉语文、数学、物理、英语四门课程，孙、李、周都只熟悉数学 和物理两门课程。 问能否安排他们 5 人每人只上一门自己所熟悉的课 程，使得每门课程都有人教，说明理由
三、 (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 会 讲法语与德语。 给出一种排座方法， 使每个人能够和他身边的人交流 （用图论方法求解） 。
则由 v 2 到 v5 的途径长度为 2 的条数为 _________ 。 6 、若 K n 为欧拉图，则 n= _________ ；若 K n 仅存在欧拉迹而不存在欧拉回路，则 n= _________ 。 7、无向完全图 K n (n 为奇数)，共有 _________ 条没有公共边的哈密尔顿圈。 8 、设 G 是具有二分类 ( X , Y ) 的偶图，则 G 包含饱和 X 的每个顶点的匹配当且仅当
………以……………内……………答…… ………题……………无……………效……………………
电子科技大学研究生试卷
（考试时间： 课程名称 图论及其应用 教师 教学方式 讲授 考核方式： 至 ，共__2_小时） 学时 50 学分 成绩
考核日期_2008__年___月____日 （学生填写）
一．填空题(每题 2 分，共 20 分) 1．若 n 阶单图 G 的最大度是 ∆ ，则其补图的最小度 δ (G ) =_____； 2．若图 G1 = (n1 , m1 ) ， G2 = (n2 , m2 ) ，则它们的联图 G = G1 ∨ G2 的顶点 数=_____;边数=_____； 3．G 是一个完全 l 部图， ni 是第 i 部的的顶点数 i=1，2,3,…, l 。
2006 研究生图论期末试题(120 分钟)
一、填空题(15 分，每空 1 分) 1、若两个图的顶点与顶点之间，边与边之间都存在 _________ 对应，而且它们的关联关 系也保持其 _________ 关系，则这两个图同构。 2、完全图 K 4 的生成树的数目为 _________ ；阶为 6 的不同构的树有 _________ 棵。 3、设无向图 G 有 12 条边，已知 G 中度为 3 的结点有 6 个，其余结点的度数均小于 3，则
迈阿密：亚特兰大，丹佛，路易维尔，纳什维尔 纳什维尔：亚特兰大，波士顿，丹佛，迈阿密 (要求用图论方法求解)
九．(8 分)求下图 G 的色多项式 Pk(G).
图G
电子科技大学研究生试卷
（考试时间： 课程名称 图论及其应用 教师 教学方式 讲授 考核方式： 至 ，共__2_小时） 学时 60 学分 成绩
六． (10 分)设 l 是赋权完全偶图 G=(V,E)的可行顶点标号， 若标号对 应的相等子图 Gl 含完美匹配 M * ,则 M * 是 G 的最优匹配。
七.(10 分) 求证：在 n 阶简单平面图 G 中有 φ ≤ 2n − 4 ，这里 φ 是 G 的面数。
八、(10 分)来自亚特兰大，波士顿，芝加哥，丹佛，路易维尔，迈 阿密， 以及纳什维尔的 7 支垒球队受邀请参加比赛， 其中每支队都被 安排与一些其它队比赛(安排如下所示)。 每支队同一天最多进行一场 比赛。建立一个具有最少天数的比赛时间表。 亚特兰大：波士顿，芝加哥，迈阿密，纳什维尔 波士顿：亚特兰大，芝加哥，纳什维尔 芝加哥：亚特兰大，波士顿，丹佛，路易维尔 丹佛：芝加哥，路易维尔，迈阿密，纳什维尔 路易维尔：芝加哥，丹佛，迈阿密
四， 用图论的方法证明：任何一个人群中至少有两个人认识的朋友 数相同(10 分)
五．(10 分)
设 G 为 n 阶简单无向图，n>2 且 n 为奇数，G 与 G 的补
图 G 中度数为奇数的顶点个数是否相等？证明你的结论
六 ． (10 分 ) 设 G 是 具 有 n 个 顶 点 的 无 向 简 单 图 ， 其 边 数
_________ ，对所有 S ⊆ X 。
9、在有 6 个点。12 条边的简单连通平面图中，每个面均由 _________ 条边组成。 10、彼德森图的点色数为 _________ ；边色数为 _________ ；点独立数为 _________ 。 二、单选或多选题(15 分，每题 3 分) 1、设 V = { 1,2,3,4,5}， E = {(1,2), (2,3), (3,4), (4,5), (5,1)}, 则图 G =< V , E > 的补图是( ).
考核日期_2009__年___月____日 （学生填写）
一．填空题(每题 2 分，共 20 分) 1．若自补图 G 的顶点数是 10，则 G 的边数 m(G ) =_____； 2．若图 G1 = (n1 , m1 ) ，G2 = (n2 , m2 ) ，则它们的积图 G = G1 × G2 的顶点数 =_____;边数=_____； 3．具有 m 条边的简单图的子图个数为____；
(A) (11123); (B) (22222); (C) (3333); (D) (1333). 2． 下列图中，是欧拉图的是（ ）
A
B
C
D
3． 下列图中，不是哈密尔顿图的是（
）
A
B
C
D
4． 下列图中，是可平面图的图的是（
）
A
B
C
D
5．下列图中，不是偶图的是（ ）
A
B
C
D
三、 (8 分)画出具有 7 个顶点的所有非同构的树
v1 2 a 8 v2 1 v3 6 7 4
1 3
v4 9 v5 6 4 2 v6 b
2 2 9
图G
五、给出一个同构函数证明 G1 ≅ G 2 (10 分)
a 1 i f e d G1 h c b g 3 8 4 9 G2 7 2 5 6
六、若图 G 为自补图，那么，它的阶 n 一定能够表示为 4k 或者 4k + 1 的形式，其中 k 为非 负整数。而且，图 G 的边有
1 5
2
4
3 G
…………………… 密……………封……………线……………以……………内……………答…… ………题……………无……………效……………………
电子科技大学研究生试卷
（考试时间： 课程名称 图论及其应用 教师 教学方式 讲授 考核方式： 至 ，共_____小时） 学时 60 学分 成绩
考核日期_2007__年___月____日 （学生填写）
G 中至少有 _________ 个结点。
4、具有 5 个结点的自补图的个数有 _________ 。
0 1 5、已知图 G 的邻接矩阵 A(G ) = 0 1 0