n个节点的不同无标记无权重图共有多少种？是否有对应计算公式？

存在对应的通用计算公式，默认讨论无自环、无重边的无向简单图场景：你提到的3个节点仅存在链状、三角形2种形态，属于连通无标号无向简单图的计数结果，如果包含非连通图，3个节点的图总共有4种。

1. 包含非连通图的总计数公式 #

总数量a(n)基于波利亚计数定理推导，对n个节点的全排列群的边轨道进行计数，公式如下：

a(n) = (1/n!) * Σ（所有满足j₁+2j₂+…+njₙ =n的非负整数组合） [ (n! / ∏(d=1到n) (d^j_d * j_d! )) * 2^( (1/2)*Σ(d=1到n)Σ(e=1到n) gcd(d,e)*j_d*j_e ) ]

小数值验证：

• n=1：1
• n=2：2
• n=3：4
• n=4：11
• n=5：34

2. 仅统计连通图的计数公式 #

连通图的数量c(n)可通过总计数a(n)递推得到，递推公式为：

c(n) = a(n) - (1/n) * Σ(k=1到n-1) k*c(k)*a(n-k)

小数值验证：

• n=1：1
• n=2：1
• n=3：2（和你给出的示例完全匹配，对应2条边的链状、3条边的三角形）
• n=4：6
• n=5：21

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