(reformatting last email)
>
> these as 1 or 4 or something in between?
>
> Also does a single node count as a tree?
>
These are good questions. In my problem, a binary tree is different if
the set of nodes are different. For example:
a We have 9 different binary trees: {a}, {b}, {c},
\ {a,b}, {b,c}, {b,d}, {c,d}, {a,b,c}, {a,b,d}. It does
b not matter the number of different binary trees
/ \ that can be formed by each of these sets. The
d - c set {b,c,d} can not be considered because it would
for a cycle, so it would not be a tree.
My initial question was not well specified. Sorry.
Bruno
>
> On Wed, May 14, 2008 at 12:11 PM, Geoffrey Summerhayes
> <[EMAIL PROTECTED]> wrote:
> >
> > On May 14, 8:39 am, pramod <[EMAIL PROTECTED]> wrote:
> > > Let's say we have E number of edges and V number of vertices.
> > > Any subgraph which is a tree with V vertices will have V-1 edges. So
> > > we need to retain V-1 edges and eliminate the rest E-(V-1). So in a
> > > brute force manner if we retain any set of V-1 edges and see if the
> > > resultant graph is indeed a tree or not. So we need to test for E C
> > > (V-1) such cases. This is definitely an upper bound.
> > > We may optimize the above exponential algorithm by not considering
> > > those edges which are not part of any cycles since they can't be
> > > removed. And in the middle of removing the edges if we encounter an
> > > edge with vertex having a degree of only 1 then we can't remove that
> > > edge.
> >
> > To OP, what counts as a distinct binary tree? Are you going to count
> >
> > a b c b
> > \ / \ \ / \
> > b a c b c a
> > \ /
> > c a
> > (use a monospace font to view)
> >
> > these as 1 or 4 or something in between?
> >
> > Also does a single node count as a tree?
> >
> > For a minimum, counting single nodes you would get V
> > vertices/trees. For a simple, connected graph you also
> > get at least one path between any pair of nodes giving
> > an additional V*(V-1).
> >
> > So a bare minimum would have at least V*V trees.
> >
> > ----
> >
> >
> > Geoff
> >
> > > >
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
