图论试卷及参考答案A-13级数学本科
V .. . ..
**学院2013—2014学年第二学期期末考试 数学与应用数学专业2013级《图论》试卷A
（本试卷满分100分，考试时间110分钟）
一、填空题 （每小题2分，共20分） 1．5阶完全图G 的边的个数是___________．
2．如果图G 的每个顶点的度数都相同，则称图G 为________图． 3．当且仅当无向连通图G 的顶点个数比边的个数多1时，图 G 是___． 4．无向图G 为欧拉图当且仅当G 连通，并且所有顶点的度都是 ． 5．(p ,q ) 图G 的向量空间的维数是_________．
6．图G 的任意一个顶点的关联集都是其余各顶点关联集的____． 7．5阶完全图的边连通度是 ．
8．已知M 是图G 的一个 ，若从G 中一个顶点到另一个顶点存
在一条道路，此路径由属于M 和不属于M 的边交替出现组成的，则称此路径为M -交错道路．
9．图G 是2-色的当且仅当G 是 ． 10．极大平面图所有面的次数均为 ． 二、判断题（每小题2分，共20分） 1．图的所有顶点的度数之和是边数的2倍．
2．连通图的一个生成树是边数最少的连通生成子图． 3．若一个图是欧拉图，那它也一定是哈密顿图．
专业：__________ 班级：______ 学号：_______________________ 姓名：_____________________
——————————————密——————————————封————————————————线———————————
专业：________ 班级：___________ 学号：_______________________ 姓名：_____________________ ——————————————密——————————————封————————————————线———————————
V .. . .. 4．图的秩等于图的完全关联矩阵的秩，也等于其关联矩阵的秩．5．r一定是r—正则图的一个特征值．
6．图的点连通度小于等于图的边连通度．
7．若一个图G存在完美匹配，则该匹配必定是最大匹配．8．图G的一个M—可增广道路未必是一个M—交错道路．9．图的边着色问题可以转化成图的点着色问题．
10．设G为p阶、q条边、f个面的连通平面图，则p q+f=2．
三、解答题（每小题5分，共30分） 1．试判断下列两个图是否同构．
2．写出下图G 的一个生成树T 并写出图G 关于T 的基本圈组．
3．求下图的完全关联矩阵并以v 2为参考点写出关联矩阵和一个可逆大子阵．
A
B C
D
G
F
4v
5v 6v 1v
2v 3v
15 u u
43 u u
26 u u
4．简述图的点连通度、边连通度、最小顶点的度数三者之间的关系，并举例说明．
5．下面的图中加粗的边构成最大匹配吗？如果不是请说明理由．
6．试写出下图的一个着色方案，并回答该图的色数．
四、应用题（每小题5分，共10分）
1．下图是一个公园的平面图，能不能使游人走遍每一条路不重复？入口和出口又应设在哪儿？
v 1
v 4
3 v e 2 e 3
4 e f 1
f 2
m 1 f 3
f 4
f 5
m 2 m 3 m 4 m
5
v 2
v 3
v 15
2．试建立下列问题的数学模型：有两组化学药品X 和Y ，每组各三类，设
{}123,,x x x 和{}123,,y y y ，已知不同组的化学药品不能放在一起，否则会发生爆
炸．现在将这些物品存放在三个仓库1，2，3中，但由于物品的特性及仓库自身的物理条件（如有无空调、通风条件等），1x 和1y 只允许放在1号和2号仓库，2x 和2y 只允许放在2号和3号仓库，3x 和3y 只允许放在1号和3号仓库，问：满足要求的存放方案是否存在？若存在，如何存放？ 五、证明题（每小题10分，共20分）
1．设T 是一个无向（p ,q ）图，证明T 是树则T 无圈且q =p -1．
2．设G 为p 阶连通平面图, 有q 条边, 且每个面的次数不小于l (l ≥3), 证明
()≤
l
q p -2l -2
．
**学院2013—2014学年第二学期期末考试 数学与应用数学专业2013级《图论》
参考答案与评分标准A
命题教师：***
二、填空题 （每小题2分，共20分）
参考答案：
1．120；2．正则图；3．树；4．偶数；5．q ;6．环和；7．4；8．匹配；9．二部图；10．3 评分标准：
本部分每小题2分．凡与答案一致或意义相同的得2分，不一致（含空白）的不得分．
三、判断题（每小题2分，共20分） 参考答案：1-5.√√×√√ 6-10.√√×√√ 评分标准：
本部分每小题2分．凡与答案一致的得2分，不一致（含未做判断）的不得分．
三、解答题（每小题5分，共30分）
参考答案：
1.解：建立一一映射,1,2,3,4,5,6i
i v u i =，可知两图同构． ……（5分）
2.解：因为图的生成树即其连通无圈的生成子图，因此，去掉图的一些边使其保持连通无圈即得其生成树．下图是其中的一种做法． …………（2分）
关于这棵树的基本圈有6个：AEG ，ABG ，EFG ，BCE ，DEF ，CDF ．（5分）
3.解：
10011??
?? ?2完全关联矩阵关联矩阵(v 为参考点)
10011E
A
B C
D
G
F
………………（3分）
其中一个可逆的大子阵
100011001??
? ? ???
123
e e e …………………………………………（5分） 4.解：图的点连通度、边连通度、最小顶点的度数三者之间的关系为
k (G )≤λ(G )≤δ (G )． …………………………………………（3分）
下图是无向连通图，点连通度k (G )=1，边连通度λ(G )=2，最小度δ(G )=3，此图满足k (G )≤λ(G )≤δ (G )． …………………………………………（5分）
5.解：
不是最大匹配，因为该图中存在M-可增广道路． ………………（5分） 6.该图是3色的，颜色1：v 1，v 5，颜色2：v 2，v 4，颜色3：v 3． ………（5
f 1
f 2
m 1 f 3
f 4
f 5
m 2 m 3 m 4 m 5
分）
本部分每小题5分，由于某些题的结果不唯一，因此要求只要运用理论正确，结果与答案等价，即得满分；如果有些偏差，酌情扣分；如果关键部分错误，该得分点不得分．
四、应用题（每小题5分，共10分）
参考答案：
1.这个问题可以归结为一笔画问题，一个连通图存在欧拉圈当且仅当图的顶点的度数是偶数．H 点和B 点是奇点，其余都是偶点，所以入口和出口应设在H 点和B 点． ………………（5分）
2.解：以药品为点，两药品不能放在一起则连边，则得到一个二部图，然后再对图中每个点x ，指定一个集合()L x ，用以表示允许存放的仓库和集合，即令()(){}111,2L x L y ==，()(){}222,3L x L y ==，()(){}331,3L x L y ==，如下图所示，于是问题转化为对3,3K 的点着色，但要求对每个点x 的着色，应选用各自的中所罗列的“颜色”，如下图所示：
{}
3
1,3y
{}
2
2,3y
{}
1
1,2x
{}
2
2,3x
{}
3
1,3x
{}1
1,2y