Christopher Menzel wrote:
> On Feb 23, 2008, at 9:19 AM, Wacek Kusnierczyk wrote:
>
>> ...
>> By definition (one from graph theory, Azamat might have had other
>> definitions in mind), a tree is a connected acyclic graph. Undirected
>> trees have no roots.
>>
>> A rooted tree is a directed tree with exactly one distinguished vertex
>> chosen as the tree's root. Following the definition (in a rooted
>> tree,
>> there is exactly one path from the root to any other vertex in the
>> graph), if a tree were to have two roots, each of them would have to
>> be
>> accessible from the other, which implies a cycle in the graph; but
>> such
>> a graph is not a tree.
>>
>
> Yes, though one can define trees so that multiple roots are allowed,
>
obviously, anyone can provide any definition one wishes for the term
'tree', in any context.
> though of course in those cases the trees would not be connected;
> you'd have what by other definitions would be called a forest, as
>
yes; and since trees are connected graphs, and forests are disconnected
-- disconnected unions of trees -- no forest is a tree (though
admittedly i'd have a hard time saying that forests are not trees ;)).
you can call a forest a 'tree', but such switching names does not change
the fact that what is referred to in graph theory by the term 'tree'
cannot have more than one root, irrespectively of how you wish to use
the term 'tree' otherwise. (01)
now, if paola was asking about graph-theoretic trees specifically, the
answer was clear. the answer is likely to be different if some other
meaning of 'tree' is considered. (02)
> Randall noted. This is the case for the general set theoretic
> definition of a tree as a partially ordered set such that the set S_n
> of predecessors of any node is well-ordered by the partial ordering
> restricted to S_n. Not surprisingly, one often subsequently finds the
> definition of a "normal" tree among the conditions for being which are
> that the tree has only one root.
>
it is easy to imagine, in addition to trees and forests, graphs that are
connected and appear, in some way, tree-like, with more than one vertex
designated as a root. but they either contain cycles, or some of their
vertices are not reachable from one or more roots. (03)
vQ (04)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx (05)
|