[
Lists Home |
Date Index |
Thread Index
]
Burak Emir <Burak.Emir@epfl.ch> writes:
>
> Elliotte Harold wrote:
>
> > Hunsberger, Peter wrote:
> >
> >
> >> I don't get the distinction. As soon as you've got a graph you've
> >> got a tree (or perhaps many trees).
> >>
> >
> > Not necessarily. All trees are graphs but not all graphs are trees.
> > For instance a pure tree can't represent a cycle but a graph can.
> > XML's rule that a node can only have one parent is not a limit of
> > graphs in general.
> >
> I think he meant a spanning tree, i.e. one that has all the nodes but
> all edges. A graph can have many spanning trees.
>
> This works for undirected edges. For directed, there might not be a
> spanning tree in the mathematical sense, but you can still
> get one if you reverse the arrows, like in this one
>
> o -> o <- o
Nothing that sophisticated, I just meant that any tree can be contained
in a graph. Guess I should have wrote something more like "As soon as
you've got a tree there is a graph that can contain it (and perhaps many
other trees)".
Which still leaves the original question; once you've got a way of
managing and manipulate graphs, why would you need a way to distinguish
trees? What does recognizing the special case get you?
|