ontolog-forum
[Top] [All Lists]

## Re: [ontolog-forum] What words mean

 To: "[ontolog-forum]" Wacek Kusnierczyk Sat, 23 Feb 2008 22:04:07 +0100 <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) ```
 Current Thread Re: [ontolog-forum] What words mean, (continued) Re: [ontolog-forum] What words mean, paola . dimaio Re: [ontolog-forum] What words mean, Randall R Schulz Re: [ontolog-forum] What words mean, Christopher Menzel Re: [ontolog-forum] What words mean, Sharma, Ravi Re: [ontolog-forum] What words mean, Christopher Menzel Re: [ontolog-forum] What words mean, Azamat Re: [ontolog-forum] What words mean, paola . dimaio Re: [ontolog-forum] What words mean, Wacek Kusnierczyk Re: [ontolog-forum] What words mean, paola . dimaio Re: [ontolog-forum] What words mean, Christopher Menzel Re: [ontolog-forum] What words mean, Wacek Kusnierczyk <= Re: [ontolog-forum] What words mean, Christopher Menzel Re: [ontolog-forum] What words mean, Wacek Kusnierczyk Re: [ontolog-forum] What words mean, John F. Sowa Re: [ontolog-forum] What words mean, Barker, Sean (UK) Re: [ontolog-forum] What words mean, Christopher Menzel Re: [ontolog-forum] What words mean, John F. Sowa Re: [ontolog-forum] What words mean, John F. Sowa Re: [ontolog-forum] What words mean, Azamat Re: [ontolog-forum] What words mean, John F. Sowa Re: [ontolog-forum] What words mean, Christopher Menzel