Here is an DP solution:
(consider only simple graph, with at most 1 line between any 2 distinct
points, and no point connect to itself)
Suppose f(n,m) is the number of ways m lines can connect n points.
Then f(n,m) = 0 when m n-1 or m n(n-1)/2;
For graph with n vertices and m edges (connected or disconnected), the
overall count is C(n*(n-1)/2, m).
There are 2 types:
1) connected:
The number is f(n,m) that to be computed.
2) disconnected:
Consider the connected component containing vertex 1, suppose it has n'
vertices and m' edges. Then:
a. there are C(n-1, n'-1) ways to select the points in the component
b. there f(n',m') ways to connect the n' points using m' edges
c. the rest n-n' vertices and m-m' edges can be arbitrarily placed.
In summary, f(n,m) = C(n*(n-1)/2, m) - ∑(∑C(n-1, n'-1) * f(n', m') *
C((n-n')*(n-n'-1)/2, m-m') for m' in [n'-1,m]) for n' in [1, n-1]
(C(N, K) is binomial coefficient choosing K from N)
The overall time complexity is O(m^2*n^2), and space complexity is O(mn)
On 2012-2-8 12:03, rspr wrote:
Hi All,
can there be a formulato which we can estimate how many ways (n-1)
lines can connect n points in the same way how many ways n lines can
connect n points and so onthere is one way that we store the
information in adjacency list or in adjacency matrixand will check
for the same for every event in sample space.is there any other
way that can optimize this calculation or may it possible that we can
directly calculate it.
.
rspr
--
You received this message because you are subscribed to the Google Groups Algorithm
Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
