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


Tonico wrote: > On Mar 11, 5:42 pm, Tony Orlow <t...@lightlink.com> wrote: >> G. Frege wrote: >>> On Mon, 10 Mar 2008 23:44:16 0500, Tony Orlow <t...@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." >> > ************************************************************ > > Where did you get that definition from?
It's what it says on that Wikipedia page G. Frege cited. :)
According to it, the perimeter > of a triangle is a tree...which, of course, it is not.
That's true. Perhaps Wikipedia wasn't the best source to cite.
> > A tree is a connected graph without any cycles. Period. This is not an > "alternative" definition to the nonsense written above. This is THE > definition of a tree in graph theory and it is not equivalent to what > you wrote above. > > Regards > Tonio > > Ps. By the way, are you trying to make some point by tagging a binary > ""tree"" the way you did? Where are you heading?
Good question. I'm partly just sharing the idea of extrapolating backwards above the root node to see what might give rise to it in the first place. I thought it a nice discovery.
Let's say we number the root on level 0 as 1 and the subroot as 0. As we number the nodes at each level, we have 2^n nodes up to and including level n, for n>1. This would appear to be a power set relation, would it not? Indeed, if we identify each node by the bit string leading from subroot 0 to that node, where a 0 is a left branch and a 1 is a right, then each of those bit strings is a unique binary natural, with no natural excluded, and alternatively represents a unique subset of the set of levels, with no subset excluded. A left branch 0 may be considered to exclude that level, and a right branch 1 to include it. Thus this countably infinite set of binary naturals IS the power set of the countably infinite set of levels, and some contradiction ensues regarding the power set result.
This is related to the question as to the required depth for a binary tree with a countably infinite number of paths. How deep was that again?
Have a nice day.
Tony

