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