基本概念题: 8-1已知图G=(V,E),其中V={a,b,c,d,e,f,g},E={<a,b>,<a,g>,<b,g>,<c,b>, <d,c>,<d,f>,<e,d>,<f,a>,<f,e>,<g,c>,<g,d>,<g,f》},请画出图G,并画出图G 的邻接矩阵和图G的邻接表。 8-2对于图8-17所示的有向图,要求给出: (1)该有向图的邻接矩阵存储结构 (2)该有向图的邻接表存储结构 (3)设顶点A为访问的第一个顶点,按照邻接矩阵存储结构给出的每个顶点的邻接顶 点次序,给出该有向图的深度优先遍历的顶点访问序列 (4)设顶点A为访问的第一个顶点,按照邻接矩阵存储结构给出的每个顶点的邻接顶 点次序,给出该有向图的广度优先遍历的顶点访问序列 图8-17有向图 8-3对于图8-18所示的无向带权图,要求 (1)根据普里姆算法思想,画出构造该无向带权图最小生成树的过程 (2)根据克鲁斯卡尔算法思想,画出构造该无向带权图最小生成树的过程 图8-18无向带权图 8-4对于图8-19所示的有向带权图,根据狄克斯特拉算法思想,画出生成从顶点A到 其余各顶点最短路径的过程 8-19有向带权图 复杂概念题 8-5证明:无向完全图中一定有n(n-1)/2条边。 8-6证明:有向完全图中一定有n(n-1)条弧。 *8-7证明:在一个有n个顶点的完全图中生成树的数目可以有2n-1-1个。 *8-8证明:对于一个无向图G=(V,E),若G中各顶点的度均大于或等于2,则G中必 存在回路1 b c d e a f g 3 G C E F A B D 2 8 4 9 6 4 1 9 7 5 8 1 v2 v3 v6 v1 v5 v4 基本概念题： 8-1 已知图 G=(V,E)，其中 V={a,b,c,d,e,f,g}，E={<a,b>，<a,g>，<b,g>，<c,b>， <d,c>，<d,f>，<e,d>，<f,a>，<f,e>，<g,c>，<g,d>，<g,f>}，请画出图 G，并画出图 G 的邻接矩阵和图 G 的邻接表。 8-2 对于图 8-17 所示的有向图，要求给出： （1）该有向图的邻接矩阵存储结构； （2）该有向图的邻接表存储结构； （3）设顶点 A 为访问的第一个顶点，按照邻接矩阵存储结构给出的每个顶点的邻接顶 点次序，给出该有向图的深度优先遍历的顶点访问序列。 （4）设顶点 A 为访问的第一个顶点，按照邻接矩阵存储结构给出的每个顶点的邻接顶 点次序，给出该有向图的广度优先遍历的顶点访问序列。 图 8-17 有向图 8-3 对于图 8-18 所示的无向带权图，要求： （1）根据普里姆算法思想，画出构造该无向带权图最小生成树的过程； （2）根据克鲁斯卡尔算法思想，画出构造该无向带权图最小生成树的过程。 图 8-18 无向带权图 8-4 对于图 8-19 所示的有向带权图，根据狄克斯特拉算法思想，画出生成从顶点 A 到 其余各顶点最短路径的过程。 8-19 有向带权图 复杂概念题： 8-5 证明：无向完全图中一定有 n(n - 1) / 2 条边。 8-6 证明：有向完全图中一定有 n(n - 1)条弧。 *8-7 证明：在一个有 n 个顶点的完全图中生成树的数目可以有 2 n - 1 – 1 个。 *8-8 证明：对于一个无向图 G = (V, E)，若 G 中各顶点的度均大于或等于 2，则 G 中必 存在回路。 10 12 4 25 3 16 12 7 10 8 2