算法与数据结构 | 您所在的位置:网站首页 › 结点度数之和等于边数两倍 › 算法与数据结构 |
自用。 1.以下关于图的叙述中,正确的是(CF. )。 A.强连通有向图的任何顶点到其他所有顶点都有弧。 B.图的任意顶点的入度等于出度。 C.有向完全图一定是强连通有向图。 D.有向图的边集的子集和顶点集的子集可构成原有向图的子图。 E.图与树的区别在于图的边数大于等于顶点数 F.无向图的连通分量是指无向图中的极大连通子图。 解答:CF. A.强连通有向图的任何顶点到其他所有顶点都有路径(概念和定义!) B. 在有向图中,所有顶点的入度之和是所有顶点出度之和的1倍。 由于每条弧必然连接两个顶点,也对应一个入度和一个出度,所以所有顶点的入度之和等于所有顶点的出度之和。 E.图与树的区别是逻辑上的区别,而不是边数的区别 2.在一个图中,所有顶点的度数之和等于图的边数的(C)倍 A. 1/2 B. 1 C. 2 D. 4 解析: 任意一条边都对应2个度,所以度数总和是边数总和的两倍。 3.【习题】关于无向连通图特性的描述中,正确的是( A ) I.所有顶点的度之和为偶数 II.边数大于顶点个数减1 III.至少有一个顶点的度为1 A.只有I B.只有II C.I和II D.I和III 解析:A. 结论.在一个图中,所有顶点的度数之和等于图的边数的2倍。(任意一条边都对应2个度,所以度数总和是边数总和的两倍。);无向连通图对应的生成树也是无向连通图,但边数等于顶点数减1,II错误;一个无向连通图的顶点恰好构成一个回路的情况,每个顶点的度都是2,III错; 4.已知无向图G含有16条边,其中度为4的顶点个数为3,度为3的顶点个数为4,其他顶点的度均小于3。图G所含的顶点个数至少是( B )。 A.10 B. 11 C. 13 D. 15 解析: 无向图度之和为边数的两倍;4*3+3*4+2x=16*2 推导出x=4,所以3+4+4=11 5~7为关于连通的问题 5.【习题】具有6个顶点的无向图,当有( B )条边时能确保是一个连通图。 A.10 B. 11 C. 13 D. 15 牵扯到完全图的一些应用。 问的是至少而不是最少,最少的话是5条 5个顶点构成的完全无向图,需要5*(5-1)/2=10条边,再加上1条边后,能保证第6个顶点必然与此完全无向图构成一个连通图,所以10+1=11 6.若无向图G=(V,E)中含有7个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是(C ). A.6 B.15 C.16 D. 21 解析: C。题干要求在“任何情况"下都是连通的,考虑最极端的情形,即图G的6个顶点构成一个完全无向图,再加上-条边后,第7个顶点必然与此完全无向图构成一个连通图,所以最少边数=6x5/2+1= 16.若边数n小于等于15,可以使这n条边仅连接图G中的某6个顶点,从而导致第7个顶点无法与这6个顶点构成连通图(不满足“任何情况")。 6.【习题】图G是一个非连通无向图,共有28条边,该图至少有( A )个顶点 A.9 B. 10 C. 11 D.12 解析:图G是一个非连通无向图,在边数固定时,顶点数最少的情况是该图由两个连通子图构成,且其中之一只含一个顶点,另一个为完全图,只含一个顶点的没有边,完全图的边数为n(n-1)/2=28,n=8,所以8+1=9 7.【习题】有n个顶点的图:若是连通无向图,其边的个数至少为( A );若是强连通有向图其边的个数至少为( )。 A. n-1,n B. n-1,n(n-1) C. n,n D. n,n(n-1) 解析: 极小连通子图n-1,强连通有向图就是一个有向环 8.【习题】若具有n个顶点的图是一个环,则它有( B )棵生成树。 A.n2 B.n C.n-1 D.1 解析: n个顶点的生成树是具有n-1条边的极小连通子图,n个顶点构成的环共有n条边,去掉任意一条边就是一棵生成树,所以共有n中情况 9.【习题】以下关于图的存储结构的描述中,正确的是( B ) A.一个图的邻接矩阵表示唯一,邻接表表示唯一。 B.一个图的邻接矩阵表示唯一,邻接表表示不唯一。 C.一个图的邻接矩阵表示不唯一,邻接表表示唯一。 D.一个图的邻接矩阵表示不唯一,邻接表表示不唯一。 10.若邻接表中有奇数个边表结点,则( D )。 A.图中有奇数个结点 B.图中有偶数个结点 C.图为无向图 D.图为有向图 解析: 对于无向图来说,这个点链接的边表节点就是度数,而无向图的度一定是一个偶数,所以无向图的邻接表一定是偶数;对于有向图来说,邻接表的个数就是这个出度,出度的和可以是奇数。 补充:有向图中,任意一条边AB(A->B)都会给A提供一个出度,给B提供一个入度,所以 顶点的度之和 = 2 * 顶点入度之和 = 2*顶点出度之和 = 顶点入度之和+顶点出度之和=边数的两倍。 11.n个顶点的无向图邻接表最多有( B )个边表结点。 A.n2 B.n(n-1) C.n(n+1) D.n(n-1)/2 解析: 由上题我们可以知道,无向图的边表节点就是它的度数,边表节点的和就是这个图的度数,那么度数又等于边数的两倍,所以最多就是在完全图的情况下啦 12.编程相关: 【习题】已知无向连通图G由顶点集V和边集E组成。|E|>0,当G中度为奇数的顶点个数为不大于2的偶数时,G存在包含所有边且长度为|E|的路径(称为EL路径)。设图采用邻接矩阵存储,类型定义如下: Typedef struct{ int numVertices,numEdges; //顶点数和边数 char VerticesList[MAXV]; //顶点表 int Edge[MAXV][MAXV]; //邻接矩阵 }Mgraph;请设计算法int IsExistEL(Mgraph G),判断G是否存在EL路径,若存在,则返回1,否则返回0。要求: 1)给出算法的基本设计思想。 2)根据设计思想,采用C语言描述算法,关键之处给出注释。 3)说明你所设计算法的时间复杂度和空间复杂度。 答: 刚开始看了几遍题没有看懂想要表达什么意思,关于|EL|图的定义(感觉有种高考时候做的那种题的感觉了)。 1)对于采用邻接矩阵的无向图,在邻接矩阵的每一行(列)中,非零元素的个数为本行(列)对应顶点的度。依次计算连通图G中各顶点的度,并记录为奇数的顶点个数,若个数为0或2,则返回1,否则返回0。 2)根据上述思想,设计算法。 int IsExistEL(Mygraph G){ int degree,i,j,count=0; for(i=0;j |
CopyRight 2018-2019 实验室设备网 版权所有 |