
Re: An Argument for the Subroot Node
Posted:
Mar 11, 2008 11:42 AM


G. Frege wrote: > On Mon, 10 Mar 2008 23:44:16 0500, Tony Orlow <tony@lightlink.com> > wrote: > >> So, in conclusion, the "complete" binary tree includes not only a root >> node, but a subroot node, which is its own parent [...]. >> > Such a structure (graph) is not a /tree/ any more (since a tree does not > have cycles _by definition_). > > See: > http://en.wikipedia.org/wiki/Tree_(graph_theory) > > > F. >
"In graph theory, a tree is a graph in which any two vertices are connected by exactly one path."
Apparently this means a simple path, with no vertices repeated, or else we could define a path that backtracks on itself, which would be different from the simple path between two nodes. If this is the case, then the selfreferential cycle hanging off the subroot node doesn't affect that property of the tree, because including it in a path would repeat that node, making it not a simple path. That node cannot be repeated in a simple path.
"Alternatively, any connected graph with no cycles is a tree."
At http://en.wikipedia.org/wiki/Cycle_graph we find:
"In graph theory, a cycle graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn. The number of vertices in a Cn equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it."
Notice that the supposed cycle you object to does NOT have two edges associated with the subroot, but only a single edge from it and back to it. In other words, such a loop doesn't quite qualify as a cycle, and doesn't present any problems in selecting a unique simple path between nodes, since taking that edge is immediately prohibited by the fact that it repeats the node you are currently on. The tree could be littered with such selfreferential fruits, and it wouldn't affect the fact there there was only one simple path between any two nodes. Would it?
Have a nice day.
Tony

