带标号的接通图计数

带标号的连通图计数

统计 n 个顶点的连通图有多少个，每个顶点有标号。记 f(n) 为带标记的连通图的个数，g(n) 为带标记的非连通图的个数，则 f(n) + g(n) = h(n) = 2^(n(n-1)/2) ；考虑 g(n) 的计数：按照结点 1 所在的联通分量的点数分类，设结点 1 所在联通分量包含 k 点（k  = 1 ... n-1）则有 C(n-1, k -1) 种不同情况，每种情况下，结点 1 所在连通分量有 f(k) 种，剩余的 n - k 点组成的图有 h(n-k) 种，所以有递推关系：g(n) = ∑c(n-1, k-1)f(k)h(n-k), k = 1...n ；初始值为 f(1)=1, g(1)=1。

另外，h(n) / h(n-1) = 2^(n(n-1)/2-(n-1)(n-2)/2) = 2^(n-1)，所以 h(n) = h(n-1)2^(n-1)

public class NumberOfConnectedGraph {

	public static long solve(int N) {
		
		long[] f = new long[N+1];	// 连通图数目
		long[] g = new long[N+1];	// 非连通图数目
		long[] h = new long[N+1];	// 图数目
		
		f[1] = 1; g[1] = 1; h[1] = 1;
		
		for ( int n=2; n<=N; n++ ) {
			
			// h(n) = h(n-1) * 2^(n-1)
			h[n] = ( 1 << (n-1) ) * h[n-1];
			
			long comb = 1;
			g[n] = 0;
			
			for ( int k=1; k<=n-1; k++ ) {
				// 递推 c(n-1,k-1) = c(n,k-2)*(n-k+1)/(k-1)
				comb = (k==1)?1:comb*(n-k+1)/(k-1);
				g[n] += comb * f[k] * h[n-k];
			}
			
			f[n] = h[n] - g[n];  
		}
		
		return f[N];
	}
	
	// 测试
	public static void main(String[] args) {
		int[] v = { 3, 4, 5, 6 };
		for ( int x : v ) {
			System.out.println(solve(x));
		}

	}

}