Page tree

Versions Compared


  • This line was added.
  • This line was removed.
  • Formatting was changed.


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 yields the directed tree on the left.

Image RemovedImage Added           Image Removed Image Added

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

A directed tree is bifurcating if the outdegree of each node is 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 extant ancestors (whose descendants are then codices descripti) or hypothetical lost manuscripts which may remain unlabeled.

In other languages

ENDE: Baum
FR: arbre
IT: albero