>
> 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 not matter
\ the number of different binary trees that can be
formed by each of these sets. The set {b,c,d} can not be
b considered because it would for a cycle, so it
would not be a tree.
/ \
d - c
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
-~----------~----~----~----~------~----~------~--~---
