Free trees in data structure

A free tree is a connected, acyclic, undirected graph. We often omit the adjective “free” when we say that a graph is a tree. If an undirected graph is acyclic but possibly disconnected, it is a forest. Many algorithms that work for trees also work for trees also work for forests. Figure B.4(a) shows a free tree, and Figure B.4(b) shows a forest. The forest in Figure B.4(b) is not a tree because it is not connected. The graph in Figure B.4(c) is connected but neither a tree nor a forest, because it contains a cycle.

Free trees
Free trees

(a) A free tree. (b) A forest. (c) A graph that contains a cycle and is therefore neither a tree nor a forest.

Properties of free trees

  • Let G D .V; E/ be an undirected graph. The following statements are equivalent
  • is a free tree.
  • Any two vertices in G are connected by a unique simple path.
  • G is connected, but if any edge is removed from E, the resulting graph is disconnected.
  • G is connected, and |E| D |V | – 1
  • G is acyclic, and |E| D |V| – 1.
  • G is acyclic, but if any edge is added to E, the resulting graph contains a cycle