[Top] [All Lists]

Re: [ontolog-forum] What words mean

To: "[ontolog-forum]" <ontolog-forum@xxxxxxxxxxxxxxxx>
From: Wacek Kusnierczyk <Waclaw.Marcin.Kusnierczyk@xxxxxxxxxxx>
Date: Sat, 23 Feb 2008 22:04:07 +0100
Message-id: <47C08A47.2060807@xxxxxxxxxxx>
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)

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