含有N个顶点和e条弧的有向图的邻接矩阵中零元素的个数为
时间: 2024-05-31 15:14:55 浏览: 156
有向图的邻接矩阵.。。
5星 · 资源好评率100%
对于一个含有 $N$ 个顶点和 $e$ 条弧的有向图,其邻接矩阵是一个 $N \times N$ 的矩阵。由于是有向图,邻接矩阵中的元素值只能是 0 或 1,表示从一个顶点到另一个顶点是否存在一条边。
由于每个顶点最多能与其他 $N-1$ 个顶点相连,因此邻接矩阵中最多会有 $N\times(N-1)$ 个非零元素。而根据有向图的定义,如果一个顶点没有到其他顶点的弧,则其对应的行和列都为 0,因此邻接矩阵中最少会有 $N^2-e$ 个零元素。
因此,邻接矩阵中零元素的个数为 $N^2-e-N\times(N-1)$。
阅读全文