图论期末复习题(16年).ppt
图论期末复习图论期末复习一、填空题一、填空题1.任意两个顶点都任意两个顶点都_的简单图称为完全图的简单图称为完全图2如果如果G=(V,E)中任何顶点都是连通的，则称图中任何顶点都是连通的，则称图G是是连通的；否则称连通的；否则称G为为3.如果无向图的顶点集如果无向图的顶点集V分成两个子集分成两个子集V1,V2,(即满即满足足V1V2=,V1V2=V),使得使得G中任意一边的中任意一边的两个端点分属于两个端点分属于V1和和V2,则称则称G为为-5.完全二部图完全二部图 中边的个数为中边的个数为_6.设是具有个设是具有个p顶点的一棵树，则的边数一定为顶点的一棵树，则的边数一定为_7在任何图中，度数为奇数的顶点个数必为在任何图中，度数为奇数的顶点个数必为_ 4图图G是二部是二部图图的充分必要条件是的充分必要条件是G是不含是不含-的非平凡的非平凡图图86阶完全图阶完全图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有唯一的圈，则的边数为有唯一的圈，则的边数为_;17G是是Euler图图G连通且每个点度数均为连通且每个点度数均为_18.e为为G的割边的割边 e不在不在G的任一的任一_中。中。19.无向连通图无向连通图G G是欧拉图的充分必要条件是是欧拉图的充分必要条件是G G不不含含顶点。顶点。20连连通通图图G具有欧拉路而无欧拉圈当且具有欧拉路而无欧拉圈当且仅仅当当G恰有恰有个奇数度个奇数度顶顶点点21.无向图的关联矩阵每一行元素之和等于对应无向图的关联矩阵每一行元素之和等于对应顶点的顶点的l2222一个具有一个具有6 6个顶点的连通图个顶点的连通图G G的秩为的秩为_l2323一个具有一个具有5 5个个顶顶点的点的连连通通图图G G的秩的秩_l24247 7阶完全图的边连通度是阶完全图的边连通度是_l2525(6,9)(6,9)图图G G的向量空的向量空间间的的维维数是数是_l2626(5,8)(5,8)图图G G的向量空间的维数是的向量空间的维数是_l27连连通通简单图简单图G的关的关联联矩矩阵阵的一个大子的一个大子阵阵是非奇异的充要是非奇异的充要条件条件为为与与这这个大子个大子阵阵的列相的列相应应的的边边，组组成成G的的_ l28.G的的_是使得是使得G不不连连通或成通或成为为平凡平凡图图所必所必须删须删除的除的顶顶点的最小个数点的最小个数l2929设设M M为为G G的一个匹配，则的一个匹配，则M M中的任意两条边都中的任意两条边都_（填是或（填是或不是）邻接的不是）邻接的l30设设M为为G的一个匹配，则的一个匹配，则M中的任意中的任意两条边都两条边都_（填是或不是）邻接的（填是或不是）邻接的l31设设M1和和M2是是图图G的两个不同匹配的两个不同匹配,由由M1 M2导导出的出的G的的边导边导出子出子图记图记作作H,则则H的任意的任意连连通分支是下列情况之一：通分支是下列情况之一：(1)边边在在M1和和M2中交中交错错出出现现的偶圈的偶圈;(2)边边在在M1和和M2中交中交错错出出现现的的l32二部二部图图G中若中若满满足足V1=V2，则则G必有完美匹配必有完美匹配l33(G)=2G是是l34.若最大匹配的若最大匹配的边边数数为为p(G)/2，则说则说明明该图该图_（填存在或（填存在或不存在）完美匹配不存在）完美匹配l35.在计算平面图面的次数之和时，每条边边计算了在计算平面图面的次数之和时，每条边边计算了_次次 l36一个一个图图是平面是平面图图当且当且仅仅当它既没有收当它既没有收缩缩到到K5的子的子图图，也，也没有收没有收缩缩到到的子的子图图l37如果一个平面如果一个平面图图有一个面的次数有一个面的次数为为4，则该图则该图_（填是或不是）极大平面（填是或不是）极大平面图图三、判断题三、判断题l1若途径中的所有点互不相同，则称此途径为一条若途径中的所有点互不相同，则称此途径为一条链链l2若途径中的所有边互不相同，则称此途径为一条若途径中的所有边互不相同，则称此途径为一条道路道路l3任何无圈的图均是二部图任何无圈的图均是二部图l4两图即使满足顶点数相等、边数相等和度数相同两图即使满足顶点数相等、边数相等和度数相同的顶点数相等这三个条件，也不一定同构的顶点数相等这三个条件，也不一定同构l5在树中至少存在两个度为在树中至少存在两个度为1的顶点（树叶）的顶点（树叶）l6G是含有是含有56个顶点的无圈图，且对个顶点的无圈图，且对G中任两个不相邻的顶点中任两个不相邻的顶点u,v，G+uv有唯一的圈，则有唯一的圈，则G的边数为的边数为55l7凡是由奇数点组成的连通图，一定可以一笔画成凡是由奇数点组成的连通图，一定可以一笔画成l8凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完l9.哈密哈密顿图顿图一定是欧拉一定是欧拉图图，而欧拉，而欧拉图图未必是哈密未必是哈密顿图顿图l10.具有5个顶点8条边的连通图有5个不同的基本圈组l11连通图G的关联矩阵M的一个大子阵是非奇异的充要条件是与这个大子阵的列相应的边组成G的一颗生成树.l12设设是具有是具有n个个顶顶点的点的图图，其，其邻邻接矩接矩阵为阵为A，则则2，)中的中的项项元素等于从元素等于从顶顶点到点到顶顶点的点的长长度等于度等于k的途径的的途径的总总数数l138一定是一定是8正则图的一个特征值正则图的一个特征值l14图图的点的点连连通度可能等于通度可能等于图图的的边连边连通度通度l15点连通度的数值越小，图的连通性越脆弱点连通度的数值越小，图的连通性越脆弱l16可扩充路的长度必为奇数，且不属于的边比属于的边可扩充路的长度必为奇数，且不属于的边比属于的边少少1条条l17任何简单平面图，均有任何简单平面图，均有l二、解答题二、解答题l1.同构的判定及理由3.左图称作什么图？两图是否同构？为什么？xyzabcxyzabc2、给定图、给定图：(1)给出图给出图的一个生成树的一个生成树。(2)给出图给出图的顶点的最大度数的顶点的最大度数。(3)给出图给出图的最长链。的最长链。(4)给出图给出图的一个边数最多的割集。的一个边数最多的割集。abcde fge1e2e3e4e5e6e7e8e93.设设G1，G2如图所示，求它们的交、并以及环和。如图所示，求它们的交、并以及环和。1234G113245G24.写出下赋权图的一颗最小生成树写出下赋权图的一颗最小生成树abcdegfaedcbgf37512191418168学学号号21l5 5求下图的最优生成树求下图的最优生成树ABCDEF91515121187666l6 6求下图的最优生成树求下图的最优生成树ABCDEF915151211876667设T是一棵树，它有两个2度顶点，两个3度顶点，三个4度顶点，求T的树叶数l8设设G是无向连通图，则是无向连通图，则G是一笔画的充分是一笔画的充分必要条件是什么？下列各图是否可以一笔画出必要条件是什么？下列各图是否可以一笔画出？9、甲乙两个邮递员去送信，两人以同样的速度走、甲乙两个邮递员去送信，两人以同样的速度走遍所有的街道，甲从遍所有的街道，甲从A点出发，乙从点出发，乙从B点出发，点出发，最后都回到邮局（最后都回到邮局（C点）。如果要选择最短的线点）。如果要选择最短的线路，谁先回到邮局？路，谁先回到邮局？DCEFB A10请陈请陈述无向述无向图图的完全关的完全关联联矩矩阵阵M(G)的性的性质质11.写出图写出图G的一个生成树以及基本圈组的一个生成树以及基本圈组bav2fdcev3v1412、写出下图所示无向图的关联矩阵，并根、写出下图所示无向图的关联矩阵，并根据大子阵找到一颗生成树据大子阵找到一颗生成树v2v3e2v4e5e4e3e1v113写出下图写出下图G的完全关联矩阵的完全关联矩阵v1v2v4e2v3e1e3e414试写出下图的一个着色方案，并回试写出下图的一个着色方案，并回答该图的色数答该图的色数v2v3v4v1v515.请陈述定理Whitney定理并指出下图的点连通度、边连通度与最小顶点的度数。l四、应用题四、应用题l1.(蚂蚁比赛问题蚂蚁比赛问题)甲、乙两只蚂蚁分别位于如下图中甲、乙两只蚂蚁分别位于如下图中的顶点的顶点A，B处，并设图中的边长度是相等的。甲、处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的顶点出发，走过图中的所乙进行比赛：从它们所在的顶点出发，走过图中的所有边最后到达顶点有边最后到达顶点C处。如果它们的速度相同，问谁处。如果它们的速度相同，问谁先到达目的地？先到达目的地？甲甲A乙乙BCl2某地要兴建5个工厂，拟修筑道路连接这5处。经勘测其道路可依如下图无向边铺设。为使这5处都有道路相通，问至少要铺几条路？3.某博物馆的一层布置如下图，其中边代表走廊，结点e是入口，结点g是礼品店，通过g我们可以离开博物馆。请找出从博物馆e进入，经过每个走廊恰好一次，最后从g处离开的路线hcafedbigjl4六名间谍被擒，已知懂汉语、法语和日语，懂德语、俄语和日语，懂英语和法语，懂西班牙语，懂英语和德语，懂俄语和西班牙语，问至少用几个房间监禁他们，能使在一个房间里的人不能直接对话。五、证明题五、证明题1证证明明任任意意六六个个人人中中有有三三个个人人互互相相认认识识，或或有有三三个个人互不人互不认识认识。2、证证明明在在8个个人人的的团团体体中中，总总有有两两个个人人在在此此团团体体中中恰好有相同个数的朋友恰好有相同个数的朋友3设设G=（V,E）是是有有限限平平面面图图，有有f个个面面，q条条边边，则所有面的次数之和等于边数的则所有面的次数之和等于边数的2倍，即倍，即=2|q|4证证明明：设设G是是极极大大平平面面图图，有有p(p3)个个顶顶点点，q条条边，则边，则q=3p6,f=2p-4
