给定一个nxn邻接矩阵,如何计算图中三角形的数量(Matlab)？

Question

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

Answer 1

邻接矩阵A的第n次幂中的(i,j)元素对从i开始到j结束的长度为n的路径的数量进行计数.

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

对于图中的三个节点中的每一个,每个不同的三角形将被计数两次(每个方向一次,顺时针和逆时针).

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