图论期末复习题(16年)

图论期末复习 一 填空题1 任意两个顶点都 的简单图称为完全图 2 如果G V E 中任何顶点都是连通的 则称图G是连通的 否则称G为 3 如果无向图的顶点集V分成两个子集V1 V2 即满足V1 V2 V1 V2 V 使得G中任意一边的两个端点分属于V1和V2 则称G为 5 完全二部图中边的个数为 6 设是具有个p顶点的一棵树 则的边数一定为 7 在任何图中 度数为奇数的顶点个数必为 4 图G是二部图的充分必要条件是G是不含 的非平凡图 8 6阶完全图G的边的个数是 9 边数最少的连通图是 10 G是有40个点的简单图且G中任两个点之间有且只有1条路 则G是 11 若G有32个点的连通图 且对G每条边e G e非连通 则G的边数为 12 若G有n个顶点的是k 正则图 则G的边数为 13 简单图G满足 则G是图 14 如果连通图G的所有顶点的度数均为 则称图G为欧拉图 15 若G是有31个点的连通图且G中每条边都是割边 则q G 16 G是含有56个顶点的无圈图 且对 中任两个不相邻的顶点u v uv有唯一的圈 则 的边数为 17 G是Euler图 G连通且每个点度数均为 18 e为G的割边 e不在G的任一 中 19 无向连通图G是欧拉图的充分必要条件是G不含 顶点 20 连通图G具有欧拉路而无欧拉圈当且仅当G恰有 个奇数度顶点 21 无向图的关联矩阵每一行元素之和等于对应顶点的 22 一个具有6个顶点的连通图G的秩为 23 一个具有5个顶点的连通图G的秩 24 7阶完全图的边连通度是 25 6 9 图G的向量空间的维数是 26 5 8 图G的向量空间的维数是 27 连通简单图G的关联矩阵的一个大子阵是非奇异的充要条件为与这个大子阵的列相应的边 组成G的 28 G的 是使得G不连通或成为平凡图所必须删除的顶点的最小个数 29 设M为G的一个匹配 则M中的任意两条边都 填是或不是 邻接的 30 设M为G的一个匹配 则M中的任意两条边都 填是或不是 邻接的 31 设M1和M2是图G的两个不同匹配 由M1 M2导出的G的边导出子图记作H 则H的任意连通分支是下列情况之一 1 边在M1和M2中交错出现的偶圈 2 边在M1和M2中交错出现的 32 二部图G中若满足V1 V2 则G必有完美匹配 33 G 2 G是 34 若最大匹配的边数为p G 2 则说明该图 填存在或不存在 完美匹配 35 在计算平面图面的次数之和时 每条边边计算了 次 36 一个图是平面图当且仅当它既没有收缩到K5的子图 也没有收缩到的子图 37 如果一个平面图有一个面的次数为4 则该图 填是或不是 极大平面图 三 判断题 1 若途径中的所有点互不相同 则称此途径为一条链 2 若途径中的所有边互不相同 则称此途径为一条道路 3 任何无圈的图均是二部图 4 两图即使满足顶点数相等 边数相等和度数相同的顶点数相等这三个条件 也不一定同构 5 在树中至少存在两个度为1的顶点 树叶 6 G是含有56个顶点的无圈图 且对G中任两个不相邻的顶点u v G uv有唯一的圈 则G的边数为55 7 凡是由奇数点组成的连通图 一定可以一笔画成 8 凡是只有两个奇点 其余均为偶点 的连通图 一定可以一笔画完 9 哈密顿图一定是欧拉图 而欧拉图未必是哈密顿图 10 具有5个顶点8条边的连通图有5个不同的基本圈组 11 连通图G的关联矩阵M的一个大子阵是非奇异的充要条件是与这个大子阵的列相应的边组成G的一颗生成树 12 设是具有n个顶点的图 其邻接矩阵为A 则2 中的项元素等于从顶点到顶点的长度等于k的途径的总数 13 8一定是8 正则图的一个特征值 14 图的点连通度可能等于图的边连通度 15 点连通度的数值越小 图的连通性越脆弱 16 可扩充路的长度必为奇数 且不属于的边比属于的边少1条 17 任何简单平面图 均有 二 解答题1 同构的判定及理由 3 左图称作什么图 两图是否同构 为什么 2 给定图 1 给出图的一个生成树 2 给出图的顶点的最大度数 3 给出图的最长链 4 给出图的一个边数最多的割集 3 设G1 G2如图所示 求它们的交 并以及环和 4 写出下赋权图的一颗最小生成树 5 求下图的最优生成树 6 求下图的最优生成树 7 设T是一棵树 它有两个2度顶点 两个3度顶点 三个4度顶点 求T的树叶数 8 设G是无向连通图 则G是一笔画的充分必要条件是什么 下列各图是否可以一笔画出 9 甲乙两个邮递员去送信 两人以同样的速度走遍所有的街道 甲从A点出发 乙从B点出发 最后都回到邮局 C点 如果要选择最短的线路 谁先回到邮局 10 请陈述无向图的完全关联矩阵M G 的性质 11 写出图G的一个生成树以及基本圈组 13 写出下图G的完全关联矩阵 14 试写出下图的一个着色方案 并回答该图的色数 15 请陈述定理Whitney定理并指出下图的点连通度 边连通度与最小顶点的度数 四 应用题1 蚂蚁比赛问题 甲 乙两只蚂蚁分别位于如下图中的顶点A B处 并设图中的边长度是相等的 甲 乙进行比赛 从它们所在的顶点出发 走过图中的所有边最后到达顶点C处 如果它们的速度相同 问谁先到达目的地 2 某地要兴建5个工厂 拟修筑道路连接这5处 经勘测其道路可依如下图无向边铺设 为使这5处都有道路相通 问至少要铺几条路 3 某博物馆的一层布置如下图 其中边代表走廊 结点e是入口 结点g是礼品店 通过g我们可以离开博物馆 请找出从博物馆e进入 经过每个走廊恰好一次 最后从g处离开的路线 4 六名间谍被擒 已知懂汉语 法语和日语 懂德语 俄语和日语 懂英语和法语 懂西班牙语 懂英语和德语 懂俄语和西班牙语 问至少用几个房间监禁他们 能使在一个房间里的人不能直接对话 五 证明题1 证明任意六个人中有三个人互相认识 或有三个人互不认