在 Python 中查找所有具有 n 个节点的简单无向图的成本总和的程序

假设我们有一个有 n 个节点的无向图 G。现在考虑一个简单的无向图的成本是其节点成本的总和。并且一个节点的成本是 D^k，其中 D 是它的度数。现在我们有 n 和 k 值。我们必须找到所有可能的具有 n 个节点的简单无向图的成本之和。结果可能非常大，因此返回结果模 1005060097。

因此，如果输入类似于 n = 3 k = 2，那么输出将是 36，因为有 8 个具有 3 个节点的简单图。

• 一张只有 3 条边的图，其成本为 2^2+2^2+2^2 = 12。

• 有两条边的图，每条边的成本是 1^2+1^2+2^2 = 6。

• 三个图有一条边，每个图的代价是 0^2+1^2+1^2 = 2。

• 一张没有边的图，其成本为 0^2+0^2+0^2 = 0。

所以，总数是 12*1 + 6*3 + 2*3 + 0*1 = 36。

示例

让我们看看以下实现以获得更好的理解 -

def choose(n, k):
   product = 1
   for i in range(n, n-k, -1):
      product *= i
   for i in range(1, k+1):
      product /= i
   return int(product)

def util(d, n):
   return choose(n-1, d) * 2 ** (choose(n-1, 2))

def solve(n, k):
   total = 0
   for d in range(n):
      total += util(d, n) * d ** k
      total %= 1005060097
   return (total * n) % 1005060097

n = 3
k = 2
print(solve(n, k))

输入

3, 2

36