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

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

因此，如果输入类似于n = 3 k = 2，则输出将为36，因为有八个具有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。

为了解决这个问题，我们将遵循以下步骤：

• 定义一个函数choose()。它将接收n，k
• product := 1
• 对于i从n到n-k，递减1，执行：
  • product := product * i
• 对于i从1到k，执行：
  • product := product / i
• 返回product作为整数
• 定义一个函数util()。它将接收d，n
• 返回choose(n-1, d) * 2 ^(choose(n-1, 2))
• 从主方法中执行以下操作：
• total := 0
• 对于d从0到n - 1，执行：
  • total := total + util(d, n) * d^k
  • total := total mod 1005060097
• 返回(total * n) mod 1005060097

示例

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

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

Arnab Chakraborty

更新于: 2021年10月25日

258 次查看

开启你的职业生涯

通过完成课程获得认证

开始