[algogeeks] Re: How many ways n points can be connected
@Terence: The DP approach is nice. if we have constraint likewhile 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 edgesagain we have to check that is it making more trianglethen 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 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- 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.
Re: [algogeeks] Re: How many ways n points can be connected
@rspr: Are you talking about dependencies in my approach? or adding new constraints? In my DP approach, f(n,m) only depends on f(n-1,m'), f(n-2, m') ,..., f(1,m') (m' = m) Using s(n,m) denoting the number of all graphs of n vertices and m edges, obviously s(n,m) = C(n(n-1)/2, m) Instead of counting connected graphs f(n,m), I count the number of the disconnected graphs g(n,m) = s(n,m)-f(n,m) 1. choose the n' (n'n) points in the first connected component (containing 1st vertex): C(n-1, n'-1) 2. count the number of ways to connect those n' vertices with m' (m'=m) edges: f(n',m') 3. count the number of ways to place the rest (m-m') edges among the reset (n-n') vertices: s(n-n', m-m') Total number of disconnected graphs of this type is: C(n-1, n'-1) * f(n',m') * s(n-n', m-m') Sum it over all (n',m') (n'n, m'=m), we get g(n,m), then f(n,m) = s(n,m)-g(n,m) On 2012-2-9 16:52, rspr wrote: @Terence: The DP approach is nice. if we have constraint likewhile 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 edgesagain we have to check that is it making more trianglethen 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, Terencetechnic@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 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- 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.
[algogeeks] Re: How many ways n points can be connected
Let's start with n-1 lines Build up the edges like this: Start by connecting any point to any other point. There are n*(n-1)/2 ways to do this. Then add edges from a connect point to an unconnected point. For the first edge added this way, there are 2*(n-2) options. After that it is 3*(n-3), 4*(n-4)...(n-1)*1. But that generates all of the orders in which the edges can be added, so you have to divide out (n-1)!. If you simplify that out, you get n!/2. For more than n-1 lines you need to specify the constraints. Can there be multiple edges connecting the same pair of points? Either way, look for the pattern in the number of ways the edges can be selected and multiply it out. Don On Feb 7, 10:03 pm, rspr ravishanker@gmail.com 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.
[algogeeks] Re: How many ways n points can be connected
@Don: I had the similar approach, but I didn't think of dividing by (n-1)! Why is this needed? -- I think this is to avoid the cases in which, just the order of picking the nodes is different and lines drawn are same. How is this (n-1)! -- i might be missing the the very basic thing.. plz correct. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/BMUax98JaNAJ. 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.
[algogeeks] Re: How many ways n points can be connected
The approach of adding one edge connecting a connected point to an unconnected point will produce every possible set of n-1 edges which connect all the points, but it will include duplicates, because it can generate all of those edges in any order. There are (n-1)! possible orders that the same set of edges can be generated, so to get the number of unique sets of edges, you have to divide by (n-1)!. Don On Feb 8, 11:43 am, sravanreddy001 sravanreddy...@gmail.com wrote: @Don: I had the similar approach, but I didn't think of dividing by (n-1)! Why is this needed? -- I think this is to avoid the cases in which, just the order of picking the nodes is different and lines drawn are same. How is this (n-1)! -- i might be missing the the very basic thing.. plz correct. -- 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.
[algogeeks] Re: How many ways n points can be connected
@Don: thank you. each possible arrangement of lines can be done in (n-1)! ways.. and only one is needed of it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/WlW-U-4MBUgJ. 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.
