Page 665 - Discrete Mathematics and Its Applications

644 10 / Graphs

TABLE 1 Graph Terminology.
Type Edges Multiple Edges Allowed? Loops Allowed?
Simple graph Undirected No No
Multigraph Undirected Yes No
Pseudograph Undirected Yes Yes
Simple directed graph Directed No No
Directed multigraph Directed Yes Yes
Mixed graph Directed and undirected Yes Yes

For some models we may need a graph where some edges are undirected, while others are
directed.A graph with both directed and undirected edges is called a mixed graph. For example,
a mixed graph might be used to model a computer network containing links that operate in both
directions and other links that operate only in one direction.
This terminology for the various types of graphs is summarized in Table 1. We will some-
times use the term graph as a general term to describe graphs with directed or undirected edges
(or both), with or without loops, and with or without multiple edges. At other times, when the
context is clear, we will use the term graph to refer only to undirected graphs.
Because of the relatively modern interest in graph theory, and because it has applications to a
wide variety of disciplines, many different terminologies of graph theory have been introduced.
The reader should determine how such terms are being used whenever they are encountered.
The terminology used by mathematicians to describe graphs has been increasingly standardized,
but the terminology used to discuss graphs when they are used in other disciplines is still quite
varied. Although the terminology used to describe graphs may vary, three key questions can
help us understand the structure of a graph:
Are the edges of the graph undirected or directed (or both)?
Ifthegraphisundirected,aremultipleedgespresentthatconnectthesamepairofvertices?
If the graph is directed, are multiple directed edges present?
Are loops present?

Answering such questions helps us understand graphs. It is less important to remember the
particular terminology used.

Graph Models

Graphs are used in a wide variety of models.We began this section by describing how to construct
graph models of communications networks linking data centers. We will complete this section
by describing some diverse graph models for some interesting applications. We will return to
many of these applications later in this chapter and in Chapter 11. We will introduce additional
graph models in subsequent sections of this and later chapters. Also, recall that directed graph
Can you find a subject to
models for some applications were introduced in Chapter 9. When we build a graph model, we
which graph theory has
not been applied? need to make sure that we have correctly answered the three key questions we posed about the
structure of a graph.
SOCIAL NETWORKS Graphs are extensively used to model social structures based on dif-
ferent kinds of relationships between people or groups of people. These social structures, and the
graphs that represent them, are known as social networks. In these graph models, individuals
or organizations are represented by vertices; relationships between individuals or organizations
are represented by edges. The study of social networks is an extremely active multidisciplinary
area, and many different types of relationships between people have been studied using them.