**学院2016—2017学年第二学期期末考试2014级本科数学与应用数学专业《图论》试卷A
（本试卷满分100分，考试时间110分钟）
一、填空题（每小题2分，共20分）
1.图G的两个子图G1，G2的环和表示为_______．
2.图G中的一圈，若它通过G中的每一条边(或弧)恰好一次，则称该圈为____．
3.图G的两个不同的生成的树T1，T2的顶点个数_______．（填相同或不相同）4．“3,3
K是欧拉图也是哈密顿图”这句话是_______。
(填对或错)
5.图G的任意顶点的关联集都等于其余各顶点关联集的____．
6.(p,q)图G的基本圈有_________个．
7.连通图G的边连通度定义为．
8.设M是G的一个匹配，如果G的每一个顶点都是M-饱和点，则M为______．
9.使图G为n-着色的最小数值即为G的_________．
10.极大可平面图的每一个面的次数都是_________．
二、判断题（每小题1分，共10分）
1.同构的图保持邻接关系．
2.最小生成树即G的所有生成树中权值最小的生成树．
K是欧拉图．
3.
5
4.设G是无向连通图，则G是一笔画 G中没有奇数度顶点．
5.图的秩等于图的完全关联矩阵的秩，而不等于其关联矩阵的秩．
6.图的关联矩阵是对称矩阵．
7.图的边连通度大于最小顶点的度数．
8.一个非完全连通图的连通度就是使这个图成为非连通图所需要去掉的最小顶点数．
9.完美匹配必定是最大匹配，但反之不然．
K的子图．
10．一个图是平面图当且仅当它没有收缩到K5或
3,3
三、单项选择题（每小题2分，共20分）
1. 一个图的所有顶点的度数之和不可能是( )
A. 5
B. 6
C. 8
D. 10
2. 如果连通图G 的顶点个数为8，则其生成树中边的个数为( )
A. 7
B. 6
C. 9
D. 8
3. 在如下各图中（ ）欧拉图。
4．如下右图所示，以下说法正确的是 ( )．
A ．{a, e }是点割集
B ．e 是割点
C ．{b , e }是点割集
D ．{d }是点割集
5. 如果连通图G 的顶点个数为7，边数为8，则其向量空间的维数为( )
A. 9
B. 8
C. 7
D. 1
6．设无向图G 的邻接矩阵为
⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡010*******
000011100100110， 则G 的边数为( )．
A ．3
B ．4
C ．5
D ．6
7.如果连通图G 的点连通度为2，边连通度为3，图的最小顶点的度数可能为（ ）
A. 0
B. 1
C. 3 D ．2
8.G 的一个匹配M 中的顶点（ ）M 饱和顶点
A. 都不是
B. 只有一个是
C. 有些是，有些不是
D.全部是
9.如果连通图G 的最大顶点的度数3，则图G 的色数不可能是（ ）
A.2
B. 3
C. 4
D. 5
10.如果一个图含同胚于（ ）的子图，它可能是可平面图
A.5K
B. 3,3K
C. 5阶完全图
D. 3K
四、解答题（每小题10分，共40分）
1.下图中各图是否可以一笔画出？请写明理由。
（10分）
2. 求下图的完全关联矩阵并以v 1为参考点写出关联矩阵和一个可逆大子阵（10分）
3．请回答一下问题：（1）试说明下图是否为正则图？请画出该图的一颗生成树；（2）简述四色定理，画出下图的一种顶点着色方案。
4
e 2 3
v 4 v 1
4.5项工作准备分给5个人去做，如图，其中边（f i ,m j )表示f i 可以从事m j ，如果每个人最多从事其中一项，且每项工作只能由一人担任．问怎样才能使尽可能多的人安派上任务？（10分）
五、证明题（10分）
证明：(平面图欧拉公式) 设G 为p 阶q 条边f 个面的连通平面图，则 p q +f =2.
f 1 f 2 m 1 f 3 f 4 f 5
m 2 m 3 m 4 m 5
**学院2016—2017学年第二学期期末考试
2014级本科数学与应用数学专业《图论》
参考答案与评分标准A
命题教师：***
二、填空题
参考答案：
1，12G G ⊕；2，链；3, 相同；4，错；5, 环合；6, 1q p -+；7，使得连通图G 变为不连通的边割集的最小边数；8，完美匹配；9，色数；10,3
评分标准：
本部分每小题2分。
凡与答案一致的得2分，不一致（含空白）的不得分。
三、判断题
参考答案：
1-5 √√√×× 6-10. ××√√√
评分标准：
本部分每小题1分。
凡与答案一致的得1分，不一致（含未作判断）的不得分。
三、单项选择题
参考答案：1-5 AABBB 6-10 CCDDD
评分标准：
本部分每小题2分。
凡与答案一致的得2分，不一致（含未选）的不得分。
四、解答题
参考答案：
1. 解：一个图是“一笔画”当且仅当奇数度顶点的个数是0或2个，因此（2）
（3）（4）是“一笔
画”。
……………………… （10分）
2. 解：
………………
………（10分） 本题答案不唯一，答对即可。
3. 解：（1）不是为正则图，因为各个顶点的度数不完全相同。
该图的生成树不唯一，只要是该图的子图当中含七条边的树即可。
……………………（10分）
（2）四色定理即在一张地图中，给地图的各地域着色，要使邻接的地域具有不同的颜色，四种颜色足够，该图的色数为3，顶点着色方案不唯一，符合题意即可。
……………（10分）
4. 解：这个问题即为：二部图12,,G V V E =是否存在1V ―完美匹配。
如图所示，实线表示的即为一种分配方案 ………………… （10分）
评分标准：
f 1 f 2 m 1 f 3 f 4 f 5
m 2 m 3 m 4 m
5 ⎛⎫⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎛⎫ ⎪ ⎪ ⎪⎝⎭1100001101001101100110011完全关联矩阵关联矩阵(v 为参考点)1001111000→01101一个可逆的大子1阵0010123 e e e
本部分每小题10分，考生每解出一个步骤，得相应的分数。
由于某一步单纯计算错误而导致其后数据错误，但方法正确的，可以在不超过该部分应得分一半的范围内给分。
五、证明题
参考答案：
证明：（1）若G中无圈, 则G为无圈连通图，是一颗树，必有一个度数为1的顶点v, 删除v及与它关联的边, 记作G ?. G ?连通无圈, 有p-1个顶点, 条边和f个面. 由归纳假设,
(p-1)-（q-1）+f=2,
即p-q+f=2, 得证q=k+1时结论成立. ………………（5分）
(2) 若G中有圈,则删去一个圈上的一条边,记作G ?. G ?连通, 有p个顶点,q-1条边和f-1个面. 由归纳假设,
p- （q-1）+（f-1）=2,
即p-q+f=2,得证. 证毕. ………………（10分）
评分标准：
本部分共10分，根据参考答案的答题要点给分。
对于应用理论不准确的或不完全者，酌情扣分；关键词错误的不予给分。
如果解题过程与参考答案不一致但解题正确的也应相应给分。