图有十个顶点,则对应邻接矩阵真有多少个元素?

Question

如题所述

Answer 1

一个图的邻接矩阵是一个方阵，它的行数和列数等于图中顶点的数量。如果一个图有$n$个顶点，则其邻接矩阵就是一个$n\times n$的方阵。

根据方阵的定义，一个$n\times n$的方阵共有$n^2$个元素。因此，如果一个图有10个顶点，则其邻接矩阵真正含有$10^2=100$个元素。其中，每个元素对应了图中的一条边，如果该元素值为1表示边存在，否则表示边不存在。需要注意的是，一个无向图的邻接矩阵是对称的，因此只需要存储矩阵上（或下）三角形的元素即可，因此真正需要存储的邻接矩阵元素个数为$(n^2+n)/2=55$个。而对于有向图，邻接矩阵不一定对称，需要存储对角线以上和对角线以下的所有$n^2$个元素。