[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 17:25:34 -0600
Message-id: <08453A03-3AA0-44BE-90FE-6867F05F7945@xxxxxxxx>
On Feb 23, 2008, at 3:04 PM, Wacek Kusnierczyk wrote:
> 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.    (01)

Well, that's just a *bit* disingenuous.  Obviously, one could define  
"tree" as a synonym for, say, "partial ordering" or "continuous  
nowhere differentiable function".  The point is that there *are*  
definitions of 'tree' in specific research communities that permit  
multiple roots, and there are contexts where it is convenient to do so.    (02)

>> 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,    (03)

In graph theory.    (04)

> and forests are disconnected    (05)

Except in the limiting case of a forest consisting of a single tree.    (06)

> -- 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,    (07)

Nor does this fine, if entirely obvious, expository point change the  
fact that in set theory a 'tree' *can* have more than one root.  Look,  
I'm not claiming it's a good or bad idea.  I was just making what I'd  
thought was a completely straightforward and uncontroversial point,  
viz., that there are in different contexts different (though obviously  
related) definitions of 'tree', and that, for *applied* purposes, you  
are free to choose the one that suits your purposes best.  Obviously,  
if you are *working* in graph theory, you would not want to alter the  
conventional definition, but I didn't take that to be the context of  
Paola's question.    (08)

> 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.    (09)

Of course.  As noted, I didn't take her question to be specifically  
graph-theoretic.    (010)

>> 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.    (011)

Well, sure thing.    (012)

-chris    (013)

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    (014)

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