如何计算n个顶点的连通图总数？求8顶点连通图计数正确代码

核心思路：递推+容斥原理 #

n个顶点的连通图总数可通过所有可能的图的数量减去不连通图的数量计算，利用递推公式避免重复计数：

1. 所有图的总数：n个顶点的简单图中，每对顶点间可选有边或无边，总共有 T(n) = 2^(n*(n-1)/2) 种图。
2. 连通图递推公式：设C(n)为n个顶点的连通图数量，递推式为：

   C(n) = T(n) - sum_{k=1}^{n-1} [C(k) * C(n-1, k-1) * T(n-k)]
   

   其中：
   • C(n-1, k-1) 是从剩下的n-1个顶点中选k-1个，与固定顶点组成大小为k的连通分量的组合数；
   • T(n-k) 是剩下的n-k个顶点组成任意图的数量；
   • 求和遍历所有可能的连通分量大小k（从1到n-1），覆盖所有不连通情况。

针对n=8的代码实现（Python） #

import math

def count_connected_graphs(n):
    # 预计算所有顶点数对应的总图数T
    T = [0] * (n+1)
    for i in range(n+1):
        edge_count = i * (i-1) // 2
        T[i] = 2 ** edge_count
    
    # 动态规划预计算组合数C(n,k)
    comb = [[0]*(n+1) for _ in range(n+1)]
    for i in range(n+1):
        comb[i][0] = 1
        comb[i][i] = 1
        for j in range(1, i):
            comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
    
    # 递推计算连通图数量
    C = [0]*(n+1)
    C[1] = 1  # 1个顶点仅1种连通图
    for i in range(2, n+1):
        total = T[i]
        for k in range(1, i):
            total -= C[k] * comb[i-1][k-1] * T[i - k]
        C[i] = total
    return C[n]

# 计算8个顶点的连通图数量
print(count_connected_graphs(8))  # 输出：11117

代码说明 #

• 组合数预计算：用杨辉三角动态规划生成组合数，避免重复计算；
• 总图数预计算：提前计算每个顶点数对应的总图数，减少幂运算重复执行；
• 递推逻辑：从2个顶点开始逐步计算到n个顶点，每次精准减去所有不连通的情况，确保结果准确。

内容的提问来源于stack exchange，提问作者Usama Waheed