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
-~----------~----~----~----~------~----~------~--~---
