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. (01)
Yes, though one can define trees so that multiple roots are allowed,
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
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. (02)
-chris (03)
_________________________________________________________________
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 (04)
|