图习题及参考

1、第7章习题一、单项选择题1.在无向图中定义极点的度为与它有关系的（）的数量。A.极点B.边C.权D.权值2.在无向图中定义极点vi与vj之间的路径为从vi抵达vj的一个（）。A.极点序列B.边序列C.权值总和D.边的条数3.图的简单路径是指（）不重复的路径。A.权值B.极点C.边D.边与极点均4.设无向图的极点个数为n，则该图最多有（）条边。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)5.n个极点的连通图起码有（）条边。A.n-1B.nC.n+1D.06.在一个无向图中，全部极点的度数之和等于全部边数的()倍。A.3B.2C.1D.1/27.若采纳毗邻矩阵法储存一个n个极

2、点的无向图，则该毗邻矩阵是一个()。A.上三角矩阵B.稀少矩阵C.对角矩阵D.对称矩阵8.图的深度优先搜寻近似于树的（）序次遍历。A.先根B.中根C.后根D.层次9.图的广度优先搜寻近似于树的（）序次遍历。A.先根B.中根C.后根D.层次10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不可以在图中构成（）。A.重边B.有向环C.回路D.权值重复的边11.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值一定是（）。A.非零B.非整C.非负D.非正12.设G1=(V1,E1)和G2=(V2,E2)为两个图，假如V1V2，

3、E1E2，则称（）。A.G1是G2的子图B.G2是G1的子图C.G是G的连通重量D.G是G的连通重量122113.有向图的一个极点的度为该极点的（）。A.入度B.出度C.入度与出度之和D.(入度出度)214.一个连通图的生成树是包括图中全部极点的一个（）子图。A.极小B.连通C.极小连通D.无环15.n(n1)个极点的强连通图中起码含有（）条有向边。A.n-1B.nn(n-1)/2D.n(n-1)16.在一个带权连通图G中，权值最小的边必定包括在G的（）生成树中。A.某个最小B.任何最小C.广度优先D.深度优先17.关于拥有e条边的无向图，它的毗邻表中有（）个结点。A.e-1B.eC.2(e-

4、1)D.2e18.关于以下图的带权有向图，从极点1到极点5的最短路径为（）。,4,5B.1,2,3,5C.1,4,3,5D.1,2,4,3,516492315283519.一个有n个极点和n条边的无向图必定是（）。A.连通的B.不连通的C.无环的D.有环的20.关于有向图，其毗邻矩阵表示比毗邻表表示更易于（）。A.求一个极点的度B.求一个极点的毗邻点C.进行图的深度优先遍历D.进行图的广度优先遍历21.与毗邻矩阵对比，毗邻表更合适于储存（）图。A.无向B.连通C.稀少D.浓密图22.为了实现图的广度优先遍历，BFS算法使用的一个协助数据结构是（）。A.栈B.行列C.二叉树D.树二、填空题1.用

5、毗邻矩阵储存图，占用储存空间数与图中极点个数_关，与边数_关。n(n0)个极点的无向图最多有_条边，最罕有_条边。3.n(n0)个极点的连通无向图最罕有_条边。010，则图G必定是_向图。4.若3个极点的图G的毗邻矩阵为1000105.n(n0)个极点的无向图中极点的度的最大值为_。(n0)个极点的连通无向图的生成树起码有_条边。7.在使用Kruskal算法结构连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个上，才有可能加入到生成树中。_求解带权连通图最小生成树的Prim算法合适于_图的情况，而Kruskal算法合适于_图的情况。三、判断题1.一个图的子图能够是空图，极点个数为0。

6、储存图的毗邻矩阵中，矩阵元素个数不只与图的极点个数有关，并且与图的边数也有关。对一个连通图进行一次深度优先搜寻（depthfirstsearch）能够遍访图中的全部极点。4.有n(n1)个极点的无向连通图最罕有n-1条边。假如无向图中各个极点的度都大于2，则该图中必有回路。假如有向图中各个极点的度都大于2，则该图中必有回路。图的广度优先搜寻（breadthfirstsearch）算法不是递归算法。8.有n个极点、e条边的带权有向图的最小生成树一般由n个极点和n-1条边构成。9.关于一个边上权值随意的带权有向图，使用Dijkstra算法能够求一个极点到其余各个极点的最短路径。有回路的有向图不可以

7、达成拓扑排序。对任何用极点表示活动的网络（AOV网）进行拓扑排序的结果都是独一的。用边表示活动的网络（AOE网）的重点路径是指从源点到终点的路径长度最长的路径。关于AOE网络，加快任一重点活动就能使整个工程提早达成。关于AOE网络，任一重点活动延缓将致使整个工程延缓达成。在AOE网络中，可能同时存在几条重点路径，称全部重点路径都需经过的有向边为桥。假如加快这样的桥上的重点活动就能使整个工程提早达成。用毗邻矩阵储存一个图时，在不考虑压缩储存的状况下，所占用的储存空间大小只与图中的极点个数有关，而与图的边数没关。毗邻表只好用于有向图的储存，毗邻矩阵关于有向图和无向图的储存都合用。毗邻矩阵只合用于浓

8、密图（边数靠近于极点数的平方），毗邻表合用于稀少图（边数远小于极点数的平方）储存无向图的毗邻矩阵是对称的，所以只需储存毗邻矩阵的下（上）三角部分就能够了。连通重量是无向图中的极小连通子图。在AOE网络中必定只有一条重点路径。四、运算题1.设连通图G以下图。试画出该图对应的毗邻矩阵表示，并给出对它履行从极点V开始的广度优先搜0索的结果。V0V2V1V5V4V3V7V8V62.设连通图G以下图。试画出该图及其对应的毗邻表表示，并给出对它履行从V开始的深度优先搜寻0的结果。V0V2V1V5V4V3V7V8V6关于以下图的有向图，试写出：从极点出发进行深度优先搜寻所获得的深度优先生成树；从极点出发进行

9、广度优先搜寻所获得的广度优先生成树4.设有向图G以下图。试画出从极点V开始进行深度优先搜寻和广度优先搜寻获得的DFS生成丛林和0BFS生成丛林。V0V3V12VV4V56V7V设有一个连通网络以下图。试按以下格式，应用Kruskal算法给出在结构最小生成树过程中次序选出的各条边。6061182735342645(始极点号，终极点号，权值)(,)(,)(,)(,)(,)设有一个连通网络以下图。试采纳prim算法从极点0开始结构最小生成树。（写出加入生成树极点会合S和选择边Edge的次序）901172567114853S:极点号Edge:(极点，极点，权值)0(，)0(，)0(，)0(，)0(，)

10、0有八项活动,每项活动要求的前驱以下:活动A0A1A2A3A4A5A6A7前驱无前驱A0A0A0,A2A1A2,A4A3A5,A6试画出相应的AOV网络,并给出一个拓扑排序序列。(2)试改变某些结点的编号,使得用毗邻矩阵表示该网络时全部对角线以下的元素全为0。试对下列图所示的AOE网络这个工程最早可能在什么时间结束。确立哪些活动是重点活动。画出由全部重点活动构成的图，指出哪些活动加快可使整个工程提早达成。210426141961511553设带权有向图以下图。试采纳Dijkstra算法求从极点0到其余各极点的最短路径和最短路径长度。8014147292534第7章习题参照答案一、单项选择题参照

11、答案：1.B5.A6.B7.D11.C15.B16.A18.D21.C22.B二、填空题参照答案：1.有,无2.n(n-1)/2,03.n-14.有5.(n-1)6.n-17.连通重量8.浓密，稀少三、判断题参照答案：1.否2.否3.是4.是5.是6.否7.是8.否9.否10.是11.否12.是13.否14.是15.是16.是17.否18.是19.是20.否21.否四、运算题参照答案：1.图G对应的毗邻矩阵为011100000100110000100101000111000110G.Edge010000000001000000000100011000100100000000100履行广度优先搜

12、寻的结果为V0V1V3V2V4V7V6V5V8，搜寻结果不独一。图G对应的毗邻表为：0V01321V10312V20353V3012674V415V526V63787V7368V86履行深度优先搜寻的结果为：V0V1V4V3V6V7V8V2V5，搜寻结果不独一。以极点为根的深度优先生成树（不独一）：以极点为根的广度优先生成树：4.深度优先生成丛林为：V0广度优先生成丛林为：V0V3VV2311V2VV4VV4V5V7V5VV667V应用Kruskal算法次序选出最小生成树的各条边为：(始极点号，终极点号，权值)0(0,3,1)112(2,5,2)(1,4,3)35342(3,5,4)(3,4,

13、5)45采纳prim算法从极点0开始结构最小生成树的过程：S:极点号Edge:(极点，极点，权值)0(0，1，9)0,1(1，3，5)0,1,3(1，2，7)0,1,3,2(2，4，6)0,1,3,2,4(2，5，7)0,1,3,2,4,509172567345相应的AOV网络为：A1A2A0A3A4A7A5A6一个拓扑排序序列为：A0,A1,A4,A2,A5,A3,A6,A7。注意：拓扑排序结果不独一。按拓扑有序的序次对全部极点重新编号：原编号A0A1A4A2A5A3A6A7新编号A0A1A2A3A4A5A6A7相应毗邻矩阵为：01234567010101000001000001000010

14、002Edge0000110030000000140000001050000000160000000077.针对下列图所示的AOE网络210246141961511553各极点（事件）的最早可能开始时间Ve(i)和最迟同意开始时间Vl(i)参看下表：极点123456Ve01915293843Vl01915373843各边（活动）的最早可能开始时间Ee(k)和最迟同意开始时间El(k)参看下表：边Ee00151915192938El170151927273738假如活动k的最早可能开始时间Ee(k)与最迟同意开始时间El(k)相等，则该活动是重点活动。此题的重点活动为,，它们构成重点路径。这些重点活动中任一个提早达成，整个工程就能提早达成。整个工程最早在43天达成。由重点活动构成的102211941511358.带权有向图以下图：8014147292354AOV网络以下图。4665应用Dijkstra算法求从极点V到其余各极点的最短路径Path和最短路径长度Len的步骤以下：0步骤V0V1V2V