.
On 5/14/08, 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. We can use the kircofs law. We will have to deal with only fundamental circuitrs and not other circuits 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 > > > -- Ciao, Ajinkya --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
