Chapter 20 Questions
Multiple Choice Questions
1. A graph consists of ______ sets.
a. two
b. three
c. four
d. five
2. A subset of a graph’s vertices and edges is known as a ______.
a. bar graph
b. line graph
c. subgraph
d. circuit
3. Two vertices that are joined by an undirected edge are said to be ______ each other.
a. related to
b. bordering
c. utilizing
d. adjacent to
4. A path is a sequence of ______ in a graph.
a. vertices
b. edges
c. subgraphs
d. cycles
5. All ______ begin and end at the same vertex and do not pass through any other vertices more than once.
a. paths
b. simple paths
c. cycles
d. simple cycles
6. Which of the following is true about a simple cycle?
a. it can pass through a vertex more than once
b. it cannot pass through a vertex more than once
c. it begins at one vertex and ends at another
d. it passes through only one vertex
7. A graph is ______ if each pair of distinct vertices has a path between them.
a. complete
b. disconnected
c. connected
d. full
8. A graph is ______ if it has at least one pair of vertices without a path between them.
a. complete
Chapter 20 Questions
b. disconnected
c. connected
d. full
9. A complete graph has a(n) ______ between each pair of distinct vertices.
a. edge
b. path
c. cycle
d. circuit
10. A ______ can have duplicate edges between vertices.
a. spanning tree
b. connected graph
c. complete graph
d. multigraph
11. A self edge is also called a ______.
a. cycle
b. loop
c. circuit
d. multigraph
12. The ______ of a weighted graph have numeric labels.
a. vertices
b. edges
c. paths
d. cycles
13. The edges in a ______ indicate a direction.
a. complete graph
b. multigraph
c. digraph
d. spanning tree
14. If a graph has a directed edge from vertex x to vertex y, which of the following is true about x and y?
a. y is a predecessor of x
b. x is a successor of y
c. x is adjacent to y
d. y is adjacent to x
15. A graph-traversal algorithm stops when it ______.
a. first encounters the designated destination vertex
b. has visited all the vertices that it can reach
c. has visited all the vertices
d. has visited all the vertices and has returned to the origin vertex
16. A ______ is the subset of vertices visited during a traversal that begins at a given vertex.
a. circuit
Chapter 20 Questions
b. multigraph
c. digraph
d. connected component
17. An iterative DFS traversal algorithm uses a(n) ______.
a. list
b. array
c. queue
d. stack
18. A ______ order is a list of vertices in a directed graph without cycles such that vertex x precedes vertex y if the
graph has a directed edge from x to y.
a. graphical
b. topological
c. hierarchical
d. spatial
19. A ______ is an undirected connected graph without cycles.
a. tree
b. multigraph
c. digraph
d. connected component
20. A connected undirected graph that has n vertices must have at least ______ edges.
a. n
b. n – 1
c. n / 2
d. n * 2
21. A connected undirected graph that has n vertices and exactly n – 1 edges ______.
a. cannot contain a cycle
b. must contain at least one cycle
c. can contain at most two cycles
d. must contain at least two cycles
22. A connected undirected graph that has n vertices and more than n – 1 edges ______.
a. cannot contain a cycle
b. must contain at least one cycle
c. can contain at most two cycles
d. must contain at least two cycles
23. A tree with n nodes must contain ______ edges.
a. n
b. n – 1
c. n – 2
d. n / 2
24. The sum of the weights of the edges in a path can be called all of the following EXCEPT ______.
Chapter 20 Questions
a. length
b. weight
c. height
d. cost
25. A ______ is a special cycle that passes through every vertex in a graph exactly once.
a. multigraph
b. tree
c. spanning tree
d. circuit
26. A(n) ______ begins at a vertex v, passes through every edge exactly once, and terminates at v.
a. multigraph
b. spanning tree
c. Euler circuit
d. Hamilton circuit
27. A(n) ______ begins at a vertex v, passes through every vertex exactly once, and terminates at v.
a. multigraph
b. spanning tree
c. Euler circuit
d. Hamilton circuit
28. An Euler circuit exists if and only if each vertex touches ______.
a. two edges
b. three edges
c. an even number of edges
d. an odd number of edges
29. Given the following graph and neighboring list, the breath first order starting from vertex A is
a) A, B, C, D, E, F
b) A, E, C, B, D, F
c) A, B, C, E, F, D
d) A, B, F, D, E, C
Chapter 20 Questions
True/False Questions
1. Adjacent vertices are joined by an edge.
2. A simple path may pass through the same vertex more than once.
3. All paths begin and end at the same vertex.
4. A simple cycle only passes through one vertex.
5. All complete graphs are connected.
6. A connected graph has an edge between every pair of vertices.
7. A connected graph can have a pair of vertices without an edge between them.
8. Each edge in a graph cannot begin and end at the same vertex.
9. In a digraph, each pair of vertices may be joined by only one edge.
10. The adjacency matrix for an undirected graph is symmetrical.
11. A connected undirected graph that has n vertices and exactly n – 1 edges cannot contain a cycle.
12. The adjacency matrix of a graph is always symmetric with respect to the diagonal line.
Chapter 20 Questions
Short Answer Questions
1. Define a path between two vertices.
2. What is a simple path?
3. What is a cycle?
4. What is a simple cycle?
5. What is a complete graph?
6. What is a self edge?
7. What is a weighted graph?
8. What are two differences between a directed graph and an undirected graph?
9. What are the two most common implementations of a graph?
10. How does the depth-first search (DFS) strategy of graph traversal differ from the breadth-first search (BFS)
strategy?
11. What is a spanning tree?
12. What is a minimum spanning tree?
13. How is the cost of a spanning tree calculated?
14. What is the shortest path between two vertices in a weighted graph?
15. What is a planar graph?