求解含n个节点e条边的无向图的最小clique（团）规模

我们需要计算给定n个节点、e条边的无向图中，必然存在的最小团（clique）尺寸。其中团指图的顶点子集，该子集中任意两个不同顶点间都存在唯一的边相连，属于完全图组件。

相关说明 #

• 给定图为无向图
• 尺寸指团包含的节点数量

参考示例 #

• 给定5个节点、6条边时，最小团尺寸为2
• 给定5个节点、7条边时，最小团尺寸为3

计算逻辑 #

该问题可以通过图论中的Turán定理求解，核心逻辑如下：
不含r团的n个节点无向图的最大边数为Turán数T(n, r-1)，我们只需要找到最小的正整数r，满足给定的边数e > T(n, r-1)，这个r就是所求的最小团尺寸。

Turán数计算公式：
将n个节点划分为k个大小尽可能均匀的组，组间连边、组内不连边得到的完全多部图的边数即为T(n, k)，公式为：
T(n, k) = (1 - 1/k) * n² / 2 - s*(k-s)/(2k)
其中s = n mod k，s个分组的大小为⌈n/k⌉，剩下k-s个分组的大小为⌊n/k⌋。

内容的提问来源于stack exchange，提问作者trovi