The Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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
Read An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Virgil
3/11/08
Read Re: An Argument for the Subroot Node
G. Frege
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Virgil
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Virgil
3/11/08
Read Re: An Argument for the Subroot Node
G. Frege
3/11/08
Read Re: An Argument for the Subroot Node
J. Antonio Perez M.
3/11/08
Read Re: An Argument for the Subroot Node
G. Frege
3/11/08
Read Re: An Argument for the Subroot Node
G. Frege
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
briggs@encompasserve.org
3/14/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/14/08
Read Re: An Argument for the Subroot Node
David R Tribble
3/14/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
J. Antonio Perez M.
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/11/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/14/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/14/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/14/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/11/08
Read Re: An Argument for the Subroot Node
David R Tribble
3/11/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/11/08
Read Re: An Argument for the Subroot Node
LudovicoVan

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.