2011年研究生图论试卷

1

电子科技大学研究生试卷

（考试时间： 至 ，共__2_小时）

课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2011__年___月____日 成绩 考核方式： （学生填写）

一．填空题(每空

1分，共22分)

1．若n 阶单图G 的最小度是δ，则其补图的最大度()G ?=_____。 2．若图111(,)G n m =，222(,)G n m =，则它们的积图12G G G =?的顶点数

=_____; 边数=_____。

3．设A 是图G 的推广邻接矩阵，则n A 的i 行j 列元()n ij a 等于由G 中顶点i v 到顶点j v 的长度为______的途径数目。 4．完全图n K 的邻接矩阵的最大特征值为_______。 5. 不同构的3阶单图共有_______个。

6. 设n 阶图G 是具有k 个分支的森林，则其边数()m G =_______。

7. n 阶树(3n ≥)的点连通度为_______；边连通度为________；点色数

为_______； 若其最大度为?，则边色数为________。

8. 图G 是k 连通的，则G 中任意点对间至少有______条内点不交路。 9. 5阶度极大非哈密尔顿图族为______和_______。

10. 完全图2n K 能够分解为_______个边不相交的一因子之并。 11. 设连通平面图G 具有5个顶点，9条边，则其面数为_______；

学 号 姓 名 学 院

…………………… 密……………封……………线……………以……………内……………答…… ………题……………无……………效……………………

2

n (3n ≥)阶极大平面图的面数等于__________；n (3n ≥)阶极大外平

面图的顶点都在外部面边界上时，其内部面共有_______个。 12. 完全偶图,m n K 的点独立数等于________,点覆盖数等于______。 13. 完全m 元根树有t 片树叶，i 个分支点，则其总度数为_______。 14．对具有m 条边的单图定向，能得到______个不同的定向图。 二．单项选择(每题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．下列无向图(,)G n m =一定是树的是（ ）

(A) 连通图；(B)无回路但添加一条边后有回路的图； (C) 每对结点间都有路的图； (D) 连通且1m n =-。 3.以下必为欧拉图的是( ) (A) 顶点度数全为偶数的连通图； (B) 奇数顶点只有2个的图； (C) 存在欧拉迹的图； (D) 没有回路的连通图。

4.设G 是n (3n ≥)阶单图，则其最小度2

n δ≥是G 为哈密尔顿图的( ) (A) 必要条件；(B)充分条件；(C)充分必要条件。 5.下列说法正确的是( )

(A) 非平凡树和(2)n n ≥方体都是偶图；

(B) 任何一个3正则图都可1-因子分解；

(C) 可1-因子分解的3正则图中一定存在哈密尔顿圈；

(D) 平面图G的对偶图的对偶图与G是同构的。

三、 (10分)设无向图G有12条边，且度数为3的结点有6个，其余结点的度数小于3，求G的最少结点个数。

四，(12分) 在下面边赋权图中求：(1)每个顶点到点a的距离(只需要把距离结果标在相应顶点处，不需要写出过程); (2) 在该图中求出一棵最小生成树，并给出最小生成树权值(不需要中间过程，用波浪线在图中标出即可).

6

五．(10分) 今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周都只熟悉数学、物理两门课程。问能否安排他们都只上他们熟悉的一门课程，使得每门课程都有人教（用图论方法求解）。

3

4

六．(6分)设l 是赋权完全偶图G=(V,E)的可行顶点标号，若标号对应的相等子图l G 含完美匹配*M ,则*M 是G 的最优匹配。

七.(6分) 求证：在n 阶简单平面图G 中有()5G δ≤，这里()G δ是G 的最小度。

八、(10分)课程安排问题：某大学数学系要为这个夏季安排课程表。所要开设的课程为：图论(GT), 统计学(S),线性代数(LA), 高等微积分(AC), 几何学(G), 和近世代数( MA )。现有10名学生(学生用A i 表示，如下所示）需要选修这些课程。根据这些信息，确定开设这些课程所需要的最少时间段数，使得学生选课不会发生冲突。 (要求用图论方法求

解)

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分)求下图G的色多项式P k(G).

2

1

5

4

G

5