graph-algorithm - 无向图中 3-cliques(三角形)的最大可能数量的公式

Question

正如问题所述。我似乎无法找出与纸笔结果相对应的公式。我正在寻找一个公式来给出无向图中三角形的最大可能数量。

三角形被定义为路径长度为 3 的节点的任何连接，形成一个循环。例如，如果我有一个图，其中 1<->2<->3<->1 是一个三角形(<-> 是一个无向连接)。如果不清楚三角形是什么，第 2 页的顶部有一张图显示了在此上下文中三角形是什么 http://arxiv.org/pdf/1202.5230v1.pdf .

谢谢

Answer 1

C(3,n) 应该可以。基本上，您需要整个图形节点集中的 3 个组合。

编辑:由于 omegamath 想要货币化，链接现已关闭，我必须进一步解释。 C(m,n) 是 N 个不同元素中 M 个元素的可能组合数，等于 (N!)/(M!*(N-M)!) 其中 ! 是一个阶乘运算，即 N! = 1*2*3*...*N。

C(3,n) = (N*(N-1)*(N-2))/(1*2*3)