@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
@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
@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/algogeek
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
@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
cor
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
