对于有n个顶点e条边的无向图,邻接矩阵表示时有( )个0元素。请给出计算过程
时间: 2023-03-28 19:01:24 浏览: 230
代码 无向图关联矩阵和邻接矩阵的相互转换算法代码
对于一个无向图,邻接矩阵是一个n*n的矩阵,其中第i行第j列的元素表示顶点i和顶点j之间是否有边相连,如果有则为1,否则为。由于是无向图,邻接矩阵是对称矩阵,即第i行第j列的元素等于第j行第i列的元素。
那么,对于一个无向图,邻接矩阵中的元素表示两个顶点之间没有边相连。因此,我们只需要计算邻接矩阵中元素的个数即可。
由于邻接矩阵是对称矩阵,因此只需要计算矩阵的上三角或下三角即可。假设我们计算的是上三角,那么矩阵中的元素个数为:
的个数 = (n*n - n) / 2 - e
其中,n*n是矩阵中元素的总数,n是矩阵的行数(或列数),n*n-n是矩阵中上三角(或下三角)元素的总数,e是图中边的数量。因此,邻接矩阵中元素的个数为:
的个数 = (n*n - n) / 2 - e
注意,这个公式只适用于无向图。如果是有向图,则需要计算矩阵中所有的元素个数。
阅读全文