![]()
Chapter 1
Introduction
1.1 Graphs and Graph Models
A major publishing company has ten editors (referred to by 1, 2, …, 10) in the scientific, technical and computing areas. These ten editors have a standard meeting time during the first Friday of every month and have divided themselves into seven committees to meet later in the day to discuss specific topics of interest to the company, namely, advertising, securing reviewers, contacting new potential authors, finances, used and rented copies, electronic editions and competing textbooks. This leads us to our first example.
Example 1.1 The ten editors have decided on the seven committees: c1 = {1, 2, 3}, c2 = {1, 3, 4, 5}, c3 = {2, 5, 6, 7}, c4 = {4, 7, 8, 9}, c5 = {2, 6, 7}, c6 = {8, 9, 10}, c7 = {1, 3, 9, 10}. They have set aside three time periods for the seven committees to meet on those Fridays when all ten editors are present. Some pairs of committees cannot meet during the same period because one or two of the editors are on both committees. This situation can be modeled visually as shown in Figure 1.1.
Figure 1.1: A graph
In this figure, there are seven small circles, representing the seven committees and a straight line segment is drawn between two circles if the committees they represent have at least one committee member in common. In other words, a straight line segment between two small circles (committees) tells us that these two committees should not be scheduled to meet at the same time. This gives us a picture or a “model” of the committees and the overlapping nature of their membership.
What we have drawn in Figure 1.1 is called a graph. Formally, a graph G consists of a finite nonempty set V of objects called vertices (the singular is vertex) and a set E of 2-element subsets of V called edges. The sets V and E are the vertex set and edge set of G, respectively. So a graph G is a pair (actually an ordered pair) of two sets V and E. For this reason, some write G = (V, E). At times, it is useful to write V(G) and E(G) rather than V and E to emphasize that these are the vertex and edge sets of a particular graph G. Although G is the common symbol to use for a graph, we also use F and H, as well as G′, G″ and G1, G2, etc. Vertices are sometimes called points or nodes and edges are sometimes called lines. Indeed, there are some who use the term simple graph for what we call a graph. Two graphs G and H are equal if V(G) = V(H) and E(G) = E(H), in which case we write G = H.
It is common to represent a graph by a diagram in the plane (as we did in Figure 1.1) where the vertices are represented by points (actually small circles – open or solid) and whose edges are indicated ...
