图论期末复习题(16年)ppt课件

1、图论期末复习,一、填空题 1. 任意两个顶点都_的简单图称为完全图 2如果G=(V,E)中任何顶点都是连通的，则称图G是连通的；否则称G为 3. 如果无向图的顶点集V分成两个子集V1, V2,(即满足V1 V2 =, V1 V2 =V),使得G中任意一边的两个端点分属于V1和V2,则称G为-,1,5.完全二部图 中边的个数为_ 6.设是具有个p顶点的一棵树，则的边数一定为_ 7在任何图中，度数为奇数的顶点个数必为_,4图G是二部图的充分必要条件是G是不含- 的非平凡图,2,86阶完全图G的边的个数是_ 9. 边数最少的连通图是 。 10. G是有40个点的简单图且G中任两个点之间有且只有1条路

2、，则 G是 。 11若G有32个点的连通图，且对G每条边e，G-e非连通，则G的边数为,3,12.若G有n个顶点的是 k-正则图，则G的边数为 。 13.简单图 G满足 ，则G是 图。 14.如果连通图G的所有顶点的度数均为_，则称图G为欧拉图 15.若G 是有31个点的连通图且G 中每条边都是割边，则q(G) 。 16.G 是含有56个顶点的无圈图，且对中任两个不相邻的顶点u,v，+uv有唯一的圈，则的边数为_;,4,17G是Euler图G连通且每个点度数均为_ 18.e为G的割边 e不在G的任一_中。 19.无向连通图G是欧拉图的充分必要条件是G不含顶点。 20连通图G具有欧拉路而无欧拉圈

3、当且仅当G恰有个奇数度顶点 21.无向图的关联矩阵每一行元素之和等于对应顶点的,5,22一个具有6个顶点的连通图G的秩为_ 23一个具有5个顶点的连通图G的秩_ 247阶完全图的边连通度是_ 25(6,9)图G的向量空间的维数是_ 26(5,8)图G的向量空间的维数是_ 27连通简单图G的关联矩阵的一个大子阵是非奇异的充要条件为与这个大子阵的列相应的边，组成G的_ 28.G的_是使得G不连通或成为平凡图所必须删除的顶点的最小个数 29设M为G的一个匹配，则M中的任意两条边都_（填是或不是）邻接的,6,30设M为G的一个匹配，则M中的任意两条边都_（填是或不是）邻接的 31设M1和M2是图G的两

4、个不同匹配,由M1M2导出的G的边导出子图记作H,则H的任意连通分支是下列情况之一：(1)边在M1和M2中交错出现的偶圈;(2)边在M1和M2中交错出现的 ,7,32二部图G中若满足V1= V2，则G必有完美匹配 33(G)=2 G是 34.若最大匹配的边数为p(G)/2，则说明该图_（填存在或不存在）完美匹配 35.在计算平面图面的次数之和时，每条边边计算了_次 36一个图是平面图当且仅当它既没有收缩到K5的子图，也没有收缩到 的子图 37如果一个平面图有一个面的次数为4，则该图_（填是或不是）极大平面图,8,三、判断题,1若途径中的所有点互不相同，则称此途径为一条链 2若途径中的所有边互不

5、相同，则称此途径为一条道路 3任何无圈的图均是二部图 4两图即使满足顶点数相等、边数相等和度数相同的顶点数相等这三个条件，也不一定同构 5在树中至少存在两个度为1的顶点（树叶）,9,6G是含有56个顶点的无圈图，且对G中任两个不相邻的顶点u,v，G+uv有唯一的圈，则G的边数为55 7凡是由奇数点组成的连通图，一定可以一笔画成 8凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完 9.哈密顿图一定是欧拉图，而欧拉图未必是哈密顿图 10.具有5个顶点8条边的连通图有5个不同的基本圈组 11连通图G的关联矩阵M的一个大子阵是非奇异的充要条件是与这个大子阵的列相应的边组成G的一颗生成树.,1

6、0,12设是具有n个顶点的图，其邻接矩阵为A， 则 2，)中的项元素等于从顶点到顶点的长度等于k的途径的总数 138一定是8正则图的一个特征值 14图的点连通度可能等于图的边连通度 15点连通度的数值越小，图的连通性越脆弱 16可扩充路的长度必为奇数，且不属于的边比属于的边少1条 17任何简单平面图，均有,11,二、解答题 1.同构的判定及理由,12,3.左图称作什么图？两图是否同构？为什么？,13,2、给定图 ： (1)给出图 的一个生成树 。 (2)给出图 的顶点的最大度数 。 (3)给出图 的最长链。 (4)给出图 的一个边数最多的割集。,14,3.设G1，G2如图所示，求它们的交、并以

7、及环和。,15,4.写出下赋权图的一颗最小生成树,16,5求下图的最优生成树,17,6求下图的最优生成树,18,7设T是一棵树，它有两个2度顶点， 两个3度顶点，三个4度顶点，求T的树叶数,19,8设G是无向连通图，则G是一笔画的充分必要条件是什么？下列各图是否可以一笔画出？,20,9、甲乙两个邮递员去送信，两人以同样的速度走遍所有的街道，甲从A点出发，乙从B点出发，最后都回到邮局（C点）。如果要选择最短的线路，谁先回到邮局？,21,10请陈述无向图的完全关联矩阵M(G)的性质 11.写出图G的一个生成树以及基本圈组,22,23,13写出下图G的完全关联矩阵,24,14试写出下图的一个着色方案

8、，并回答该图的色数,15.请陈述定理Whitney定理并指出下图的 点连通度、边连通度与最小顶点的度数。,25,四、应用题 1. (蚂蚁比赛问题)甲、乙两只蚂蚁分别位于如下图中的顶点A，B处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的顶点出发，走过图中的所有边最后到达顶点C处。如果它们的速度相同，问谁先到达目的地？,26,2某地要兴建5个工厂，拟修筑道路连接这5处。经勘测其道路可依如下图无向边铺设。为使这5处都有道路相通，问至少要铺几条路？,27,3.某博物馆的一层布置如下图，其中边代表走廊，结点e是入口，结点g是礼品店，通过g我们可以离开博物馆。请找出从博物馆e进入，经过每个走廊恰好一次，最后从g处离开的路线,28,29,4六名间谍被擒，已知懂汉语、法语和日语，懂德语、俄语和日语，懂英语和法语，懂西班牙语，懂英语和德语，懂俄语和西班牙语，问至少用几个房间监禁他们，能使在一个房间里的人不能直接对话。,30,五、证明题 1证明任意六个人中有三个人互相认识，或有三个人互