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

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

1、**学院2013—2014学年第二学期期末考试数学与应用数学专业2013级《图论》试卷B（本试卷满分100分，考试时间110分钟）一、填空题（每小题2分，共20分）1.每一对不同的顶点都邻接的简单图称为完全图，n阶完全图记为2.树7；无圈，但增加任一新边，得到且仅得到一个。3•图G中的一个圈，若它通过G中每个顶点恰好一次，则该圈称为—o4.图G（p,q丿的基本圈有个。5.图的所有顶点的关联集线性（填相关与无关）。6.6阶完全图的连通度是o7.图的边着色要求的边着不同的颜色。8.M为的充要条件是：图G中不存在M-可增广道路。9.若M是图G二（V,E）的边子集，且M中

2、的任意两条边在G中不相邻,则称M为G中的一个o10.G的所有面的次数之和等于边数的倍。二、判断题（每小题2分，共20分）1.同构的两个图顶点数相同。2.G㊉G?中的边数一定比G中的边多。3.最小生成树即G的所有生成树中权最小的生成树。4.连通图的秩与其关联矩阵的秩不相等。5•在图的邻接矩阵中每一行中的1的个数表示相应顶点的度数。6•图的连通度、边连通度、顶点的最小度数三者可能相等。7.无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是偶数。8•—个非平凡连通图的连通度就是使这个图成为非连通图所需要去掉的最小边数。9•设G为长度大于或等于3的奇圈，则”（G）二3。

3、10.—个图是平面图当且仅当它没有收缩到叫,3和岭的子图。三、解答题（每小题5分，共30分）1•设G],G?如图所示，求它们的环和。2.写出下图G的一个生成树卩并写出图G关于T的基本圈组.3•求下图的邻接矩阵.4.写出下面两个图的点连通度、边连通度。5•下面的图屮加粗的边构成最大匹配吗？如果不是请说明理由.6•试写岀该图的色数，并回答与该图有关的一个定理.四、应用题（每小题5分，共10分）1.甲乙两个邮递员去送信，两人以同样的速度走遍所有的街道，甲从A点岀发，乙从3点出发，最后都回到邮局（C点）。如果要选择最短的线路，谁先回到邮局？A2.一个工厂有3个车间和3个仓

4、库。为了工作需要，车间与仓库之间将设专用的车道。为避免发牛车祸，应尽量减少车道的交叉点，最好是没有交叉点，这是否可能？五、证明题（每小题10分，共20分）1.证明：无向图G有生成树的充分必要条件是G为连通图。2.证明：设G是有〃个顶点（n>3）,e条边的简单平面图，贝^<3/1-60**学院2013—2014学年第二学期期末考试数学与应用数学专业2013级《图论》参考答案与评分标准B命题教师：***一、填空题（每小题2分，共20分）参考答案:l.Kn；2•圈；3•哈密顿圈;4.q-p+1；5.相关;6.5；7.邻接；8.最大兀配；9.兀配；10.2评分标准：本部分

5、每小题2分。凡与答案一致或含义相同的得2分，不一致（含空白）的不得分。二、判断题（每小题2分，共20分）参考答案：1-5VXVXV6-10.VVXVV评分标准：本部分每小题2分。凡与答案一致的得2分，不一致（含未判断）的不得分。三、解答题（每小题5分,共30分）参考答案：1.解：1J><>53“/XrG㊉G?（5分）2.解：因为图的生成树即其连通无圈的生成子图，因此，去掉图的一些边使其保持连通无圈即得其生成树.下图是其中的一种做法.（2分）D关于这棵树的基木圈有3个：ACD,BCD,ABC.（5分）1.所求邻接矩阵为：勺DM）〔3<00011V兀2000111兀3

6、000111（5分）>1111000111000>311000；2.解：左图的点连通度R（G）=1,边连通度九（G）=2・（2.5分）右图的点连通度k（G）=2,边连通度X（G）=2・（5分）3.不是最大匹配，因为该图中存在可增广道路.（5分）4.该图是2■色的，这个图是二部图。一个图是2■色的当且仅当该图是二部图.（5分）本部分每小题5分，由于某些题的结果不唯一，因此要求只要运用理论正确，结果与答案等价，即得满分；如果有些偏差，酌情扣分；如果关键部分错误，该得分点不得分.四、应用题（每小题5分，共10分）参考答案：1.解：该问题归结为一笔画问题。图中A,C为奇点

7、，其余都是偶点。甲从A点出发，可以不重复到达C点。乙从B出发一定会走重复的路，所以甲先回到邮局。（5分）1.这是《3,3的可平面性问题。如图⑺）所示，A,B,c是3个车间，M,N,P是3座仓库。经过努力表明，要想建造不相交的道路是不可能的，但可以使交叉点最少（如图@）所示）。（5分）评分标准：本部分每小题5分，考生每解出一个步骤，得相应的分数.由于某一步单纯计算错误而导致其后数据错误，但方法止确的，酌情给分.五：证明题（每小题10分，共20分）参考答案：1.证明：先用反证法来证明必要性。若G不连通，则它的任何生成子图也不连通，则不可能有生成树，与G有生成树矛盾，故

8、G是连通图