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

假设我们给定一个图，并要求找出该图中最大团的最小大小。图的团是图的一个子集，其中每对顶点都是相邻的，即每对顶点之间都存在一条边。在多项式时间内找到图中最大的团是不可能的，因此，给定一个小图的节点数和边数，我们将不得不找出它里面的最大团。

因此，如果输入类似于节点数 = 4，边数 = 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 := 节点数 + 1
  • 当 i + 1 < j 时，执行以下操作：
    • p := i + floor((j - i) / 2)
    • k := helper(节点数, p)
    • 如果 k < 边数，则
      • 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))

输入

4,4

输出

2

更新于：2021年10月6日

浏览量：168

开启你的职业生涯

完成课程获得认证

开始学习
广告