On May 15, 4:33 pm, "Bruno Avila" <[EMAIL PROTECTED]> wrote:
> > Given the conditions for the subgraphs, it's always possible to create
> > a graph that limits the size of all the acceptable subgraphs to less
> > than
> > three nodes.
>
> In the problem, there are no constraints on the cardinality of the
> subgraphs. It could have a subgraph with all nodes (e.g. if the graph
> is a binary tree).
Got it backwards, it doesn't matter how many graphs allow for
a subgraph including all nodes, it's that there exists at least
one that limits the number of nodes in an acceptable subtree.
The limitation comes from the odd little bit earlier when you
said {b,c,d} wasn't valid because it formed a cycle. Normally
when selecting a subgraph we chose a subset of nodes and
edges so I'd pick {Nodes:(b,c,d),Edges(bc,cd)} and have a
valid tree. Under your specification, we'll have to pick a set
of nodes and consider ALL the edges connecting them.
Actually what I've said earlier is two separate ideas, the
first is that the minimum set of trees from the graph must
at least contain the individual nodes themselves, as degenerate
trees, and the shortest path from each node to every other
node.
The second part is that a complete graph of V nodes
automatically forms a cycle for any set of nodes larger
than two. We've already included all possible combinations
of two nodes just above, so we know a complete graph
cannot have more trees than the minimum. This takes
the minimum above and shows that there is at least
one graph that actually meets it.
So, given any graph of V nodes, we know we must be
able to get at least V(V+1)/2 trees from it, and we
know that there exists at least one graph of V nodes
that has exactly V(V+1)/2 trees.
Still not sure about the maximum though....
---
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
-~----------~----~----~----~------~----~------~--~---
