图论试卷及参考答案A-13级数学本科

《图论试卷及参考答案A-13级数学本科》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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．极大平面图所有面的次数均为．第1页共7页二、判断题（每小题2分，共20分）1．图的所有顶点的度数之和是边数的2倍．2．连通图的一个生成树是边数最少的连通生成子图．3．若一个图是欧拉图，那它也一定是哈密顿图．4．图的秩等于图的完全关联矩阵的秩，也等于其关联矩阵的秩．5．r一定是r—正则图的一个特征值．6．图的点连通度小于等于图的边连通度．7．若一个图G存在完美匹配，则该匹配必定是最大匹配．8．图G的一个M—可增广道路未必是一个M—交错道路．9．图的边着色问题可以转化成图的点着色问题．10．设G为p阶、q

4、条边、f个面的连通平面图，则p-q+f=2．第1页共7页三、解答题（每小题5分，共30分）1．试判断下列两个图是否同构．2．写出下图G的一个生成树T并写出图G关于T的基本圈组．E●A●B●C●D●G●F●3．求下图的完全关联矩阵并以v2为参考点写出关联矩阵和一个可逆大子阵．v1v4v3v2e2e3e4e1e54．简述图的点连通度、边连通度、最小顶点的度数三者之间的关系，并举例说明．5．下面的图中加粗的边构成最大匹配吗？如果不是请说明理由．第7页共7页f1f2m1f3f4f5m2m3m4m56．试写出下图的一个着色方案，并回答该图的色数．　v2v3v4v1v5四、应用题（每小题5分

5、，共10分）1．下图是一个公园的平面图，能不能使游人走遍每一条路不重复？入口和出口又应设在哪儿？2．试建立下列问题的数学模型：有两组化学药品X和Y，每组各三类，设和，已知不同组的化学药品不能放在一起，否则会发生爆炸．现在将这些物品存放在三个仓库1，2，3中，但由于物品的特性及仓库自身的物理条件（如有无空调、通风条件等），和第7页共7页只允许放在1号和2号仓库内，和只允许放在2号和3号仓库内，和只允许放在1号和3号仓库内，问：满足要求的存放方案是否存在？若存在，如何存放？五、证明题（每小题10分，共20分）1．设T是一个无向（p,q）图，证明T是树则T无圈且q=p-1．2．设G为p

6、阶连通平面图,有q条边,且每个面的次数不小于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分，不一致（含未做判断）的不得分．三、解答题（每

7、小题5分，共30分）参考答案：第7页共7页1.解：建立一一映射，可知两图同构．……（5分）2.解：因为图的生成树即其连通无圈的生成子图，因此，去掉图的一些边使其保持连通无圈即得其生成树．下图是其中的一种做法．…………（2分）E●A●B●C●D●G●F●关于这棵树的基本圈有6个：AEG，ABG，EFG，BCE，DEF，CDF．（5分）3.解：………………（3分）其中一个可逆的大子阵…………………………………………（5分）4.解：图的点连通度、边连通度、最小顶点的度数三者之间的关系为