第五章图习题2幻灯片资料.ppt

第五章图一、填空题⑴设无向图G中顶点数为n,则图G至少有()条边,至多有()条边;若G为有向图,则至少有()条边,至多有()条边。【解答】0,n(n-1)/2,0,n(n-1)【分析】图的顶点集合是有穷非空的,而边集可以是空集;边数达到最多的图称为完全图,在完全图中,任意两个顶点之间都存在边。⑵任何连通图的连通分量只有一个,即是()。【解答】其自身⑶图的存储结构主要有两种,分别是()和()。【解答】邻接矩阵,邻接表【分析】这是最常用的两种存储结构,此外,还有十字链表、邻接多重表、边集数组等。⑷已知一个有向图的邻接矩阵表示,计算第j个顶点的入度的方法是()。【解答】求第j列的所有元素1个数之和⑸有向图G用邻接矩阵A[n][n]存储,其第i行的所有元素之和等于顶点i的()。【解答】出度⑹如果一个有向图不存在(),则该图的全部顶点可以排列成一个拓扑序列。【解答】回路⑺在一个有向图中,若存在弧、、,则在其拓扑序列中,顶点vi,vj,vk的相对次序为()。【解答】vi,vj,vk【分析】对由顶点vi,vj,vk组成的图进行拓扑排序。⑸图的生成树( ),n个顶点的生成树有()条边。A唯一 B不唯一 C唯一性不能确定DnEn+1Fn-1【解答】C,F⑹设无向图G=(V,E)和G'=(V',E'),如果G'是G的生成树,则下面的说法中错误的是()。AG'为G的子图BG'为G的连通分量CG'为G的极小连通子图且V=V'DG'是G的一个无环子图【解答】B【分析】连通分量是无向图的极大连通子图,其中极大的含义是将依附于连通分量中顶点的所有边都加上,所以,连通分量中可能存在回路。⑺G是一个非连通无向图,共有28条边,则该图至少有()个顶点。A6B7C8D9【解答】D【分析】n个顶点的无向图中,边数e≤n(n-1)/2,将e=28代入,有n≥8,现已知无向图非连通,则n=9。⑻最小生成树指的是()。A由连通网所得到的边数最少的生成树B由连通网所得到的顶点数相对较少的生成树C连通网中所有生成树中权值之和为最小的生成树D连通网的极小连通子图【解答】C⑼某无向图的邻接矩阵A=,可以看出,该图共有()个顶点。A3B6C9D以上答案均不正确【解答】A⑽无向图的邻接矩阵是一个(),有向图的邻接矩阵是一个()A上三角矩阵B下三角矩阵C对称矩阵D无规律【解答】C,D⑾下列命题正确的是()。A一个图的邻接矩阵表示是唯一的,邻接表表示也唯一B一个图的邻接矩阵表示是唯一的,邻接表表示不唯一C一个图的邻接矩阵表示不唯一的,邻接表表示是唯一D一个图的邻接矩阵表示不唯一的,邻接表表示也不唯一【解答】B⑿在一个具有n个顶点的有向完全图中包含有()条边:An(n-1)/2Bn(n-(n+1)/2Dn2【解答】B三、判断题⑴一个有向图的邻接表和逆邻接表中的结点个数一定相等【解答】对。邻接表和逆邻接表的区别仅在于出边和入边,边表中的结点个数都等于有向图中结点的个数。⑵图G的生成树是该图的一个极小连通子图【解答】错。必须包含全部顶点。⑶无向图的邻接矩阵一定是对称的,有向图的邻接矩阵一定是不对称的【解答】错。有向图的邻接矩阵不一定对称,例如有向完全图的邻接矩阵就是对称的。⑷对任意一个图,从某顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点。【解答】错。只有连通图从某顶点出发进行一次遍历,可访问图的所有顶点。⑸在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧。【解答】错。只能说明从顶点a到顶点b有一条路径。⑹若一个有向图的邻接矩阵中对角线以下元素均为零,则该图的拓扑序列必定存在。【解答】对。四、已知一个连通图如图所示,试给出图的邻接矩阵和邻接表存储示意图,若从顶点v1出发对该图进行遍历,分别给出一个按深度优先遍历和广度优先遍历的顶点序列。【解答】邻接矩阵表示如下:深度优先遍历序列为:v1v2v3v5v4v6广度优先遍历序列为:v1v2v4v6v3v5邻接表表示如下:五、如图所示是一个无向带权图,请分别按Prim算法和Kruskal算法求最小生成树。【解答】按Prim算法求最小生成树的过程如下:按Kruskal算法求最小生成树的过程如下:六、对于如图所示的带权有向图,求从源点v1到其他各顶点的最短路径。【解答】从源点v1到其他各顶点的最短路径如下表所示。源点终点最短路径最短路径长度v1v7v1→v77v1v5v1→v511v1v4v1→v7→v413v1v6v1→v7→v4→v616v1v2v1→v7→v222v1v3v1→v7→v4→v6→v325