电子科技大学研究生

1

电子科技大学研究生试卷

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

课程名称图论及其应用

教师学时60学分

教学方式讲授考核日期_2013__年_6__月__20__日成绩

考核方式：（学生填写）

一．填空题(每空2分，共20分)

1．n阶k正则图G的边数m=_____。

2．4个顶点的不同构单图的个数为________。

3．完全偶图

,rs

K(,2rs≥且为偶数)，则在其欧拉环游中共含____条边。

4．高为h的完全2元树至少有_______片树叶。

5.G由3个连通分支

124

,,KKK组成的平面图，则其共有_______个面。

6.设图G与

5

K同胚，则至少从G中删掉_______条边，才可能使其

成为可平面图。

7.设G为偶图，其最小点覆盖数为α，则其最大匹配包含的边数为

________。

8.完全图

6

K能分解为________个边不重合的一因子之并。

9.奇圈的边色数为______。

10.彼得森图的点色数为_______。

二．单项选择(每题3分，共15分)

1．下面说法错误的是()

学

号

姓

名

学

院

…

…

…

…

…

…

…

…

密

…

…

…

…

…

封

…

…

…

…

…

线

…

…

…

…

…

以

…

…

…

…

…

内

…

…

…

…

…

答

…

…

…

…

…

题

…

…

…

…

…

无

…

…

…

…

…

效

…

…

…

…

…

…

…

…

2

(A)图G中的一个点独立集，在其补图中的点导出子图必为一个完全子

图；

(B)若图G连通，则其补图必连通；

(C)存在5阶的自补图；

(D)4阶图的补图全是可平面图.

2．下列说法错误的是（）

(A)非平凡树是偶图；

(B)超立方体图(n方体,1n≥)是偶图；

(C)存在完美匹配的圈是偶图；

(D)偶图至少包含一条边。

3.下面说法正确的是()

(A)2连通图一定没有割点（假定可以有自环）；

(B)没有割点的图一定没有割边；

(C)如果3阶及其以上的图G是块，则G中无环，且任意两点均位于同

一圈上；

(D)有环的图一定不是块。

4.下列说法错误的是()

(A)设(3)nn≥阶单图的最小度满足

2

n

δ≥，则其闭包一定为完全图；

(B)设(3)nn≥阶单图的任意两个不邻接顶点u与v满足()()dudvn+≥，则

其闭包一定为完全图；

(C)有割点的图一定是非哈密尔顿图；

3

(D)一个简单图G是哈密尔顿图的充要条件是它的闭包是哈密尔顿图。

5.下列说法错误的是()

(A)极大平面图的每个面均是三角形；

(B)极大外平面图的每个面均是三角形；

(C)可以把平面图的任意一个内部面转化为外部面；

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

三、(10分)设

12

,,

n

ddd"是n个不同的正整数，求证：序列

12

(,,,)

n

dddπ="

不能是简单图的度序列。

四，(15分)在下面边赋权图中求：(1)每个顶点到点

1

v的距离(只需要把

距离结果标在相应顶点处，不需要写出过程);(2)在该图中求出一棵最

小生成树，并给出最小生成树权值(不需要中间过程，用波浪线在图中标

出即可)；(3)，构造一条最优欧拉环游。

v

5

v

4

v

3

v

2

v

1

1

v

62

3

4

5

6

8

10

7

4

9

6

4

五．(10分)设T是完全m元树，i是分支点数，t是树叶数，求证：

(1)1mit−=−

六.(10分)某大型公司7个不同部门有些公开职位，分别是(a):广告

设计，(b)：营销，(c):计算师，(d)规划师，(e):实验师，(f)：财政

主管，(g):客户接待。有6名应聘者前来申请这些职位，分别是：

Alvin(A):a,c,f;Beverly(B):a,b,c,d,e,g;

Connie(C):c,f;Donald(D):b,c,d,e,f,g;

Edward(E):a,c,f:Frances(F):a,f.

(1)用偶图为此问题建模；

(2)这6名应聘者是否可以得到他们申请的职位？为什么？

(注：要求每位申请者只能获得一个职位，每个职位只能被一位申请者

获得)

5

七、(10分)

有6名博士生要进行论文答辩，答辩委员会成员分别是

1

.A={张教授，李教授，王教授};

2

.A={赵教授，李教授，刘教授};

3

.A={张教授，王教授，刘教授};

4

.A={赵教授，王教授，刘教授};

5

.A={张教授，李教授，孙教授};

6

.A={李教授，王教授，刘教授}。

要使教授们参加答辩会不至于发生时间冲突，至少安排几次答辩时间

段？请给出一种最少时间段下的安排。

八．(10分)求下图G的色多项式P

k

(G).并求出点色数。

2013年图论及其应用答案

一、

1、

2

nk

；2、11；3、rs;4、h+1;5、4;

6、1;

7、α;8、5;9、3;10、3;

二、BDCCB

三、证明：

因为

12

,,,

n

ddd…

是n个不同的正整数，不妨假定

12

1

n

ddd≤<<<