Forest (graph theory)
In graph theory, a forest is an acyclic graph. If this is connected , one speaks of a tree . Every connected component of a forest is a tree.
Sometimes it makes sense to mark a node as the root. One then speaks of a root tree . On the one hand, such roots can be defined arbitrarily. On the other hand, there are special directed graphs where a root explains itself through the structure of the edge directions, for example as the only node without an incoming / outgoing edge. Such trees are called home , or out-Trees . The in and out forests are then graphs with several such components.
Algorithms on forests
Due to their simple structure, the complexity of algorithms working on forests can usually be estimated well. Often the algorithms with a tree as a data structure work faster than other algorithms for the same problem . For example, for the problem of sorting, the heapsort working on trees is faster than a rather naive insertion sort .
Special role within graph theory
In order to be able to consider all nodes of a graph efficiently, trees or forests are often constructed from the graph for the reasons already mentioned. Methods such as breadth-first search or depth-first search are suitable for this purpose . The result is a spanning tree . A minimal spanning tree is constructed with separate consideration of the edge weights , as is done by the algorithm of Kruskal or the algorithm of Prim . This serves, for example, as the basis for algorithms for the traveling salesman problem .
Important statements and sentences
- All forests are bipartite . A bipartition is obtained by combining the nodes with respect to their distance modulo 2 to form an arbitrary, fixed node.
- All forests are planar .
- Exactly all directed acyclic graphs can be sorted topologically , so directed forests in particular.
- A graph is a forest if and only if its cyclomatic number is.
