> > 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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---