You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 7 Next »

A tree is a connected graph in which there are no cycles. This implies that between any two nodes, there is only a single path.

In a directed tree (below left), it is also required that no node has indegree greater than one, i.e., that no node has more than one edge pointing to it. Therefore, it is possible that a directed graph has no cycles but it is not a directed tree – for example, consider the graph obtained by inverting the direction of all the edges in the graph below. A directed tree always has exactly one root (a node that has no edges pointing to it). Below, node A is the root.

An undirected tree (below right) can always be directed by picking one of the nodes as the root and orienting all edges away from it. Picking node A as the root in the undirected graph below gives the directed tree on the left.


Nodes that have degree one are called leaf nodes (C,G,E,H,I above). The other nodes are called interior nodes (A,B,D,F above).

A directed tree is bifurcating if all nodes have outdegree either zero or two. An undirected tree is bifurcating if all nodes have degree either three or one. Nodes whose degree exceeds the said limit (for directed trees two and for undirected trees three) are called multifurcating, an example being node B above with outdegree three and degree four.

A stemma is often a tree, although occasionally loops are introduced in the graph (which will then become a DAG) in order to represent instances of contamination. It is customary to associate extant manuscripts with the leaf nodes, in which case the interior nodes represent hypothetical lost manuscripts which may be unlabeled. Other interpretations of stemmata are also possible.


  • No labels