2023年研究生试卷 图论评分细则

发布 2020-05-18 00:08:28 阅读 1175

电子科技大学研究生试卷。

(考试时间: 至 ,共__2_小时)

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

教学方式讲授考核日期_2012__年___月___日成绩

考核方式学生填写)

一、填空题(填表题每空1分,其余每题2分,共30分)

1.阶正则图g的边数=;

2.3个顶点的不同构的简单图共有个;

3.边数为的简单图的不同生成子图的个数有个;

4. 图与图的积图的边数为;

5. 在下图中,点到点的最短路长度为;

6. 设简单图的邻接矩阵为,且,则图的边数为。

7. 设是n阶简单图,且不含完全子图,则其边数一定不会超过;

8.的生成树的棵数为;

9. 任意图的点连通度、边连通度、最小度之间的关系为。

10. 对下列图,试填下表(是类图的打〝√ 否则打〝 〞

二、单项选择(每题2分,共10分)

1.下面命题正确的是 ( b )

对于序列,下列说法正确的是:

a) 是简单图的度序列;

b) 是非简单图的度序列;

c) 不是任意图的度序列;

d) 是图的唯一度序列。

2.对于有向图,下列说法不正确的是 ( d )

a) 有向图中任意一顶点只能处于的某一个强连通分支中;

b) 有向图中顶点可能处于的不同的单向分支中;

c) 强连通图中的所有顶点必然处于强连通图的某一有向回路中;

d) 有向连通图中顶点间的单向连通关系是等价关系。

3.下列无向图可能不是偶图的是 ( d )

a) 非平凡的树;

b) 无奇圈的非平凡图;

c) 方体;

d) 平面图。

4.下列说法中正确的是 ( c )

a) 连通3正则图必存在完美匹配;

b) 有割边的连通3正则图一定不存在完美匹配;

c) 存在哈密尔顿圈的3正则图必能1因子分解;

d) 所有完全图都能作2因子分解。

5. 关于平面图,下列说法错误的是( b )

a) 简单连通平面图中至少有一个度数不超过5的顶点;

b) 极大外平面图的内部面是三角形,外部面也是三角形;

c) 存在一种方法,总可以把平面图的任意一个内部面转化为外部面;

d) 平面图的对偶图也是平面图。

三、 (10分) 设与其补图的边数分别为,求的阶数。

解:设的阶数为。

因4分。所以2分。

得4分。四、(10分) 求下图的最小生成树(不要求中间过程,只要求画出最。

小生成树, 并给出t的权和)。

五、(10分) (1). 求下图的k色多项式; (2). 求出的点色数 ;

3). 给出一种使用种颜色的着色方法。

解:(1)、图g的补图为:(2分)

1分。对于:,所以,其伴随多项式为:

1分。所以1分。

于是色多项式。

k (k-1) (k-2)[2+4(k-3) +k-3) (k-4)] k(k-1)2 (k-2)2

2分。解法22分。

k-13分。

(k-1)[ k(k-1) (k-2)2]

k(k-1)2 (k-2)22分。

(2)、由于,所以,点色数=3;……2分。

3)、点着色:(1分)

六、(10分) 5个人被邀请参加桥牌比赛。桥牌比赛规则是每一场比赛由两个2人组进行对决。要求每个2人组都要与其它2人组(w,z )进行对决。

若每个人都要与其他任意一个人组成一个2人组,且每个组在同一天不能有多余一次的比赛,则最少安排多少天比赛(每一天可以有多场比赛)?请给出相应的一个时间安排表。(用图论方法求解)

解:(1)、建模:5个人能够组成10个2人组:ab, ac, ad, ae, bd, bc,

be, cd , ce, de。

以每个2人组作为顶点,因要求每个2人组都与其它2人组比赛,所以,得到比赛状态图如下:

4分。2)、最少安排多少天比赛转化为求状态图的边色数。

因为彼得森图不可1因子分解,于是可推出,又可用4种色对其正常边着色(见下图),所以:。

所以2分。3)、安排时间表:

第一天:ab---de, ae---bc, ac---be, ad---ce;

第二天:ab---ce, ac---de, ae---bd, ad---bc, be---cd ;

第三天:ab---cd, bc---de, bd---ce;

第四天:ac---bd, ad---be, ae---cd。

4分。七、(10分 ) 由于在考试中获得好成绩,6名学生将获得下列书籍的奖励,分别是:代数学(a),微积分(c),微分方程(d),几何学(g),数学史(h),规划学(p),拓扑学(t)。

每门科目只有1本书,而每名学生对书的喜好是:

a:d, h, t ;b: h, t ;c:d, h ;d:d, t ;e:a, c, d ; f::c, d, p, g 。

每名学生是否都可以得到他喜欢的书?为什么?(用图论方法求解)

解:由题意,得模型图:(4分)

问题转化为是否存在饱和a,b,c,d,e,f的匹配存在2分。

取顶点子集合,因,所以。

由霍尔定理知:不存在饱和a,b,c,d,e,f的匹配。

故每名学生不能都得到他喜欢的书4分。

八、(10分) 若为偶数,且单图g满足:,求证:中有3因子。

证明:因单图g满足:,所以中存在哈密尔顿圈。 2分。

又因为偶数,所以,可分解为两个1因子,它们显然也是图g的两个1因子3分。

考虑,则,于是,中存在哈密尔顿圈。 2分。

作,则为g的一个3因子3分。

2023年研究生图论试卷

电子科技大学研究生试卷。考试时间 至 共 2 小时 课程名称图论及其应用教师学时 60 学分 教学方式讲授考核日期 2011 年 月 日成绩 考核方式学生填写 一 填空题 每空1分,共22分 1 若n阶单图g的最小度是,则其补图的最大度 2 若图,则它们的积图的顶点数 边数 3 设是图的推广邻接矩阵...

2023年机电学院研究生学业奖学金评审细则 2

机电学院研究生奖学金评定细则。按照研究生院 关于评定2015年研究生学业奖学金的通知 研函 2015 117号,特制订机电学院研究生奖学金评定办法 一 奖学金评定范围。2014级全体在籍研究生 2015全体在籍研究生 不含有工资收入或定向单位报销学费的定向研究生生 二 名额分配 按照研究生院 关于评...

12年研究生试卷

电子科技大学研究生试卷。考试时间 至 共 2 小时 课程名称图论及其应用教师学时 60 学分 教学方式讲授考核日期 2012 年 月 日成绩 考核方式学生填写 一 填空题 填表题每空1分,其余每题2分,共30分 1 阶正则图g的边数 2 3个顶点的不同构的简单图共有个 3 边数为的简单图的不同生成子...