
Re: An Argument for the Subroot Node
Posted:
Mar 11, 2008 1:23 PM


G. Frege wrote: > On Tue, 11 Mar 2008 08:40:29 0700 (PDT), Tonico <Tonicopm@yahoo.com> > wrote: > >>> "In graph theory, a tree is a graph in which any two vertices are >>> connected by /exactly one/ path." >>> >> Where did you get that definition from? >> > Wikipedia. Entry "Tree (graph theory)". > >> According to it, the perimeter of a triangle is a tree... >> which, of course, it is not. >> > Wait a second. If the nodes of your triangle were, say a, b, c then > (say) a, b would be connected by more than one path: > > p_1 = ((a,b), (b,c), (c,a)) > > p_2 = ((a,b), (b,c), (c,a), (a,b), (b,c), (c,a)) > [ or > p_3 = ((a,c), (c,b), (b,a)) ] > > See? >
Yes, you're right about that. There are two simple paths between a and b. It's a cycle, for that reason.
Even in a tree, there are multiple paths between any two nodes, if one is allowed to repeat nodes. Clearly that's not allowed, so a tree is best defined as having exactly one *simple* path, without any nodes repeated, between any pair of nodes. Given this restriction, little selfdirected loops don't affect that definition, since they are not allowed in any simple path due to the fact that they repeat a node. They are not true cycles, since they do not introduce new simple paths within the tree. They can be appended without damaging the integrity of the tree. They are not generally useful when scattered about, but the subroot node is justified, and not proscribed by the above definition.
See?
>> A tree is a connected graph without any cycles. Period. This is not an >> "alternative" definition to the nonsense written above. >> > Well... sure? See my (part of an) "argument" from above. > > > F. >
T.

