对于一个具有5个顶点的无向图,使用邻接矩阵表示时,如果邻接矩阵的对角线元素均为0,且矩阵中值为1的元素总数为8个,那么该图中边的数量是多少?
答案解析
核心考点说明: 无向图的邻接矩阵特性。无向图的邻接矩阵是对称的,且对于不含自环的图,对角线元素均为0。题目考察邻接矩阵中非零元素与图中边数量的关系。解题思路分析:邻接矩阵中,如果(i, j)位置的值为1,则表示顶点i和顶点j之间存在一条边。对于无向图,边(i, j)和边(j, i)被视为同一条边,所以在邻接矩阵中,体现为对称位置的两个1。已知矩阵中值为1的元素总数为8个,且矩阵是对称的,因此实际的边数为8 / 2 = 4。每个选项的详细分析:A:4,正确答案。8个1代表8个有向边,但无向图中一条边对应两个1,所以实际边数是4。B:8,误选。没有考虑无向图的对称性,直接将1的个数作为边数。C:16,误选,将矩阵总的元素个数除以2。D:20,误选,计算的是没有关系的量,不相关。易错点提醒:务必注意无向图的邻接矩阵是对称的,一条边对应两个1,计算边数需要除以2。
正确答案:A