TABLE OF CONTENTS In this section we give some definitions of standard graph-theoretical terms used throughout the remainder of this book.
A graph G is a tuple (V, E) which consists of a finite set V of vertices and a finite set E of edges; each edge is an unordered pair of vertices. We often denote the set of vertices of G by V(G) and the set of edges by E(G). Figure 2.1 depicts a graph G, where each vertex in V(G)={ ? 1, ? 2, , ? 6} is drawn by a small black circle and each edge in E(G)={ e 1, e 2, , e 9} is drawn by a line segment. The number of vertices of G is denoted by n, that is, n=V, and the number of edges of G is denoted by m, that is, m= E. Thus n=6 and m=9 for the graph in Fig. 2.1.
If a graph G has no multiple edges or loops, then G is called a simple graph. Multiple edges join the same pair of vertices, while a loop joins a vertex itself. A graph in which loops and multiple edges are allowed is called a multigraph. In the remainder of the...
