Informally, a graph
is a set of objects in which some of the objects are connected to each other in
some way. The objects are called vertices or nodes, and the
connections are called edges. For example, the United
States can be represented by a graph where the vertices are states and the
edges are the common borders between adjacent states. In this case, Hawaii and
Alaska would be vertices without any edges connected to them. We say that two
vertices are adjacent if there is an edge connecting them.
We can picture a
graph in several ways. For example, Figure 3.1 shows two ways to represent the
graph with vertices 1, 2, and 3 and edges connecting 1 to 2 and 1 to 3.

Figure 3.1
Let's do another
example. Figure 3.2 represents a graph of those states in the United States and
those provinces in Canada that touch the Pacific Ocean or that touch states and
provinces that touch the Pacific Ocean.

Figure 3.2
An interesting
problem dealing with maps is to try to color a map
with the fewest number of colors subject to the
restriction that any two adjacent areas must have distinct colors.
From a graph point of view, this means that any two distinct adjacent vertices
must have different colors.
A graph is n-colorable if there is an assignment of n colors to
its vertices such that any two distinct adjacent vertices have distinct colors. The chromatic number of a graph is the
smallest n for which it is n-colorable.
For example, the chromatic number of the graph in Figure 3.2 is 3. A graph
whose edges are the connections between all pairs of distinct vertices is
called a complete graph. It's easy to see that the chromatic number of a
complete graph with n vertices is n.
A graph is planar
if it can be drawn on a plane such that no edges intersect. For example, the
graph in Figure 3.2 is planar. A complete graph
with four vertices is planar, but a complete graph with five vertices is not
planar. A fundamental result on graph coloring – that
remained an unproven conjecture for over 100 years – states that every planar
graph is 4-colorable. The result was proven in 1976 by Kenneth Appel and Wolfgang Haken. They
used a computer to test over 1900 special cases.
A directed
graph (digraph for short) is
a graph where each edge points in one direction. For example, the vertices
could be cities and the edges could be the one-way air routes between them. For
digraphs we use arrows to denote the edges. For example, Figure 3 shows two
ways to represent the digraph with three vertices a, b, and ñ and edges from a to b, ñ to a, and ñ to b.

Figure 3.3
The degree
of a vertex is the number of edges that it touches. For directed graphs the indegree of a vertex is the number of edges pointing at
the vertex, while the outdegree of a vertex is the
number of edges pointing away from the vertex. In a digraph a vertex is called
a source
if its indegree is zero and a sink if its outdegree is zero. For example, in the digraph of Figure 3.3,
ñ is a source and b is a sink.
If a graph has more
than one edge between some pair of vertices, the graph is called a multigraph, or a directed multigraph
in case the edges point in the same direction. For example, there are usually
two or more road routes between most cities. So a graph representing road
routes between a set of cites is most likely a multigraph.
From a
computational point of view, we need to represent graphs as data. This is easy
to do because we can define a graph in terms of tuples,
sets and bags. For example, we can define a graph G as an ordered pair (V, E),
where V is a set of vertices and E is a set or bag of edges. If G is a digraph, then the
edges in E can be represented by ordered pairs, where (a, b) represents the edge with an arrow from a to b. In this case the set E of edges is a subset of V×V. For
example, the digraph in Figure 3 has vertex set {a, b, c} and edge set {‹a,
b›, ‹c, b›, ‹c, a›}.
If G is a directed multigraph, then we can represent the edges as a bag (or multiset) of ordered pairs. For example, the bag {‹a, b›, ‹a, b›, ‹b, a›} represents
three edges: two from a
to b and one from b to a.
If a graph is not
directed, we have more ways to represent the edges. We could still represent an
edge as an ordered pair ‹a, b› and
agree that it represents an undirected line between a and b. But we can also represent an edge between vertices a and b by a set {a,b}. For example, the graph in Figure 1 has
vertex set {1, 2, 3} and edge set {{1, 2}, {1, 3}}.
We often encounter
graphs that have information attached to each edge. For example, a good road
map places distances along the roads between major intersections. A graph is
called weighted if each edge is assigned a number, called a weight.
We can represent an edge ‹a, b› that
has weight w by the 3-tuple
‹a, b, w›.
In some cases we
might want to represent an unweighted graph as a weighted graph. For example,
if we have a multigraph in which we wish to
distinguish between multiple edges that occur between two vertices, then we can
assign a different weight to each edge, thereby creating a weighted multigraph.
Sometimes it's
useful to talk about portions of a graph. A subgraph
of a graph ‹V, E› is any graph of the
form ‹V', E'› where V'
V and E'
Å. For example, the
four graphs in Figure 3.5 are subgraphs of the graph
in Figure 3.4.
Figure 3.4
Figure 3.5