Questions Chapter 13 Flashcards

1
Q

Graphs consist of _______ connected by _______

A

vertices connected by edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

The two main search algorithms of a graph are:

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

dfs based on a stack; bfs based on a queue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

a. from one specified vertex to all other vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

b. from every vertex to every other vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

minimum number of edges between two vertices.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly