图论试卷A卷-数本

实用文档*学院20162017学年第二学期期末考试2014级本科数学与应用数学专业图论试卷A（本试卷满分100分，考试时间110分钟）一、 填空题 （每小题2分，共20分）1.图G的两个子图G1，G2的环和表示为_ 2.图G中的一圈，若它通过G中的每一条边(或弧)恰好一次，则称该圈为_3.图G的两个不同的生成的树T1，T2的顶点个数_（填相同或不相同）4“是欧拉图也是哈密顿图”这句话是_。(填对或错)5.图G的任意顶点的关联集都等于其余各顶点关联集的_6.(p,q)图G的基本圈有_个7.连通图G的边连通度定义为 8.设M是G的一个匹配，如果G的每一个顶点都是M-饱和点，则M为_9.使图G为n-着色的最小数值即为G的_10.极大可平面图的每一个面的次数都是_二、判断题（每小题1分，共10分）1.同构的图保持邻接关系2.最小生成树即G的所有生成树中权值最小的生成树3.是欧拉图4.设G是无向连通图，则G是一笔画G中没有奇数度顶点5.图的秩等于图的完全关联矩阵的秩，而不等于其关联矩阵的秩6.图的关联矩阵是对称矩阵7.图的边连通度大于最小顶点的度数8.一个非完全连通图的连通度就是使这个图成为非连通图所需要去掉的最小顶点数9.完美匹配必定是最大匹配，但反之不然10一个图是平面图当且仅当它没有收缩到K5或的子图三、单项选择题（每小题2分，共20分）1. 一个图的所有顶点的度数之和不可能是( )A. 5 B. 6 C. 8 D. 102. 如果连通图G的顶点个数为8，则其生成树中边的个数为( )A. 7 B. 6 C. 9 D. 83. 在如下各图中（ ）欧拉图。4如下右图所示，以下说法正确的是 ( )Aa, e是点割集 Be是割点 Cb, e是点割集 Dd是点割集5. 如果连通图G的顶点个数为7，边数为8，则其向量空间的维数为( )A. 9 B. 8 C. 7 D. 16设无向图G的邻接矩阵为，则G的边数为( ) A3 B4 C5 D67.如果连通图G的点连通度为2，边连通度为3，图的最小顶点的度数可能为（ ）A. 0 B. 1 C. 3 D28.G的一个匹配M中的顶点（ ）M饱和顶点A. 都不是 B. 只有一个是 C. 有些是，有些不是 D.全部是9.如果连通图G的最大顶点的度数3，则图G的色数不可能是（ ）A.2 B. 3 C. 4 D. 510.如果一个图含同胚于（ ）的子图，它可能是可平面图A. B. C. 5阶完全图 D. 四、解答题（每小题10分，共40分）1.下图中各图是否可以一笔画出？请写明理由。（10分）2. 求下图的完全关联矩阵并以v1为参考点写出关联矩阵和一个可逆大子阵（10分）v4e2e5e3v2v3e4e1v13请回答一下问题：（1）试说明下图是否为正则图？请画出该图的一颗生成树；（2）简述四色定理，画出下图的一种顶点着色方案。4.5项工作准备分给5个人去做，如图，其中边（fi,mj)表示fi可以从事mj ，如果每个人最多从事其中一项，且每项工作只能由一人担任问怎样才能使尽可能多的人安派上任务？（10分）f1f2m1f3f4f5m2m3m4m5五、证明题（10分）证明：(平面图欧拉公式) 设G为p阶q条边f个面的连通平面图，则 p-q+f=2. *学院20162017学年第二学期期末考试2014级本科数学与应用数学专业图论参考答案与评分标准A命题教师：*二、 填空题 参考答案：1，；2，链；3, 相同；4，错；5, 环合；6, ；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. 解：这个问题即为：二部图是否存在完美匹配。如图所示，实线表示的即为一种分配方案 （10分）f1f2m1f3f4f5m2m3m4m5评分标准：本部分每小题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）+