Trees

A directed graph is a pair (T,R) where T is a set and R is a binary relation on T, i.e., R⊆T×T.

The finite sequence t0, t1, ..., tn where ti∈T and tiRti+1, is called a path.

An infinite sequence t0, t1, ..., is a path if every finite subsequence starting with t0 is a path in the previously defined sense.

A tree is a triple (T,R,r) such that (T,R) is a directed graph, r∈T and for all t∈T there is a unique path from r to t. The elements of T are called the nodes of the tree. The node r is called the root of the tree. The elements of R are called the edges, or arcs, of the tree. For an edge (t,s)∈R, t is called the parent node, and s is called the child node. A node t is called a leaf if it has no children.

A branch is a path that either terminates at a leaf, or is infinite. In a finitely branching tree, there is no node which has an infinite number of children.

Example

First we define the set of nodes and edges:

	
T={t0,t1,t2,t3,t4,t5}
R={(t0,t1), (t0,t2),
    (t2,t3), (t2,t4), (t2,t5)}
	
      

The diagram below shows the tree (T,R,t0).

References

Doets, Kees. From Logic to Logic Programming. MIT Press, 1994.