Root (graph theory)

In graph theory, a root is a node of a graph that has been given special distinctions. The graph with a root is called the root graph .

Example tree

Roots are often used when traversing graphs (e.g. using breadth-first search or depth-first search ). The root represents the starting node. The result of the graph traversal is a spanning tree .

In the case of root trees , the respective root is the node from which all other nodes in the tree can be reached and which cannot itself be reached from any other node. A root is the only node in a tree that has no predecessor. If you draw a tree, the root is always the topmost node of the tree. In computer science, trees always have exactly one root. If the original tree is broken down into several sub-trees, the corresponding sub-trees again have exactly one specific root. If one generalizes the concept of the root to general graphs, one also speaks of sources .

Alternative definition

A node is a root if and only if:

• All other nodes of the graph can be reached from this node.
• The node has no predecessor.

example

• The root of the example tree has the brand 1.
• The root of the subtree, which consists of nodes 5, 9 and 10, has the label 5.
• The root of the subtree, which only consists of node 12, has the label 12.

Individual evidence

1. ↑ Peter Tittmann: Introduction to combinatorics . Springer, 2014, ISBN 978-3-642-54588-7 , pp. 210 , doi : 10.1007 / 978-3-642-54589-4 .