2023年7月19日发(作者：)

……………………

效

…

…

…

…

…

无

…

…

…

…

…

题

…

…

院…

学……

答

…

…

…

…

…

内

…

…

…

名……

姓以

…

…

…

…

…

线

…

…

…

…

…

封

…

…

号……

学…密

……………………

电子科技大学研究生试卷

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

答案

课程名称 图论及其应用 教师 学时 60 学分

教学方式 讲授 考核日期_2015__年_6__月__26__日 成绩

考核方式： （学生填写）

一．填空题(每空3分，共15分)

1.不同构的3阶简单图的个数为__4___。

2．图1中的最小生成树的权值为__20____。

3.基于图2的最优欧拉环游的总权值为____37___。

4.图3中块的个数为___4____。

6

1

6

6

3 2

2

4

5

1

2 2

2

8

7

3

4

1

3

3

6

3

2

图1

图2

图3

5.图4中强连通分支的个数为____3____。

图4

1

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

1．关于图的度序列，下列命题错误的是( D )

(A) 同构的两个图的度序列相同；

(B) 非负整数序列(d1,d2,,dn)是图的度序列当且仅当di是偶数；

i1n (C) 如果非负整数序列(d1,d2,,dn)(n2)是一棵树的度序列，那么序列中至少有两个整数的值为1；

(D). 如果非负整数序列(d1,d2,,dn)是简单图的度序列，那么在同构意义下只能确定一个图。

2．关于n阶简单图的邻接矩阵A(aij)nn，下列说法错误的是（ C ）

(A) 矩阵A的行和等于该行对应顶点的度数；

(B) 矩阵所有元素之和等于该图边数的2倍；

(C) 不同构的两个图，它们的邻接矩阵特征谱一定不同；

(D) 非连通图的邻接矩阵一定可以表示为准对角矩阵形式。

3.关于欧拉图，下面说法正确的是( B )

(A) 欧拉图存在唯一的欧拉环游；

(B) 非平凡欧拉图中一定有圈；

(C) 欧拉图中一定没有割点；

(D) 度数为偶数的图一定是欧拉图。

4.关于哈密尔顿图，下列命题错误的是( B )

(A)设G是n3的简单图，若其闭包是完全图，则G是哈密尔顿图；

2 (B) 若n阶单图的闭包不是完全图，则它一定是非哈密尔顿图；

(C)若G是哈密尔顿图，则对于V的每个非空顶点子集S，均有(GS)S；

(D) 若G是n3的非H单图，则G度弱于某个Cm,n图。

5.关于偶图，下列说法错误的是( B )

(A) 偶图中不存在奇圈；

(B) 非平凡偶图的最大匹配是唯一的；

(C)

k(k0)正则偶图存在完美匹配；

(D) 偶图中，最大匹配包含的边数等于最小点覆盖包含的顶点数。

三、 (20分)在一个赋权完全图中找到一个具有最小权值的哈密尔顿圈，称这种圈为最优哈密尔顿圈。(1)、用边交换技术方法求出图5中基于初始圈LTPePaNyMcL的近似最优哈密尔顿圈；(2)、如何获取最优哈密尔顿圈权值的一个下界？以图5为例进行说明。

L

60

51

T

13

61

78

2

68

35

21

70

Mc

56

Pe

68

51

Pa

图5

57

Ny

36

3 L

解：(1)

Pe51TL60256Mc21T60512Pa3670Ny51PaL352Pa5113353621McTNy70Mc2170T1351Ny36Pe78McL2Pa21Ny13Pe7813Pe由此获得的一个近似最优解的权值为192.

(2)、假设C是最优哈密尔顿圈，则对于赋权完全图中任意一点v，Cv必然是Gv的一条哈密尔顿路，因此它也是Gv的一棵生成树。由此，若T是Gv的一棵最小生成树，同时e,f是G中与点v相关联的两条边，使得它们的权值之和尽可能小，则W(C)W(T)W(e)W(f)，即获得最优圈的一个下界。

例如，在图5中，取顶点Ny，求出GNy的一棵最小生成树为

4

Pe

T

2

13

51

Mc

L

56

Pa

而与Ny点相关联的两条权值之和尽可能小的边是LNy与LMc,其权值之和为35+21=56.由此获取最优解的一个下界为178.

四，(10分)。矩阵的一行或一列称为矩阵的一条线，利用哥尼定理证明：布尔矩阵中，包含了所有“1”的最少数目，等于具有性质“任意两个1都不在同一条线上的1的最大数目”。（ 注：哥尼定理：在偶图中，最大匹配包含的边数等于最小点覆盖包含的顶点数）

证明：设布尔阵是n行m列矩阵，把它模型为一个偶图如下：每行每列分别用一个点表示，X表示行点集合，Y表示列点集合，两点连线。当且仅当该行该列元为1.

于是，包含了所有“1”的线的最少数目对应偶图中的最小点覆盖数。而具有性质“任意两个1都不在同一条线上的1的最大数目” 对应偶图的最大匹配包含的边数。由哥尼定理，命题得到证明。

5

五．(10分) 求证：设G是n阶的具有m条边的简单连通平面图，则：m3n6。

证明：由于G是n阶的具有m条边的简单连通平面图，所以每个面f的次数deg(f)3。由deg(f)2m得到：m。

f23 由连通平面图的欧拉公式：nm2，将m代入欧拉公式得到

m3n6。

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

解：将动物模型为点，两点连线当且仅当两动物相克(有捕食关系)，根据题目描述，所作图形如下：

23 6 b

f

g

z

w

h

s

k

l p

r

问题转化为求出图的点色数，并用点色数种颜色对其正常点作色。

下面求点色数：一方面，图中存在K3，所以(G)3，另一方面，我们用3种颜色实现了对图的正常顶点作色：

b

1

1

z

f

1

g

1

w

3

h 3

s

2

3

k

3

r

l

2

p

2

所以，至少需要3个围栏。给出的一种最少分组方法为：

第一组：狒狒(b)、狐狸(f)、羚羊(w)和斑马(z)；

第二组：土狼(h)、狮子(l)、豪猪(p)；

第三组：山羊(g)、非洲大羚羊(k)、兔子(r)、鼩鼱(s)。

七．(10分)求下图G的色多项式Pk(G).并求出点色数。

7

图G

解：图G的补图为：

H1 H2

H1的伴随多项式为：H1(x)xx2

对于H2：r10，r21，r34，r41

所以：H32(x)x24xx4

所以：补图的伴随多项式为G(x)xx2x24x3x4x35x45x5x6因此，Pk(G)k(k1)(k2)5k(k1)(k2)(k3)5k(k1)(k2)(k3)(k4)

k(k1)(k2)(k3)(k4)(k5)。

由于k2,Pk(G)0，但k3,Pk(G)0，所以，(G)3。

8