图论期末复习题(16年)

《图论期末复习题(16年)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论期末复习一、填空题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是不含

2、-----的非平凡图．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个顶点的无圈图，且对

3、Ｇ中任两个不相邻的顶点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)图

4、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的边导出子图

5、记作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，则该图______（填是或不是）极大平面图．三、

6、判断题1．若途径中的所有点互不相同，则称此途径为一条链．2．若途径中的所有边互不相同，则称此途径为一条道路．3．任何无圈的图均是二部图．4．两图即使满足顶点数相等、边数相等和度数相同的顶点数相等这三个条件，也不一定同构．5．在树中至少存在两个度为1的顶点（树叶）．6．G是含有56个顶点的无圈图，且对G中任两个不相邻的顶点u,v，G+uv有唯一的圈，则G的边数为55．7．凡是由奇数点组成的连通图，一定可以一笔画成．8．凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完．9.哈密顿图一定是欧

7、拉图，而欧拉图未必是哈密顿图．10.具有5个顶点8条边的连通图有5个不同的基本圈组．11．连通图G的关联矩阵M的一个大子阵是非奇异的充要条件是与这个大子阵的列相应的边组成G的一颗生成树.12．设是具有n个顶点的图，其邻接矩阵为A，则2，…)中的项元素等于从顶点到顶点的长度等于k的途径的总数．13．8一定是8—正则图的一个特征值．14．图的点连通度可能等于图的边连通度．15．点连通度的数值越小，图的连通性越脆弱．16．可扩充路的长度必为奇数，且不属于的边比属于的边少1条．17．任何简单平面图，均有

8、．二、解答题1.同构的判定及理由3.左图称作什么图？两图是否同构？为什么？xyzabcxyzabc2、给定图：(1)给出图的一个生成树。(2)给出图的顶点的最大度数。(3)给出图的最长链。(4)给出图的一个边数最多的割集。abcdefge1e2e3e4e5e6e7e8e93.设G1，G2如图所示，求它们的交、并以及环和。1234G113245G24.写出下赋权图的一颗最小生成树abcdegfaedcbgf37512191418168学号215．求下图的最优生成树．ABCDEF9151512118