Chapter 2: Mathematical Preliminaries g 49
And v3e4v4e5v~ is a path from 1'3 to v~. We call 1'3e41'4e5v~ a directed path since
the edges e4 and es have the forward direction. (But 1'je~V3e3v~ is not a directed
path as e~ is in the forward direction and e3 is in the backward direction.)
Defmition 2.15 A graph (directed or undirected) is connected if there is a
path bet\veen every pair of vertices.
The graphs given by Figs. 2.3 and 2.4. for example, are connected.
Definition 2;16 A circuit in a graph is an alternating sequence 1'lelv2e~ ...
en-lVI of vertices and edges starting and ending in the same vertex such that
ei has Vi and Vi+l as the end vertices and no edge or vertex other than VI is
repeated.
In Fig. 2.3. for example. V3e3 v~e5v4e4v3' ~'1 e~1'3e4V4e5v~elVI are circuits. In
Fig. 2.4. l'je2v3e31'2ejvl and v2e3v3e4V4eSl'~ are circuits.
2.2.2 TREES
Definition 2.17 A graph (directed or undirected) is called a tree if it is
connected and has no circuits.
The graphs given in Figs. 2.6 and 2.7, for example, are trees. The graphs
given in Figs. 2.3 and 2.4 are not trees,
Note: A directed graph G is a tree iff the corresponding undirected graph
is a tree.
Fig. 2.6 A tree with four vertices.
Fig. 2.7 A tree with seven vertices.
We no",,- discuss some properties of trees (both directed and undirected)
used in developing transition systems and studying grammar rules.
And v3e4v4e5v~ is a path from 1'3 to v~. We call 1'3e41'4e5v~ a directed path since
the edges e4 and es have the forward direction. (But 1'je~V3e3v~ is not a directed
path as e~ is in the forward direction and e3 is in the backward direction.)
Defmition 2.15 A graph (directed or undirected) is connected if there is a
path bet\veen every pair of vertices.
The graphs given by Figs. 2.3 and 2.4. for example, are connected.
Definition 2;16 A circuit in a graph is an alternating sequence 1'lelv2e~ ...
en-lVI of vertices and edges starting and ending in the same vertex such that
ei has Vi and Vi+l as the end vertices and no edge or vertex other than VI is
repeated.
In Fig. 2.3. for example. V3e3 v~e5v4e4v3' ~'1 e~1'3e4V4e5v~elVI are circuits. In
Fig. 2.4. l'je2v3e31'2ejvl and v2e3v3e4V4eSl'~ are circuits.
2.2.2 TREES
Definition 2.17 A graph (directed or undirected) is called a tree if it is
connected and has no circuits.
The graphs given in Figs. 2.6 and 2.7, for example, are trees. The graphs
given in Figs. 2.3 and 2.4 are not trees,
Note: A directed graph G is a tree iff the corresponding undirected graph
is a tree.
Fig. 2.6 A tree with four vertices.
Fig. 2.7 A tree with seven vertices.
We no",,- discuss some properties of trees (both directed and undirected)
used in developing transition systems and studying grammar rules.