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 `t`

, _{0}`t`

, ..., _{1}`t`

where
_{n}`t`

and _{i}∈T`t`

, is called a path.
_{i}Rt_{i+1}

An infinite sequence `t`

, _{0}`t`

, ..., is a path if every finite subsequence
starting with _{1}`t`

is a path in the previously defined sense.
_{0}

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.

First we define the set of nodes and edges:

` ````
T={t
```_{0},t_{1},t_{2},t_{3},t_{4},t_{5}}
R={(t_{0},t_{1}), (t_{0},t_{2}),
(t_{2},t_{3}), (t_{2},t_{4}), (t_{2},t_{5})}

The diagram below shows the tree `(T,R,t`

.
_{0})

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

Copyright © 2014 Barry Watson. All rights reserved.