Question

含有n个顶点和e条弧的有向图的邻接矩阵中零元素的个数为？

Answer 1

对于一个含有n个顶点和e条弧的有向图，其邻接矩阵是一个n×n的矩阵。每个元素表示两个顶点之间的边或弧的存在与否。如果边或弧存在，则对应位置的元素为1；如果边或弧不存在，则对应位置的元素为0。
在邻接矩阵中，存在e条弧，即存在e个非零元素。因为邻接矩阵是一个n×n的矩阵，总共有n×n个元素。因此，零元素的个数为n×n - e。
简而言之，含有n个顶点和e条弧的有向图的邻接矩阵中零元素的个数为n×n - e。

Answer 2

无向的邻接矩阵一定是对称阵。当vi与vj中间有一条边相连接时，则a(ij)=1,否则为0.e条边对应了n个顶点的度的和为2e.所以零元素的个数为n^2-2e