Page 672 - Discrete Mathematics and Its Applications

10.2 Graph Terminology and Special Types of Graphs 651

24. a) Explain how graphs can be used to model electronic sent both these critics and all movies that are currently
mail messages in a network. Should the edges be di- being shown.
rected or undirected? Should multiple edges be al- 31. Describe a graph model that represents traditional mar-
lowed? Should loops be allowed? riages between men and women. Does this graph have
b) Describe a graph that models the electronic mail sent any special properties?
in a network in a particular week.
32. Which statements must be executed before S 6 is executed
25. How can a graph that models e-mail messages sent in a in the program in Example 8? (Use the precedence graph
networkbeusedtofindpeoplewhohaverecentlychanged in Figure 10.)
their primary e-mail address?
33. Construct a precedence graph for the following program:
26. How can a graph that models e-mail messages sent in
S 1 : x := 0
a network be used to find electronic mail mailing lists
used to send the same message to many different e-mail S 2 : x := x + 1
addresses? S 3 : y := 2
27. Describe a graph model that represents whether each per- S 4 : z := y
son at a party knows the name of each other person at the S 5 : x := x + 2
party. Should the edges be directed or undirected? Should S 6 : y := x + z
multiple edges be allowed? Should loops be allowed?
S 7 : z := 4
28. Describe a graph model that represents a subway system
in a large city. Should edges be directed or undirected? 34. Describe a discrete structure based on a graph that can
Should multiple edges be allowed? Should loops be al- be used to model airline routes and their flight times.
lowed? [Hint: Add structure to a directed graph.]
29. For each course at a university, there may be one or more 35. Describe a discrete structure based on a graph that can be
other courses that are its prerequisites. How can a graph used to model relationships between pairs of individuals
be used to model these courses and which courses are pre- in a group, where each individual may either like, dislike,
requisites for which courses? Should edges be directed or or be neutral about another individual, and the reverse
undirected? Looking at the graph model, how can we find relationship may be different. [Hint: Add structure to a
courses that do not have any prerequisites and how can directed graph. Treat separately the edges in opposite di-
we find courses that are not the prerequisite for any other rections between vertices representing two individuals.]
courses? 36. Describe a graph model that can be used to represent all
30. Describe a graph model that represents the positive rec- forms of electronic communication between two people
ommendations of movie critics, using vertices to repre- in a single graph. What kind of graph is needed?

10.2 Graph Terminology and Special Types of Graphs

Introduction

We introduce some of the basic vocabulary of graph theory in this section. We will use this vo-
cabulary later in this chapter when we solve many different types of problems. One such problem
involves determining whether a graph can be drawn in the plane so that no two of its edges cross.
Another example is deciding whether there is a one-to-one correspondence between the vertices
of two graphs that produces a one-to-one correspondence between the edges of the graphs. We
will also introduce several important families of graphs often used as examples and in models.
Several important applications will be described where these special types of graphs arise.

Basic Terminology

First, we give some terminology that describes the vertices and edges of undirected graphs.

DEFINITION 1 Two vertices u and v in an undirected graph G are called adjacent (or neighbors)in G if u
and v are endpoints of an edge e of G. Such an edge e is called incident with the vertices u
and v and e is said to connect u and v.