在 Python 中查找所有具有 n 个节点的简单无向图的成本总和的程序
假设我们有一个有n个节点的无向图G。现在考虑一个简单的无向图的成本是其节点成本的总和。并且一个节点的成本是D^k，其中D是它的度数。现在我们有n和k值。我们必须找到所有可能的具有n个节点的简单无向图的成本之和。结果可能非常大，因此返回结果模1005060097。
因此，如果输入类似于n=3k=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