图论试卷A卷-14数本

《图论试卷A卷-14数本》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、**学院2016—2017学年第二学期期末考试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是

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

3、然．10．一个图是平面图当且仅当它没有收缩到K5或的子图．第7页共7页三、单项选择题（每小题2分，共20分）1.一个图的所有顶点的度数之和不可能是()A.5B.6C.8D.102.如果连通图G的顶点个数为8，则其生成树中边的个数为()A.7B.6C.9D.83.在如下各图中（）欧拉图。4．如下右图所示，以下说法正确的是()．A．{a,e}是点割集B．e是割点C．{b,e}是点割集D．{d}是点割集5.如果连通图G的顶点个数为7，边数为8，则其向量空间的维数为()A.9B.8C.7D.16．设无向图G的邻接矩阵为，则G的边数为()．A．3B．4C．5D．67.如果连通图G的点连通度为2，边连通

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

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

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

7、（10分）本题答案不唯一，答对即可。3.解：（1）不是为正则图，因为各个顶点的度数不完全相同。该图的生成树不唯一，只要是该图的子图当中含七条边的树即可。……………………（10分）（2）四色定理即在一张地图中，给地图的各地域着色，要使邻接的地域具有不同的颜色，四种颜色足够，该图的色数为3，顶点着色方案不唯一，符合题意即可。……………（10分）4.解：这个问题即为：二部图是否存在―完美匹配。如图所示，实线表示的即