2

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

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

谢谢

4

1 回答 1

6

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)

于 2012-10-05T08:21:40.340 回答