Differences between revisions 2 and 4 (spanning 2 versions)
⇤ ← Revision 2 as of 2004-08-13 19:29:24 →
Size: 1204
Editor: yakko
Comment:
← Revision 4 as of 2004-08-13 19:38:32 → ⇥
Size: 1898
Editor: yakko
Comment:
Deletions are marked like this. Additions are marked like this.
Line 8: Line 8:
   1. ''x'' is an ancestor of ''y'' if ''x'' is on the unique simple path between ''r'' and ''y''.
   1. In the case above, ''y'' is a descendent of ''x''.		    1. ''x'' is an '''ancestor''' of ''y'' if ''x'' is on the unique simple path between ''r'' and ''y''.
   1. In the case above, ''y'' is a '''descendent''' of ''x''.
Line 13: Line 13:
   1. The '''subtree rooted at ''x'' '''is the tree induced by descendants of ''x''.    1. We use '''child''' and '''parent''' for nodes with edges between them. Likewise we use the term siblings for nodes that have the same parent.
   1. A node with no children is an '''external node'''
   1. A non-leaf node is an '''internal node.'''
   1. The '''subtree rooted at ''x'' '''is the tree induced by descendants of ''x'', rooted at ''x''.
   1. The number of children of a node in a rooted tree ''T'' is called the '''degree of the node'''.
   1. The length of the path (edges) from the root ''r'' to a node ''x'' is the '''depth of ''x'' in ''T'''''.
   1. The '''height of a ''node''''' in a tree is the number of edges on the longest simple downward path from the node to a leaf.
   1. The '''height of a tree''' is the height of its root.

Here we give definitions and links to several different types of tree structures

Simple Definitions:

  1. A tree (or free tree) is a connected, acyclic, undirected graph

  2. If an undirected graph is acyclic, but disconnected, it is called a forest.

  3. rooted trees have a distinguished node called the root - r.

  4. x is an ancestor of y if x is on the unique simple path between r and y.

  5. In the case above, y is a descendent of x.

  6. A node is both a descendent and a ancestor to itself.

  7. If x is an ancestor to y and x!=y then x is a proper acestor of y.

  8. Proper descendent is similarly defined.

  9. We use child and parent for nodes with edges between them. Likewise we use the term siblings for nodes that have the same parent.

  10. A node with no children is an external node

  11. A non-leaf node is an internal node.

  12. The subtree rooted at x is the tree induced by descendants of x, rooted at x.

  13. The number of children of a node in a rooted tree T is called the degree of the node.

  14. The length of the path (edges) from the root r to a node x is the depth of x in T.

  15. The height of a node in a tree is the number of edges on the longest simple downward path from the node to a leaf.

  16. The height of a tree is the height of its root.

The following are equivalent:

  1. G is a free tree.

  2. Any 2 vertices in G are connected by a unique SimplePath

  3. G is connected, but if any edge is removed from E, the resulting graph is disconnected
  4. G is connected, and |E|=|V|-1.
  5. G is acyclic, and |E|=|V|-1.
  6. G is acyclic, but if any edge is added to E, the resulting graph contains a cycle.

TreeStructures (last edited 2018-04-01 17:45:24 by scot)