图论试卷A卷-14数本

1、*学院2016 2017学年第二学期期末考试2014级本科数学与应用数学专业图论试卷（本试卷满分100分，考试时间110分钟）一、填空题（每小题2分，共20分）1. 图G的两个子图G1，G2的环和表示为.2图G中的一圈，若它通过G中的每一条边（或弧）恰好一次，则称该圈为3. 图G的两个不同的生成的树T1, T2的顶点个数.（填相同或不相同）4. K3,3是欧拉图也是哈密顿图”这句话是 。（填对或错）5. 图G的任意顶点的关联集都等于其余各顶点关联集的 .6. （p,q）图G的基本圈有 .7. 连通图G的边连通度定义为 .8. 设M是G的一个匹配，如果G的每一个顶点都是M-饱和点，则M为9. 使

2、图G为n-着色的最小数值即为G的.10. 极大可平面图的每一个面的次数都是.二、判断题（每小题1分，共10分）1. 同构的图保持邻接关系.2. 最小生成树即G的所有生成树中权值最小的生成树.3. K5是欧拉图.4. 设G是无向连通图，则G是一笔画 G中没有奇数度顶点.5. 图的秩等于图的完全关联矩阵的秩，而不等于其关联矩阵的秩.6. 图的关联矩阵是对称矩阵.7. 图的边连通度大于最小顶点的度数.8. 一个非完全连通图的连通度就是使这个图成为非连通图所需要去掉的最小顶点数.9. 完美匹配必定是最大匹配，但反之不然.10. 一个图是平面图当且仅当它没有收缩到 K5或K3,3的子图.三、单项选择题（

3、每小题2分，共20分）1. 一个图的所有顶点的度数之和不可能是（）A.5B. 6C. 8D. 102. 如果连通图G的顶点个数为8,则其生成树中边的个数为（）A.7B. 6C. 9D.83. 在如下各图中（）欧拉图。第5页共7页4如下右图所示，以下说法正确的是（）.A . a,e是点割集B. e是割点C. b, e是点割集D. d是点割集5.如果连通图G的顶点个数为7,边数为8,则其向量空间的维数为（）A. 9B.8C. 7D.16设无向图G的邻接:矩阵为0 11001 00111 0000 ,0 10010 1010则G的边数为（）.A . 3B . 4C .5D. 67. 如果连通图G的点

4、连通度为2,边连通度为3,图的最小顶点的度数可能为（）A. 0 B. 1 C. 3 D. 28. G的一个匹配M中的顶点（）M饱和顶点A.都不是 B.只有一个是C.有些是，有些不是D.全部是9. 如果连通图G的最大顶点的度数3,则图G的色数不可能是（）A.2 B. 3 C. 4 D. 510. 如果一个图含同胚于（）的子图，它可能是可平面图A. KsB. K3,3C. 5 阶完全图D. K3四、解答题（每小题10分，共40分）1.下图中各图是否可以一笔画出？请写明理由。（10分）(1) 2. 求下图的完全关联矩阵并以 v1为参考点写出关联矩阵和一个可逆大子阵(10 分)3请回答一下问题：（1）

5、试说明下图是否为正则图？请画出该图的一颗生成树；（2）简述四色定理，画出下图的一种顶点着色方案。El4.5项工作准备分给5个人去做，如图，其中边（fi,mj）表示fi可以从事mj , 如果每个人最多从事其中一项，且每项工作只能由一人担任.问怎样才能使尽可能多的人安派上任务？ （ 10分）（10 分）五、证明题证明：平面图欧拉公式）设G为p阶q条边f个面的连通平面图，贝U p q+f=2.* 学院 20162017 学年第二学期期末考试2014 级本科数学与应用数学专业图论 参考答案与评分标准 A 命题教师： *二、填空题参考答案：1， G1 G2 ；2，链； 3, 相同； 4，错； 5, 环合

6、；6, q p 1 ；7，使得连通 图 G 变为不连通的边割集的最小边数； 8 ，完美匹配； 9 ，色数； 10,3评分标准：本部分每小题 2 分。凡与答案一致的得 2 分，不一致（含空白）的不得分三、判断题 参考答案：1-5WVxx6-10. xxWV评分标准： 本部分每小题 1 分。凡与答案一致的得 1 分，不一致（含未作判断）的不 得分。三、单项选择题 参考答案： 1-5 AABBB 6-10 CCDDD评分标准：本部分每小题 2 分。凡与答案一致的得 2 分，不一致（含未选）的不得分四、解答题参考答案：1.解：一个图是“一笔画”当且仅当奇数度顶点的个数是 0或2个，因此（2）（3）（

7、4）是“一笔画”。 （10分）2.解：完全关联矩阵关联矩阵（V1为参考点）100111100011000T 01101011010011000110一个可逆的大子阵ei e2 31 1 00 i i（W 分）1本题答案不唯一，答对即可。3. 解：（1）不是为正则图，因为各个顶点的度数不完全相同。该图的生成树不唯一，只要是该图的子图当中含七条边的树即 可。（10分）（2）四色定理即在一张地图中，给地图的各地域着色，要使邻接的地域具有 不同的颜色，四种颜色足够，该图的色数为 3，顶点着色方案不唯一，符合题意即可。（10分）4解：这个问题即为：二部图 G ：V1,V2，E是否存在V 完美匹配。如图所

8、 示， 实线 表示 的 即 为一种 分配方 案（10分）f1f2f3f4f5m1m2m3m4m5f1f2f3f4f5评分标准:本部分每小题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 分) 若G中有圈，则删去一个圈上的一条边，记作G . G连通，有p个顶点,q-1 条边和f-1个面.由归纳假设，p- (