欢迎来到天天文库
浏览记录
ID:49567532
大小:198.50 KB
页数:7页
时间:2020-03-02
《图论试卷及参考答案A-13级数学本科.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、专业:________班级:___________学号:_______________________姓名:_____________________——————————————密——————————————封————————————————线———————————专业:__________班级:______学号:_______________________姓名:_____________________——————————————密——————————————封————————————————线———————————**学院2013—2014学年第二学期期末考试数学与应用数学专业
2、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的边交替出现
3、组成的,则称此路径为M-交错道路.9.图G是2-色的当且仅当G是.10.极大平面图所有面的次数均为.word资料二、判断题(每小题2分,共20分)1.图的所有顶点的度数之和是边数的2倍.2.连通图的一个生成树是边数最少的连通生成子图.3.若一个图是欧拉图,那它也一定是哈密顿图.4.图的秩等于图的完全关联矩阵的秩,也等于其关联矩阵的秩.5.r一定是r—正则图的一个特征值.6.图的点连通度小于等于图的边连通度.7.若一个图G存在完美匹配,则该匹配必定是最大匹配.8.图G的一个M—可增广道路未必是一个M—交错道路.9.图的边着色问题可以转化成图的点着色问题.10.设G为p阶、q条边、f个面
4、的连通平面图,则p-q+f=2.word资料三、解答题(每小题5分,共30分)1.试判断下列两个图是否同构.2.写出下图G的一个生成树T并写出图G关于T的基本圈组.E●A●B●C●D●G●F●3.求下图的完全关联矩阵并以v2为参考点写出关联矩阵和一个可逆大子阵.v1v4v3v2e2e3e4e1e54.简述图的点连通度、边连通度、最小顶点的度数三者之间的关系,并举例说明.5.下面的图中加粗的边构成最大匹配吗?如果不是请说明理由.word资料f1f2m1f3f4f5m2m3m4m56.试写出下图的一个着色方案,并回答该图的色数. v2v3v4v1v5四、应用题(每小题5分,共10分)1.
5、下图是一个公园的平面图,能不能使游人走遍每一条路不重复?入口和出口又应设在哪儿?2.试建立下列问题的数学模型:有两组化学药品X和Y,每组各三类,设和,已知不同组的化学药品不能放在一起,否则会发生爆炸.现在将这些物品存放在三个仓库1,2,3中,但由于物品的特性及仓库自身的物理条件(如有无空调、通风条件等),和word资料只允许放在1号和2号仓库内,和只允许放在2号和3号仓库内,和只允许放在1号和3号仓库内,问:满足要求的存放方案是否存在?若存在,如何存放?五、证明题(每小题10分,共20分)1.设T是一个无向(p,q)图,证明T是树则T无圈且q=p-1.2.设G为p阶连通平面图,有q条
6、边,且每个面的次数不小于l(l³3),证明.**学院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分)参考
7、答案:word资料1.解:建立一一映射,可知两图同构.……(5分)2.解:因为图的生成树即其连通无圈的生成子图,因此,去掉图的一些边使其保持连通无圈即得其生成树.下图是其中的一种做法.…………(2分)E●A●B●C●D●G●F●关于这棵树的基本圈有6个:AEG,ABG,EFG,BCE,DEF,CDF.(5分)3.解:………………(3分)其中一个可逆的大子阵…………………………………………(5分)4.解:图的点连通度、边连通度、最小顶点的度数三者之间的关系为
此文档下载收益归作者所有