Page 663 - Discrete Mathematics and Its Applications

642 10 / Graphs

Detroit
New York
San Francisco Chicago
Washington
Denver

Los Angeles
FIGURE 1 A Computer Network.

graphs by using points to represent vertices and line segments, possibly curved, to represent
edges, where the endpoints of a line segment representing an edge are the points representing
the endpoints of the edge. When we draw a graph, we generally try to draw edges so that they do
not cross. However, this is not necessary because any depiction using points to represent vertices
and any form of connection between vertices can be used. Indeed, there are some graphs that
cannot be drawn in the plane without edges crossing (see Section 10.7). The key point is that
the way we draw a graph is arbitrary, as long as the correct connections between vertices are
depicted.
Note that each edge of the graph representing this computer network connects two different
vertices. That is, no edge connects a vertex to itself. Furthermore, no two different edges connect
the same pair of vertices. A graph in which each edge connects two different vertices and where
no two edges connect the same pair of vertices is called a simple graph. Note that in a simple
graph, each edge is associated to an unordered pair of vertices, and no other edge is associated
to this same edge. Consequently, when there is an edge of a simple graph associated to {u, v},
we can also say, without possible confusion, that {u, v} is an edge of the graph.
A computer network may contain multiple links between data centers, as shown in Figure 2.
To model such networks we need graphs that have more than one edge connecting the same
pair of vertices. Graphs that may have multiple edges connecting the same vertices are called
multigraphs.When there are m different edges associated to the same unordered pair of vertices
{u, v}, we also say that {u, v} is an edge of multiplicity m. That is, we can think of this set of
edges as m different copies of an edge {u, v}.

Detroit
Chicago New York
San Francisco
Washington
Denver

Los Angeles
FIGURE 2 A Computer Network with Multiple Links between Data Centers.

Sometimes a communications link connects a data center with itself, perhaps a feedback
loop for diagnostic purposes. Such a network is illustrated in Figure 3. To model this network we

Detroit
Chicago New York

San Francisco

Denver
Washington

Los Angeles

FIGURE 3 A Computer Network with Diagnostic Links.