498
Graphs and Trees
exerciSeS 6.1
1. Give the function g that is part of the formal definition of the directed graph shown.
a
d
c
b
1
3
2
2. Use the graph in the figure to answer the questions that follow.
a. Is the graph simple?
b. Is the graph complete?
c. Is the graph connected?
d. Can you find two paths from 3 to 6?
e. Can you find a cycle?
f. Can you find an arc whose removal will make the graph acyclic?
g. Can you find an arc whose removal will make the graph not connected?
3. Sketch a picture of each of the following graphs.
a. Simple graph with three nodes, each of degree 2
b. Graph with four nodes, with cycles of length 1, 2, 3, and 4
c. Noncomplete graph with four nodes, each of degree 4
4. Use the directed graph in the figure to answer the questions that follow.
a. Which nodes are reachable from node 3?
b. What is the length of the shortest path from node 3 to node 6?
c. What is a path from node 1 to node 6 of length 8?
5. Draw K 6 .
6. Draw K 3,4 .
7. For each of the following characteristics, draw a graph or explain why such a graph does not exist.
a. Four nodes of degree 1, 2, 3, and 4, respectively
b. Simple, four nodes of degree 1, 2, 3, and 4, respectively
c. Four nodes of degree 2, 3, 3, and 4, respectively
d. Four nodes of degree 2, 3, 3, and 3, respectively
S e c t i o n 6 . 1 review
tecHniQueS
• Use graph terminology.
Prove or disprove that two graphs are isomorphic.
• Find a planar representation of a simple graph or
prove that none exists.
Construct adjacency matrices and adjacency lists
for graphs and directed graphs.
main iDeaS
• Diverse situations can be modeled by graphs.
• Graphs can be represented in a computer by matrices or by linked lists.
W
W
1
4
3
7
2
6
5
a 5
a 2
a 3
a 4
a 1
a 6
a 7
1
2
3
5
6
4