非连通无向图

第六章的练习题一、选择题1．设无向图的顶点个数为n ，则该图最多有（ ）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0E ．n2 2．一个n 个顶点的连通无向图，其边的个数至少为（ ）。

A ．n-1B ．nC ．n+1D ．nlogn ； 3．要连通具有n 个顶点的有向图，至少需要（ ）条边。

A ．n-lB ．nC ．n+lD ．2n 4．n 个结点的完全有向图含有边的数目（ ）。

A ．n*nB ．n （n ＋１）C ．n ／2D ．n*（n －l ） 5．一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。

A ．0 B ．1 C ．n-1 D ．n6．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。

A ．1/2B ．2C ．1D ．47．一个图中包含K 个连通分量，若按深度优先搜索方法访问所有结点，则必须调用（ ）次深度优先搜索遍历算法。

A ．1B ．K-1C ．KD ．K+1 8．下列哪一种图的邻接矩阵是对称矩阵？（ ）A ．有向图B ．无向图C ．AOV 网D ．AOE 网9． 从邻接阵矩可以看出，该图共有（①）个顶点；如果是有向图该图共有（②） 条弧；如果是无向图，则共有（③）条边。

①．A ．9 B ．3 C ．6 D ．1 E ．以上答案均不正确 ②．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 ③．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 10．对某个无向图的邻接矩阵来讲，（ ）。

A ．第i 行上的非零元素个数和第i 列的非零元素的个数一定相等B ．矩阵中的非零元素个数等于图中的边数C ．第i 行上，第i 列上非零元素总数等于顶点vi 的度数D ．矩阵中非全零行的行数等于图中的顶点数11．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。

第七章：图练习题一、选择题1、一个有n个顶点的无向图最多有（）条边。

A、nB、n(n-1)C、n(n-1)/2D、2n2、具有6个顶点的无向图至少有（）条边才能保证是一个连通图。

A、5B、6C、7D、83、具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（）。

A、线性图B、无向完全图C、无向图D、简单图4、具有4个顶点的无向完全图有（）条边。

A、6B、12C、16D、205、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点A、6B、7C、8D、96、存储稀疏图的数据结构常用的是（）。

A、邻接矩阵B、三元组C、邻接表D、十字链表7、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。

A、nB、(n-1)2C、(n+1)2D、n28、设连通图G的顶点数为n，则G的生成树的边数为（）。

A、n-1B、nC、2nD、2n-19、n个顶点的无向图的邻接表中结点总数最多有（）个。

A、2nB、nC、n/2D、n(n-1)10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（），所有顶点邻接表的结点总数为（）。

A、nB、n+1C、n-1D、2nE、e/2F、eG、2eH、n+e11、在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（）。

A、顶点v的度B、顶点v的出度C、顶点v 的入度D、依附于顶点v的边数12、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（）和（）（1）A、abecdf B、acfebd C、acebfd D、acfdeb（2）A、abcedf B、abcefd C、abedfc D、acfdeb13、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（）和（）。

A、中序遍历B、先序遍历C、后序遍历D、层次遍历14、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（）和（）。

《 离散数学 》同步测试卷10:图的基本概念一．填空：1．一个无向图表示为G=<V , E>，其中V 是 结点 的集合，E 是 边 的集合， 并且要求E 中的任何一条边必须和G 中的两个结点 相关联 。

2．设无向图G 中有12条边，已知G 中度为3的结点有6个，其余的结点度均 小于3，则G 中至少有 9 个结点。

3．设G=(n,m)是简单图，v 是G 中一个度为k 的结点，e 是G 中的一条边，则G – v 中有1n -个结点，m k -条边；G – e 中有n 个结点，1m -条边。

4．设G 是个有向图，当且仅当G 中有一条经过每一个结点的路径时，G 才是 单向 连通图。

5．设图G=<V , E>，则：若E 中的每条边都是_无向边 _，则称图G 为无向图；若E 中的每条边都是_有向边__，则称图G 为有向图。

6．设图G 中 无自环 和 无平行边 ，则称图G 为简单图。

7．设G 是个无自环的无向图，其中有2个结点的度数为4，其余结点的度为2，有6条边。

则G 中共有_ 4 个结点。

因此，G 是个多重边_图。

8．一个无向图G 有16条边，若G 中每一个结点的度均为2，则G 有16个结点。

9．设G 是个具有5个结点的简单无向完全图，则G 有__10_条边。

10．设G 是个具有5个结点的简单有向完全图，则G 有_20_条边。

11．设G 是个n 阶简单有向图，G '是G 的子图，已知G '的边数()1E n n '=-，则G 的边数m 为()1n n -。

12．35条边，每个结点的度数至少是3的图最多有__23_个结点。

13、3个结点可构成 4 个不同构的简单无向图，可构成 16 个不同构的简单有向图。

14、设()100,100G =为无向连通图，则从G 中能找到 1 条回路15、5K 的点连通度为 4 ，边连通度为 4 。

16、设图G=<V , E>，{}1234,,,V v v v v =，若G 的邻接矩阵0101101111001000A ⎛⎫ ⎪ ⎪= ⎪ ⎪⎝⎭，则 ()1deg v -= 3 ，()4deg v += 1 ，，从2v 到4v 长度为2的通路有 1 条。

图1. 填空题⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

⑵任何连通图的连通分量只有一个，即是（）。

【解答】其自身⑶图的存储结构主要有两种，分别是（）和（）。

【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。

⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。

⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。

【解答】求第j列的所有元素之和⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。

【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

【解答】前序，栈，层序，队列⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。

【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。

⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。

【解答】回路⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。

【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。

习题7 图7.1 单项选择题1．在一个图中，所有顶点的度数之和等于所有边数的____倍。

A. 1/2B. 1C. 2D. 42．任何一个无向连通图的最小生成树。

A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。

A. 1/2B. 1C. 2D. 44．一个有n个顶点的无向图最多有____条边。

A. nB. n(n-1)C. n(n-1)/2D. 2n5．具有4个顶点的无向完全图有____条边。

A. 6B. 12C. 16D. 206．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。

A. 5B. 6C. 7D. 87．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。

A. nB. n+1C. n-1D. n/28．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。

A. nB. (n-1)2C. n-1D. n29．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。

①A. n B. n+1 C. n-1 D. n+e②A. e/2 B. e C.2e D. n+e10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。

①A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,bC. a,e,b,c,f,dD. a,c,f,d,e,b图 7.1 一个无向图11．已知一有向图的邻接表存储结构如图7.2所示。

⑴根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。

A. v1,v2,v3,v5,v4B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2D. v1,v4,v3,v5,v2⑵根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。