@Terence: The DP approach is nice. if we have constraint like....while choosing the first 3 edges if it makes a triangle so we will require n edges to connect the graph completely...in the same fashion...after selecting 2 more edges....again we have to check that is it making more triangle....then no. of total edges will increase by 1 and now we will require total n+1 edges. So in such a scenario how we can compute the sample space for every cases. so for all the all the valid m what should be the sample space for f(n,m). if M(m1,m2,...) is all the vaild m. Then how we can calcualte the dependency between sample space for f(n,m1) and f(n,m2).
@Terence On Feb 9, 8:22 am, Terence <technic....@gmail.com> wrote: > 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 formula....to 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 on....there is one way that we store the > > information in adjacency list or in adjacency matrix....and 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- Hide quoted text - > > - Show quoted text - -- 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.
