Questions Chapter 13

Question 1

Graphs consist of _______ connected by _______

Answer 1

vertices connected by edges

Question 2

The two main search algorithms of a graph are:

Answer 2

depth-first search (dfs) and breadth-first search (bfs)

Question 3

The depth-first search algorithm can be based on a _______; the breadth-first search algorithm can be based on a _______.

Answer 3

dfs based on a stack; bfs based on a queue

Question 4

How do you tell, by looking at its adjacency matrix, how many edges there are in an undirected graph?

Answer 4

count number of 1s and divide by 2 (assuming the identity diagonal is all 0s)

Question 5

In a game simulation, what graph entity corresponds to a choice about what move to make?

Answer 5

node

Question 6

The weight in a weighted graph is a property of the graph’s _________

Answer 6

edges

Question 7

True or False: The shortest-path problem (SPP) must be carried out on a directed graph

Answer 7

False

Question 8

Dijkstra’s algorithm finds the shortest path:

a. from one specified vertex to all other vertices
b. from one specified vertex to another specified vertex
c. from all vertices to all other vertices that can be reached along one edge
d. from all vertices to all other vertices that can be reached along multiple edges

Answer 8

a. from one specified vertex to all other vertices

Question 9

True or False: The rule in Dijkstra’s algorithm is to always put in the tree the vertex that is closest to the starting vertex

Answer 9

True

Question 10

In the railroad fares example of a weighted graph, a fringe town is one

a. to which the distance is known, but from which no distances are known
b. which is in the tree
c. to which the distance is known and which is in the tree
d. which is completely unknown

Answer 10

a. to which the distance is known, but from which no distances are known

Question 11

The all-pairs shortest-path problem involves finding the shortest path

a. from the starting vertex to every other vertex
b. from every vertex to every other vertex
c. from the starting vertex to every vertex that is one edge away
d. from every vertex to every other vertex that is one or more edges away

Answer 11

b. from every vertex to every other vertex

Question 12

The shortest-path problem for weighted graphs involves finding the ________ number of ______ between two ______.

Answer 12

minimum number of edges between two vertices.