Diff for "TreeStructures"

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.