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

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

假设我们有一个由 n 个节点组成的无向图 G。现在考虑简单无向图的成本是其节点成本的总和。节点的成本是其度数的 D^k,其中 D 是其度数。现在我们有 n 和 k 值。我们必须找到所有可能的简单无向图的成本总和。结果可能非常大,所以返回结果模 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。

因此,总数为 121 + 63 + 23 + 01 = 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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程