资源描述
专业：_ 班级：_ 学号：_ 姓名：_密封线专业：_ 班级：_ 学号：_ 姓名：_密封线*学院20132014学年第二学期期末考试数学与应用数学专业2013级图论试卷A（本试卷满分100分，考试时间110分钟）一、 填空题 （每小题2分，共20分）15阶完全图G的边的个数是_2如果图G的每个顶点的度数都相同，则称图G为_图3当且仅当无向连通图G的顶点个数比边的个数多1时，图 G是_4无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是 5(p,q) 图G的向量空间的维数是_6图G的任意一个顶点的关联集都是其余各顶点关联集的_75阶完全图的边连通度是 8已知M是图G的一个 ，若从G中一个顶点到另一个顶点存在一条道路，此路径由属于M和不属于M的边交替出现组成的，则称此路径为M-交错道路9图G是2-色的当且仅当G是 10极大平面图所有面的次数均为 二、判断题（每小题2分，共20分）1图的所有顶点的度数之和是边数的2倍2连通图的一个生成树是边数最少的连通生成子图3若一个图是欧拉图，那它也一定是哈密顿图4图的秩等于图的完全关联矩阵的秩，也等于其关联矩阵的秩5r一定是r正则图的一个特征值6图的点连通度小于等于图的边连通度7若一个图G存在完美匹配，则该匹配必定是最大匹配8图G的一个M可增广道路未必是一个M交错道路9图的边着色问题可以转化成图的点着色问题 10设G为p阶、q条边、f个面的连通平面图，则 p-q+f=2三、解答题（每小题5分，共30分）1试判断下列两个图是否同构2写出下图G的一个生成树T并写出图G关于T的基本圈组EABCDGF3求下图的完全关联矩阵并以v2为参考点写出关联矩阵和一个可逆大子阵v1v4v3v2e2e3e4e1e54简述图的点连通度、边连通度、最小顶点的度数三者之间的关系，并举例说明5下面的图中加粗的边构成最大匹配吗？如果不是请说明理由f1f2m1f3f4f5m2m3m4m56试写出下图的一个着色方案，并回答该图的色数v2v3v4v1v5四、应用题（每小题5分，共10分）1下图是一个公园的平面图，能不能使游人走遍每一条路不重复？入口和出口又应设在哪儿？ 2试建立下列问题的数学模型：有两组化学药品X和Y，每组各三类，设和，已知不同组的化学药品不能放在一起，否则会发生爆炸现在将这些物品存放在三个仓库1，2，3中，但由于物品的特性及仓库自身的物理条件（如有无空调、通风条件等），和只允许放在1号和2号仓库内，和只允许放在2号和3号仓库内，和只允许放在1号和3号仓库内，问：满足要求的存放方案是否存在？若存在，如何存放？五、证明题（每小题10分，共20分）1设T是一个无向（p,q）图，证明T是树则T无圈且q=p-12设G为p阶连通平面图, 有q条边, 且每个面的次数不小于l (l 3), 证明 *学院20132014学年第二学期期末考试数学与应用数学专业2013级图论参考答案与评分标准A命题教师：*二、 填空题 （每小题2分，共20分）参考答案：1120；2正则图；3树；4偶数；5q ;6环和；74；8匹配；9二部图；103评分标准：本部分每小题2分凡与答案一致或意义相同的得2分，不一致（含空白）的不得分三、 判断题（每小题2分，共20分）参考答案：1-5. 6-10.评分标准：本部分每小题2分凡与答案一致的得2分，不一致（含未做判断）的不得分三、解答题（每小题5分，共30分）参考答案：1.解：建立一一映射，可知两图同构 （5分）2.解：因为图的生成树即其连通无圈的生成子图，因此，去掉图的一些边使其保持连通无圈即得其生成树下图是其中的一种做法 （2分）EABCDGF 关于这棵树的基本圈有6个：AEG，ABG，EFG，BCE，DEF，CDF（5分）3.解： （3分）其中一个可逆的大子阵 （5分）4.解：图的点连通度、边连通度、最小顶点的度数三者之间的关系为k(G)l(G)d (G) （3分）下图是无向连通图，点连通度k(G)=1，边连通度l(G)=2，最小度d(G)=3，此图满足k(G)l(G)d (G) （5分）5.解： f1f2m1f3f4f5m2m3m4m5不是最大匹配，因为该图中存在M-可增广道路 （5分）6.该图是3色的，颜色1：v1，v5，颜色2：v2，v4，颜色3：v3 （5分）本部分每小题5分，由于某些题的结果不唯一，因此要求只要运用理论正确，结果与答案等价，即得满分；如果有些偏差，酌情扣分；如果关键部分错误，该得分点不得分四、 应用题（每小题5分，共10分）参考答案：1.这个问题可以归结为一笔画问题，一个连通图存在欧拉圈当且仅当图的顶点的度数是偶数H点和B点是奇点，其余都是偶点，所以入口和出口应设在H点和B点 （5分）2.解：以药品为点，两药品不能放在一起则连边，则得到一个二部图，然后再对图中每个点，指定一个集合，用以表示允许存放的仓库和集合，即令，如下图所示，于是问题转化为对的点着色，但要求对每个点的着色，应选用各自的中所罗列的“颜色”，如下图所示： 实际上，本问题的着色不存在 （5分）评分标准：本部分每小题5分，考生每解出一个步骤，得相应的分数由于某一步单纯计算错误而导致其后数据错误，但方法正确的，酌情给分五、 证明题（每小题10分，共20分）参考答案：1.证明:由树的定义可知T无圈下证q=p-1对p进行归纳证明 当p=1时，q=0，显然q=p-1 假设p=k时结论成立，现证明p=k+1时结论也成立 （2分）由于树是连通而无圈的，所以至少有一个度数为1的顶点，在T中删去及其关联边，便得到个顶点的连通无圈图 （4分）由归纳假设它有k-1条边再将顶点及其关联边加回得到原图T，所以T中含有k+1个顶点和k条边，故结论q=p-1成立所以树是无圈且q=p-1的图即q=k+1时结论成立 （10分）2.证明：由于在计算面数之和时，每个边被计算了两次，因此各面次数之和等于边数的2倍，再由欧拉公式得： （5分） 2q lf = l (2+q-p) （10分）评分标准：本部分每小题10分，根据参考答案的答题要点给分。要求只要运用理论正确，结果与答案等价，即得满分；如果有些偏差，酌情扣分；如果关键部分错误，该得分点不得分
展开阅读全文