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.
On May 13, 10:51 pm, "Bruno Avila" <[EMAIL PROTECTED]> wrote: > Yes, you're right. It depends on the topology of the graph. Do you > have any references for the upper or lower bound? Or even an > asymptotic of form O(2^k)? > > Bruno > > On Tue, May 13, 2008 at 12:28 PM, Geoffrey Summerhayes > > <[EMAIL PROTECTED]> wrote: > > > On May 12, 8:20 pm, brunotavila <[EMAIL PROTECTED]> wrote: > > > Hi people, > > > > How to calculate the number of binary trees that are subgraphs of a > > > given connected, undirected, unweighted and simple (no parallel edges > > > nor loops) graph? > > > Haven't given it too much thought, but I believe the number is > > dependant on the actual topology of the graph. It should be possible > > to calculate an upper and lower bound, but for an accurate number for > > a given graph I think you're stuck with counting them. > > > --- > > 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 -~----------~----~----~----~------~----~------~--~---
