Graphs Chapter.24 Test Bank Answers

Chapter 24: Graphs

Multiple Choice Questions:

1) In graph terminology, the nodes are referred to as ____________________.

a) vertices

b) edges

c) parents

d) children

e) none of the above

2) In a(n) _____________________ graph, an edge from node labeled A to a node labeled B is the same as having an edge from B to A.

a) directed

b) undirected

c) sparse

d) tree-like

e) none of the above

3) Which of the following describes vertices that are adjacent?

a) They are close to one another in the visual representation of the graph.

b) They are far apart in the visual representation of the graph.

c) There is no edge connecting them.

d) There is an edge connecting them.

e) None of the above describes adjacent vertices.

4) A graph in which every edge is connected to every other edge is said to be ___________________ .

a) sparse

b) complete

c) full

d) balanced

e) connected

5) A connected graph has which of the following properties?

a) For any pair of vertices, there is an edge between them.

b) Every vertex is adjacent to every other vertex.

c) No vertex is adjacent to every other vertex.

d) For any pair of vertices, there is a path between them.

e) There exists a vertex that is adjacent to every other vertex.

6) A graph is said to have a(n) ________________, if there exists a path where the first and last vertices are the same, and no edge is repeated.

a) connected component

b) algorithm

c) cycle

d) weight

e) complete component

7) A digraph is a __________________________ .

a) graph in which every cycle contains 2 edges.

b) graph in which every cycle contains 3 edges.

c) graph in which there are no cycles.

d) graph in which there are 2 cycles.

e) directed graph.

8) A graph with integer weights or costs associated with edges is sometimes called a(n) _________________.

a) acyclic graph

b) directed graph

c) network

d) adjacency matrix

e) none of the above

9) A breadth-first traversal of a graph uses which of the following data structures?

a) binary search tree

b) stack

c) queue

d) array

e) none of the above

10) A depth-first traversal of a graph uses which of the following data structures?

a) binary search tree

b) stack

c) queue

d) array

e) none of the above

11) A spanning tree of a graph is a tree with that always has which of the following properties?

a) It includes some of the edges and some of the vertices of the graph.

b) It includes all of the edges and some of the vertices of the graph.

c) It includes some of the edges and all of the vertices of the graph.

d) It includes all of the edges and all of the vertices of the graph.

e) none of the above

12) A(n) ___________________ is a two-dimensional array that can be used to represent a graph.

a) adjacency list

b) adjacency matrix

c) digraph list

d) graph node

e) none of the above

13) A __________________ traversal can be used to determine if a graph is connected.

a) inorder

b) preorder

c) depth-first

d) breadth-first

e) none of the above

14) Consider a digraph with the following vertices and edges:

vertices: A, B, C, D

edges: (A,B), (B,A), (C,D)

Which of the following statements are true?

a) The graph has a cycle

b) The graph is connected

c) The graph is acyclic

d) all of the above are true

e) neither a, b, nor c are true.

15) A(n) _______________________ is one implementation of a graph where the graph is implemented as a linked structure, and each node contains a structure that contains links to all other nodes.

a) adjacency list

b) adjacency matrix

c) digraph list

d) graph node

e) none of the above

1) In an undirected graph, an edge of the form (A, B) is the same as an edge of the form (B, A).

2) A complete graph on n vertices has n(n-1)/2 edges.

3) In order to create a topological ordering of vertices in a directed graph, the graph cannot have a cycle.

4) A network is a type of graph in which there is a cost associated with each edge.

5) A graph is a special kind of tree.

6) A breadth-first traversal uses a stack as a supporting data structure.

7) An adjacency matrix is one approach to implementing a graph that uses a two-dimensional array.

8) A spanning tree of a graph does not necessarily include all of the edges of the graph.

9) A cycle is a path that starts and ends on the same vertex.

10) A minimum spanning tree of a weighted graph is a spanning tree in which the sum of the weights of the edges is less than or equal to the sum of the weights for any other spanning tree for the same graph.

1) Is every tree a graph? Is every graph a tree? Explain.

2) Can a tree ever have a cycle? Explain.

3) What is a complete graph? How many edges are contained in a complete graph on n vertices?

4) Consider the following undirected graph.

vertices: A, B, C, D, E

edges: (A,B),(C,D), (B,D), (B,C)

Is the graph connected?

5) Consider the following undirected, weighted graph:

vertices: Chicago, New York, Boston, Washington

edges: (Chicago, Boston, 159), (Chicago, New York, 129),

(Chicago, Washington, 219), (Boston, New York, 89),

(New York, Washington, 59)

What is the least expensive path between Chicago and Washington?

6) Write out all of the edges in a complete, undirected graph on 4 vertices, where the vertices are labeled A, B, C, and D.

7) Explain how a breadth-first traversal of a graph works.

8) What data structure is used to support a depth-first traversal of a graph?

9) Consider the following undirected graph.

vertices: A, B, C, D, E

edges: (A,B),(C,D), (B,D), (B,C), (C,E), (D,E)

Give a spanning tree for this graph.

10) Consider the following undirected graph.

vertices: A, B, C, D, E

edges: (A,B),(C,D), (B,D), (B,C), (C,E), (D,E)

Write out an adjacency matrix for this graph.

11) What is the maximum number of edges in a directed graph on n vertices? Explain how you arrived at your solution.

12) What is the difference between a spanning tree and a minimum spanning tree?

13) Explain how an adjacency matrix can be used to represent a weighted graph.

14) What does it mean for a graph to be connected?

15) Can an edge be part of more than one cycle in a graph? Explain.