ABSTRACT
Trees, as data structures, are somewhat limited because they can only represent relations of a hierarchical nature, such as that of parent and child. A generalization of a tree so that a binary relation is allowed between any pair of elements would constitute a graph-formally defined as follows:
A graph G = (V,E) consists of a finite set of vertices V = {υ1, υ2, . . . , υn} and a finite set E of edges E = {e1, e2, . . . , em} (see Figure 4.1). To each edge e there corresponds a pair of vertices (u, υ) which e is said to be incident on. While drawing a graph we represent each vertex by a dot and each edge by a line segment joining its two end vertices . A graph is said to be a directed graph (or digraph for short) (see Figure 4.2) if the vertex pair (u, υ) associated with each edge e (also called arc) is an ordered pair. Edge e is then said to be directed from vertex u to vertex υ, and the direction is shown by an arrowhead on the edge. A graph is undirected if the end vertices of all the edges are unordered (i.e., edges have no direction). Throughout this chapter we use the letters n and m to denote the number of vertices |V | and number of edges |E| respectively, in a graph. A vertex is often referred to as a node (a term more popular in applied fields).
