在图中找出最大团的最小大小的程序（Python）

假设我们已经有一个图，并被要求在图中找出最大团的最小大小。一个图的最大团是满足每对顶点之间有边缘的图的一个子集，即每对顶点之间都存在边缘。在多项式时间内找到图中的最大团是不可能的，因此我们需要在小图的节点和边数给定的情况下找到它的最大团。

因此，如果输入类似于 nodes = 4, edges =4; 那么输出将是 2。

在上面的图中，最大团的大小为 2。

要解决这个问题，我们将遵循以下步骤 –

定义一个函数 helper()。这将带有 x 和y 作为参数
- ga := x mod y
- gb := y – ga
- sa := 商的价值(x / y) + 1
- sb := 商的价值(x / y)
- 返回 ga * gb * sa * sb + ga * (ga – 1) * sa * sa / 2 + gb * (gb – 1) * sb * sb / 2
i := 1
j := nodes + 1
当 i + 1 < j 时执行以下操作
- p := i + floor value of((j – i) / 2)
- k := helper(nodes, p)
- 如果 k < edges，那么
  - i := p
- 否则，
  - j := p
返回 j

示例

让我们看一下以下实现以更好的了解 –

import math
def helper(x, y):
    ga = x % y
    gb = y - ga
    sa = x // y + 1
    sb = x // y
    return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2

def solve(nodes, edges):
    i = 1
    j = nodes + 1
    while i + 1 < j:
        p = i + (j - i) // 2
        k = helper(nodes, p)
        if k < edges:
            i = p
        else:
            j = p
    return j

print(solve(4, 4))