matlab - 给定一个 nxn 邻接矩阵，如何计算图中三角形的数量（Matlab）？

Question

我写了一个函数，给定 n，生成随机 nxn 邻接矩阵。我想知道是否有办法计算矩阵表示的图中三角形的数量。

Answer 1

邻接矩阵A的n次方中的 ( i , j ) 元素计算从i开始到j结束的长度为n的路径的数量。

三角形是在同一节点开始和结束的长度为 3 的路径。因此， A的 3 次方的第i个对角元素计算包含i作为节点之一的三角形的数量。

对于图中的三个节点中的每一个，每个不同的三角形将被计算两次（每个方向一次，顺时针和逆时针）。

因此，不同三角形的数量是trace(A^3) / 6。