Chapter 2: Mathematical Preliminaries ~ 47
2.2 GRAPHS AND TREES
The theory of graphs is widely applied in many areas of computer scienceformal languages, compiler writing, artificial intelligence (AI), to mention only
a few. Also. the problems in computer science can be phrased as problems in
graphs. Our interest lies mainly in trees (special types of graphs) and their
properties.
2.2.1 GRAPHS
Defmition 2.11 A graph (or undirected graph) consists of (i) a nonempty set
V c...lled the set of vertices. (ii) a set E called the set of edges, and (iii) a map
which assigns to every edge a unique unordered pair of vertices.
Representation of a Graph
Usually a graph. namely the undirected graph. is represented by a diagram
where the vertices are represented by points or small circles, and the edges by
arcs joining the vertices of the associated pair (given by the map Figure 2.3. for example, gives an undirected graph. Thus. the unordered
pair {VI, v:} is associated with the edge el: the pair (v:' v:) is associated with
e6' (e6 is a self-loop. In generaL an edge is called a self-loop if the vertices in
its associated pair coincide.)
Fig. 2.3 An undirected graph.
Defmition 2.12 A directed graph (or digraph) consists of (i) a nonempty set
V called the set of vertices, (ii) a set E called the set of edges, and (iii) a map
which assigns to every edge a unique ordered pair of vertices.
Representation of a Digraph
The representation is as in the case of undirected graphs except that the edges
; ...:'e represented by directed arcs.
Figure 2.4. for example. gives a directed graph. The ordered pairs (v:, 1'3),
(1'3, 1'4), (VI. 1'3) are associated with the edges e3' e4, e:, respectively.