Page 671 - Discrete Mathematics and Its Applications

650 10 / Graphs

For Exercises 3–9, determine whether the graph shown has c) A 1 ={x | x< 0},
directed or undirected edges, whether it has multiple edges, A 2 ={x |−1 <x < 0},
and whether it has one or more loops. Use your answers to A 3 ={x | 0 <x < 1},
determine the type of graph in Table 1 this graph is. A 4 ={x |−1 <x < 1},
3. a b 4. a b A 5 ={x | x> −1},
A 6 = R
14. Use the niche overlap graph in Figure 11 to determine the
species that compete with hawks.
15. Construct a niche overlap graph for six species of birds,
where the hermit thrush competes with the robin and
c d c d with the blue jay, the robin also competes with the
5. a b 6. a b mockingbird, the mockingbird also competes with the
blue jay, and the nuthatch competes with the hairy wood-
pecker.
16. Draw the acquaintanceship graph that represents thatTom
e
and Patricia, Tom and Hope, Tom and Sandy, Tom and
Amy, Tom and Marika, Jeff and Patricia, Jeff and Mary,
Patricia and Hope, Amy and Hope, and Amy and Marika
c d c d
know each other, but none of the other pairs of people
7. b 8. a e listed know each other.
17. We can use a graph to represent whether two people were
c
alive at the same time. Draw such a graph to represent
whether each pair of the mathematicians and computer
d
scientists with biographies in the first five chapters of
a d this book who died before 1900 were contemporaneous.
e b c
(Assume two people lived at the same time if they were
9. a b alive during the same year.)
18. Who can influence Fred and whom can Fred influence in
the influence graph in Example 2?
c 19. Construct an influence graph for the board members of a
f company if the President can influence the Director of Re-
search and Development, the Director of Marketing, and
e
d the Director of Operations; the Director of Research and
10. For each undirected graph in Exercises 3–9 that is not Development can influence the Director of Operations;
simple, find a set of edges to remove to make it simple. the Director of Marketing can influence the Director of
Operations; and no one can influence, or be influenced
11. Let G be a simple graph. Show that the relation R on the
set of vertices of G such that uRv if and only if there by, the Chief Financial Officer.
is an edge associated to {u, v} is a symmetric, irreflexive 20. Which other teams did Team 4 beat and which teams beat
relation on G. Team 4 in the round-robin tournament represented by the
graph in Figure 13?
12. Let G be an undirected graph with a loop at every vertex. 21. In a round-robin tournament theTigers beat the Blue Jays,
Show that the relation R on the set of vertices of G such the Tigers beat the Cardinals, the Tigers beat the Orioles,
that uRv if and only if there is an edge associated to {u, v} the Blue Jays beat the Cardinals, the Blue Jays beat the
is a symmetric, reflexive relation on G. Orioles, and the Cardinals beat the Orioles. Model this
13. The intersection graph of a collection of sets A 1 , outcome with a directed graph.
A 2 ,...,A n is the graph that has a vertex for each of these 22. Construct the call graph for a set of seven telephone
sets and has an edge connecting the vertices representing numbers 555-0011, 555-1221, 555-1333, 555-8888,
two sets if these sets have a nonempty intersection. Con- 555-2222, 555-0091, and 555-1200 if there were three
struct the intersection graph of these collections of sets. calls from 555-0011 to 555-8888 and two calls from
a) A 1 ={0, 2, 4, 6, 8}, A 2 ={0, 1, 2, 3, 4}, 555-8888 to 555-0011, two calls from 555-2222 to
555-0091, two calls from 555-1221 to each of the
A 3 ={1, 3, 5, 7, 9}, A 4 ={5, 6, 7, 8, 9},
other numbers, and one call from 555-1333 to each of
A 5 ={0, 1, 8, 9}
555-0011, 555-1221, and 555-1200.
b) A 1 ={..., −4, −3, −2, −1, 0},
23. Explain how the two telephone call graphs for calls made
A 2 ={..., −2, −1, 0, 1, 2,...}, during the month of January and calls made during the
A 3 ={..., −6, −4, −2, 0, 2, 4, 6,...}, month of February can be used to determine the new tele-
A 4 ={..., −5, −3, −1, 1, 3, 5,...}, phone numbers of people who have changed their tele-
A 5 ={..., −6, −3, 0, 3, 6,...} phone numbers.