Trees
An acyclic graph (also known as a forest) is a graph with no cycles. A tree is a connected acyclic graph. Thus each component of a forest is tree, and any tree is a connected forest.
Theorem The following are equivalent in a graph G with n vertices.
- G is a tree.
- There is a unique path between every pair of vertices in G.
- G is connected, and every edge in G is a bridge.
- G is connected, and it has (n - 1) edges.
- G is acyclic, and it has (n - 1) edges.
- G is acyclic, and whenever any two arbitrary nonadjacent vertices in G are joined by and edge, the resulting enlarged graph G' has a unique cycle.
- G is connected, and whenever any two arbitrary nonadjacent vertices in G are joined by an edge, the resulting enlarged graph has a unique cycle.
Generally speaking, algorithms associated with trees can be divided into three types.
- Algorithms for searching and labeling a given tree.
- Algorithms for constructing various types of tree.
- Algorithms for counting trees of a particular type.
Tree A tree is a connected graph which contain no cycles.
For example,
Theorem Let T be a graph with n vertices. Then the following statements are equivalent.
- T is connected and contains no cycles.
- T is connected and has n-1 edges.
- T has n-1 edges and contains no cycles.
- T is connected and each edge is abridge.
- Any two vertices of T are connected by exactly one path.
- T contains no cycles, but the addition of any new edge creates exactly one cycles.