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

9

我写了一个函数,给定n,生成随机的nxn邻接矩阵。我想知道有没有一种方法来计算由该矩阵表示的图中三角形的数量。

1个回答

18

在邻接矩阵 A 的第 n 次幂中,元素 (i, j) 表示从节点 i 开始,到节点 j 结束的长度为 n 的路径数量。

三角形是一条以同一节点为起点和终点的长度为3的路径。因此,邻接矩阵 A 的第3次幂中的第 i 个对角线元素表示包含节点 i 的三角形总数。

每个不同的三角形在图中的三个节点中会被计算两次(顺时针方向和逆时针方向各一次)。

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


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接