ontolog-forum
[Top] [All Lists]

Re: [ontolog-forum] What words mean

To: "[ontolog-forum] " <ontolog-forum@xxxxxxxxxxxxxxxx>
From: Christopher Menzel <cmenzel@xxxxxxxx>
Date: Sat, 23 Feb 2008 14:22:36 -0600
Message-id: <A53F10A0-DD73-4EF5-BC99-B915224D0A8D@xxxxxxxx>
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)

<Prev in Thread] Current Thread [Next in Thread>