第8章图 (2)邻接表 (出边表 5∧ 3D (入边表) ABCDEF -3B (3)邻接多重表(十字链表) data fin fout j ilink jlink 0A∧ 0 03∧∧ 4121(((((B.C) 2|5A 31 54A∧cE 7-4用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边的条数是否相关? 【解答】 用邻接矩阵表示图,矩阵元素的个数是顶点个数的平方,与边的条数无关。矩阵中非零元素的个数 与边的条数有关。 7-5有n个顶点的无向连通图至少有多少条边?有n个顶点的有向强连通图至少有多少条边?试举例说 【解答】 个顶点的无向连通图至少有n1条边,n个顶点的有向强连通图至少有n条边。例如: 无向图 有向图第 8 章 图 97 (2) 邻接表 (3) 邻接多重表（十字链表） 7-4 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？ 【解答】 用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数 与边的条数有关。 7-5 有 n 个顶点的无向连通图至少有多少条边？有 n 个顶点的有向强连通图至少有多少条边？试举例说 明。 【解答】 n 个顶点的无向连通图至少有 n-1 条边，n 个顶点的有向强连通图至少有 n 条边。例如： 0 A 1 B 2 C 3 D 4 E 5 F 1 0 A 1 B 2 C 3 D 4 E 5 F 3 2 4 5 1 4 4 0 3 1 0 1 3 5 2 ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ （出边表） （入边表） 0 A 1 B 2 C 3 D 4 E 5 F data fin fout i j ilink jlink 0 1 (A, B) 0 3 (A, D) 1 2 (B, C) 1 4 (B, E) 2 5 (C, F) 3 1 (D, B) 3 4 (D, E) 5 4 (F, E) ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧