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. The subtree rooted at x is the tree induced by descendants of x.

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.