334 CHAPTER 6 Graph Theory
6.1.1 Definitions
The Job Assignment Problem gives an insight regarding how graph theory can be used
to model a problem. Before exploring more uses of this theory, however, a more careful
definition of graphs is needed.Definition 1. A graph G = (V, E) consists of a finite nonempty set V, the elements of
which are the vertices of G, and a finite set E of unordered pairs of distinct elements of V
called the edges of G.We can think of vertices as points and edges as lines joining pairs of points. Even
though edges are defined as unordered pairs of distinct vertices, it is common to denote an
edge consisting of the vertices a and b as (a, b). In graph theory usage, the notation (b, a)
denotes the same edge as (a, b). For any edge e = (a, b) in a graph, the vertices a and b
are the ends of e, e is incident to both a and b, and the vertices a and b are adjacent.
We often call adjacent vertices neighbors. If two distinct edges have a common end, then
the edges are adjacent. For any vertex v, the degree of v, denoted deg(v), is the number of
edges incident to it. A vertex is even (or odd) if its degree is even (or odd). A vertex of
degree zero is called an isolated vertex.
These terms are illustrated in Figure 6.4.odd degree - ,.- isolated vertexadjacent
, edges
/
ends / e
ofe eK\/\
/ even degree
adjacent
verticesFigure 6.4 Names of parts of a graph.A sequence of n nonnegative numbers, dl, d2. d, is said to be graphical if there
exists a graph having n vertices with the degrees of the vertices being dl, d 2 ..... d, The
degrees of the vertices of a graph are called a degree sequence. Without loss of generality,
one can assume that d, < d 2 < ... < dn. The graph in Figure 6.4 has degree sequence 0,2,2,3,3,4.
Definition 2. A graph on n vertices having each pair of distinct vertices joined by anedge is called a complete graph and is denoted by K,. Complete graphs are often called
cliques. A graph in which each vertex has the same degree is called a regular graph. A