A tree is a connected graph with no circuits or loops.
In a tree there is one and only one path between every pair of
50 £;! Theory of Computer Science
Property 1
Property 2
vertices.
Property 3 If in a graph there is a unique (i.e. one and only one) path
between every pair of vertices, then the graph is a tree.
Property 4
Property 5
a tree.
Property 6
it is a tree.
A tree with n vertices has 11 - 1 edges.
If a connected graph with n vertices has 11 - 1 edges, then it is
If a graph with no circuits has n vertices and 11 - 1 edges,tben
A leaf in a tree can be defined as a vertex of degree one. The vertices
other than leaves are called internal ve11ices.
In Fig. 2.6. for example, 1'1, "'3, "'4 are leaves and "'2 is an internal vertex.
In Fig. 2.7. "'2, 1'5. V6' Vi are leaves and 1'1, 1'3' 1'4 are internal vertices.
The following definition of ordered trees will be used for representing
derivations in context-free grammars.
Defmition 2.18 An ordered directed tree is a digraph satisfying the following
conditions:
T 1 : There is one vertex called the root of the tree which is distinguished
from all the other vertices and the root has no predecessors.
T:: There is a directed path from the root to every other vertex.
T 3 : Every ve11ex except the root has exactly one predecessor.
T 4 : The successors of each vertex are ordered 'from the left'.
Note: The condition T 4 of the definition becomes evident once we have the
diagram of the graph.
Figure 2.7 is an ordered tree with VI as the root. Figure 2.8 also gives an
ordered directed tree with V1 as the root. In this figure the successors of 1'1 are
ordered as 1':1'3' The successors of 1'3 are ordered as 1'51'6'
!\
v, !\
v 4
®
®
Fig. 2.8 An ordered directed tree.
In a tree there is one and only one path between every pair of
50 £;! Theory of Computer Science
Property 1
Property 2
vertices.
Property 3 If in a graph there is a unique (i.e. one and only one) path
between every pair of vertices, then the graph is a tree.
Property 4
Property 5
a tree.
Property 6
it is a tree.
A tree with n vertices has 11 - 1 edges.
If a connected graph with n vertices has 11 - 1 edges, then it is
If a graph with no circuits has n vertices and 11 - 1 edges,tben
A leaf in a tree can be defined as a vertex of degree one. The vertices
other than leaves are called internal ve11ices.
In Fig. 2.6. for example, 1'1, "'3, "'4 are leaves and "'2 is an internal vertex.
In Fig. 2.7. "'2, 1'5. V6' Vi are leaves and 1'1, 1'3' 1'4 are internal vertices.
The following definition of ordered trees will be used for representing
derivations in context-free grammars.
Defmition 2.18 An ordered directed tree is a digraph satisfying the following
conditions:
T 1 : There is one vertex called the root of the tree which is distinguished
from all the other vertices and the root has no predecessors.
T:: There is a directed path from the root to every other vertex.
T 3 : Every ve11ex except the root has exactly one predecessor.
T 4 : The successors of each vertex are ordered 'from the left'.
Note: The condition T 4 of the definition becomes evident once we have the
diagram of the graph.
Figure 2.7 is an ordered tree with VI as the root. Figure 2.8 also gives an
ordered directed tree with V1 as the root. In this figure the successors of 1'1 are
ordered as 1':1'3' The successors of 1'3 are ordered as 1'51'6'
!\
v, !\
v 4
®
®
Fig. 2.8 An ordered directed tree.