2015电子科技大学研究生试卷答案

时间:2025-07-11

1

一.填空题(每空

3分,共15分)

1.不同构的3阶简单图的个数为__4___。 2.图1中的最小生成树的权值为__20____。 3.基于图2的最优欧拉环游的总权值为____37___。 4.图3中块的个数为___4____。

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

二.单项选择(每题3分,共15分)

1.关于图的度序列,下列命题错误的是( D ) (A) 同构的两个图的度序列相同;

(B) 非负整数序列12(,,,)n d d d 是图的度序列当且仅当1n

i i d =∑是偶数;

(C) 如果非负整数序列12(,,,)n d d d (2)n ≥是一棵树的度序列,那么序列

6 图1

图2

3

图4

2 中至少有两个整数的值为1;

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

2.关于n 阶简单图的邻接矩阵()ij n n A a ⨯=,下列说法错误的是( C )

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

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

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

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

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

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

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

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

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

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

(A)设G 是3n ≥的简单图,若其闭包是完全图,则G 是哈密尔顿图;

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

(C)若G 是哈密尔顿图,则对于V 的每个非空顶点子集S ,均有()G S S ω-≤;

(D) 若G 是3n ≥的非H 单图,则G 度弱于某个,m n C 图。

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

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

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

(C) (0)

k k 正则偶图存在完美匹配;

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

三、 (20分)在一个赋权完全图中找到一个具有最小权值的哈密尔顿圈,称这种圈为最优哈密尔顿圈。(1)、用边交换技术方法求出图5中基于初

始圈

e a y c

LTP P N M L的近似最优哈密尔顿圈;(2)、如何获取最优哈密尔顿圈权值的一个下界?以图5为例进行说明。

解:(1)

51

60 56

70

21

35

36

57

68

78

68

51

13

61

2

L

T

P e

Pa

Ny

Mc

图5

T

Pe

Pa

Mc

21

T

Pe

Pa

Mc

36

L

3

4

由此获得的一个近似最优解的权值为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 -的一棵最小生成树为

T

Pe

Pa

Mc

36

T

Pe Pa Ny

Mc

35

2170

1351

2

L

51

56

13

2

L

T

P e

Pa

Mc

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

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

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

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

五.(10分) 求证:设G 是n 阶的具有m 条边的简单连通平面图,则:

36m n ≤-。

证明:由于G 是n 阶的具有m 条边的简单连通平面图,所以每个面f 的次数deg()3f ≥。由deg()2f f m ∈Φ=∑得到:23

m φ≤。

由连通平面图的欧拉公式:2n m φ-+=,将23

m φ≤代入欧拉公式得到 36m n ≤-。 六.(20分) 一家公司计划建造一个动物园,他们打算饲养下面这些动物:狒狒(b)、狐狸(f)、山羊(g)、土狼(h)、非洲大羚羊(k)、狮子(l)、豪猪(p)、兔子(r)、鼩鼱(s)、羚羊(w)和斑马(z)。根据经验,动物的饮食习惯为:狒狒喜欢吃山羊、非洲大羚羊(幼年)、兔子和鼩鼱;狐狸喜欢吃山羊、豪猪、兔子和鼩鼱;土狼喜欢吃山羊、

6 非洲大羚羊、羚羊和斑马;狮子喜欢吃山羊、非洲大羚羊、羚羊和斑马;豪猪喜欢吃鼩鼱和兔子;而其余的则喜欢吃虫子、蚯蚓、草或其它植物。公司将饲养这些动物,希望它们能自由活动但不能相互捕食。求这些动物的一个分组,使得需要的围栏数最少。(要求用图论方法求解)

解:将动物模型为点,两点连线当且仅当 …… 此处隐藏:897字,全部文档内容请下载后查看。喜欢就下载吧 ……

2015电子科技大学研究生试卷答案.doc 将本文的Word文档下载到电脑

    精彩图片

    热门精选

    大家正在看

    × 游客快捷下载通道(下载后可以自由复制和排版)

    限时特价:7 元/份 原价:20元

    支付方式:

    开通VIP包月会员 特价:29元/月

    注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
    微信:fanwen365 QQ:370150219