Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: An Argument for the Subroot Node
Replies: 28   Last Post: Mar 14, 2008 8:32 PM

 Messages: [ Previous | Next ]
 Tony Orlow Posts: 3,142 Registered: 8/23/06
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 self-referential 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 self-referential 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

Date Subject Author
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 G. Frege
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 G. Frege
3/11/08 J. Antonio Perez M.
3/11/08 G. Frege
3/11/08 G. Frege
3/11/08 Tony Orlow
3/11/08 briggs@encompasserve.org
3/14/08 Tony Orlow
3/14/08 David R Tribble
3/14/08 LudovicoVan
3/11/08 Tony Orlow
3/11/08 J. Antonio Perez M.
3/11/08 Tony Orlow
3/11/08 Tony Orlow
3/11/08 Tony Orlow
3/11/08 LudovicoVan
3/11/08 LudovicoVan
3/14/08 Tony Orlow
3/14/08 LudovicoVan
3/14/08 LudovicoVan
3/11/08 David R Tribble
3/11/08 LudovicoVan
3/11/08 LudovicoVan