@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 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.
