图论期末复习题{16年}.ppt

5.完全二部图 中边的个数为_________． 6.设是具有个p顶点的一棵树，则的边数一定为___． 7．在任何图中，度数为奇数的顶点个数必为______． 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.左图称作什么图？两图是否同构？为什么？ 5．求下图的最优生成树． 6．求下图的最优生成树． 8．设G是无向连通图，则G是一笔画的充分必要条件是什么？下列各图是否可以一笔画出？ 9、甲乙两个邮递员去送信，两人以同样的速度走遍所有的街道，甲从A点出发，乙从B点出发，最后都回到邮局（C点）。如果要选择最短的线路，谁先回到邮局？ 13．写出下图G的完全关联矩阵． 14．试写出下图的一个着色方案，并回答该图的色数． 四、应用题 1. (