グラフ理論と組み合わせ論の問題

最近トッポコーダーの「ランドムグラフ」と言う問題を挑戦したが解けませんでした。　目的は全てな頂点が接続されている部分が含まれているグラフ確率を計算する事です。　Outputting the number of graphs with a given number of vertices (up to 50), is feasible, but iterating over all of these graphs to determine which ones contain at least one connected component of 4 or more vertices is non-trivial. For 50 vertices, this would involve a 1275-bit bitmap, so checking all states would be O(2^1275), which is intractable. An alternative approach might be some sort of dynamic programming on the number of overall vertices in the graph and the number of vertices in the connected component. However, the transition from (k,r) to (k+1,r+1) was not entirely clear, as for a larger k value, there might be two connected components of r or more vertices.
The actual solution involves both complementarity and non-trivial dynamic programming. The complementarity case involves solving not for the probability of a graph with a connected component of four vertices but instead solving for the probability that such a graph does not exist. Defining this value as f, the solution to the problem is 1-f. f is defined as a function of (r,a,b,c) where r is the number of vertices which remain to be added, a is the number of 1-vertex components, b is the number of 2-vertex components, and c is the number of 3-vertex components. The initial problem f(n,0,0,0) can be solved via depth-first search with memorization. At each recursive call, r is decremented. In the base case, f(0,a,b,c)=1. Complexity is O(50*25*17)=O(21250), as r is determined by the values of a,b, and c.