numbers - 计算图中的三角形

Question

我的教授说我应该找到一种方法来找出图中三角形的数量。我有一个问题应该使用什么图表，但我的教授建议我必须首先找到一种方法来计算图表中的三角形。我通过谷歌搜索它，发现有一种算法可以计算图中的三角形，但我不太了解它，因为我不是 ComSci（计算机科学）学生。而且我还发现我可以通过矩阵来计算三角形的数量。(1/6)(A)^3。这是 A 的踪迹。所以...我现在要问的是另一种在图中查找三角形数量的想法。如果我得到答案，谢谢！

Answer 1

一个简单的方法是访问每个节点并尝试从它开始的每条长度为 3 的路径。如果它在起始节点处结束，它将是一个三角形。

考虑到时间消耗，这不是最优的，但它很简单。