Question

如何求有n个顶点的无向连通图个数？

顶点用v1,v2...vn标识，以示区别，边数任意，但无平行边，求能构成几种不同的连通图。
例如 n=3 时，连通图数 s=4 ，分别是有两条边的三种情况和有三条边的一种情况。

这个问题有公式吗？或者简单一点的递推公式？

Answer 1

对于一个具有n个顶点的无向连通图,它包含的连通分量的个数为：n(n-1)/2。

有n个顶点的强连通图最多有n（n-1）条边，最少有n条边。

强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径（path）及v2到v1的路径的图。

最多的情况：即n个顶点中两两相连，若不计方向，n个点两两相连有n（n-1）/2条边，而由于强连通图是有向图，故每条边有两个方向，n（n-1）/2×2=n（n-1），故有n个顶点的强连通图最多有n（n-1）条边。

相关概念

连通分量：无向图 G的一个极大连通子图称为 G的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。

强连通图：有向图 G=(V,E) 中，若对于V中任意两个不同的顶点 x和 y，都存在从x到 y以及从 y到 x的路径，则称 G是强连通图。相应地有强连通分量的概念。强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连分量。

单向连通图：设G=是有向图，如果u->v意味着图G至多包含一条从u到v的简单路径，则图G为单连通图。

Answer 2

无向连通图
• 设为 f[n]，再设 n 个点的图个数为 h[n]
• 递推，减掉不合法的，有公式：
• f[n] = h[n] - sum{i<n} C(n-1,i-1) * f[i] * h[n-i]
• 可以FFT加速的样子……

Answer 3

对于一个具有n个顶点的无向连通图,它包含的连通分量的个数为：
n(n-1)/2
希望对你有帮助，记得采纳哦~

Answer 4

n(n-1)/2