电子科技大学研究生试卷。
（考试时间： 至 ，共__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 边数为的简单图的不同生成子...