Deck 12: Graphs

Question 1

In a connected graph, there must be an edge from each vertex to every other vertex.

Answer 1

False

Question 2

A a depth-first traversal cannot be implemented recursively.

Answer 2

False

Question 3

A simple path in a graph is one in which a path passes through the same vertex at least twice.

Answer 3

False

Question 4

A graph is a set of edges and vertices such that each edge connects two vertices.

Question 5

The adjacency matrix representation of a graph stores graph information in an array of lists.

Question 6

In a DAG, there are no cycles.

Question 7

In a digraph, each edge has a source vertex and destination vertex.

Question 8

Repeated application of finding the minimum spanning tree for all the components in a graph yields a minimum spanning forest for a graph.

Question 9

A spanning tree has the fewest number of edges possible while still retaining a connection between all the vertices in the component.

Question 10

When you traverse a graph, there is always a single direct link from one item to any other item.

Question 11

Dijkstra's algorithm consists of two steps: the initialization step and the execution step.

Question 12

To find the shortest path, you can use a wighted graph and sum the edge of the weights between two vertices.

Question 13

In an undirected graph, two or more edges connect the same pair of vertices.

Question 14

The depth-first traversal of a graph uses a queue as the collection in the generic algorithm.

Question 15

In a complete graph with six vertices, the degree of a vertex is five.

Question 16

In an adjacency matrix, a 1 is used to represent an edge between two vertices.

Question 17

A topological order assigns a rank to each edge such that the vertices go from lower-to higher-ranked edges.

Question 18

On a weighted graph, the vertices are labeled with numbers.

Question 19

The adjacency list supports finding all the vertices adjacent to a given vertex more efficiently than the adjacency matrix.

Question 20

An example of a process or model that can be graphed is the links between pages on the Internet.

Question 21

In a complete undirected graph consisting of 3 vertices, how many total adjacencies will there be?

A) 2
B) 6
C) 9
D) 4

Question 22

Which of the following is NOT a process for which a graph can serve as a model?

A) a road map between hotels a town
B) a line at a movie theater
C) the paths that data can travel in a network
D) the routes between rooms in a building

Question 23

Which of the following is true about graphs?

A) graphs consist of vertices and nodes
B) the edges between vertices are always labeled
C) an adjacency is when one vertex has a path to another vertex
D) the length of a path is the number of edges on the path

Question 24

All graphs, except weighted graphs, are collections of vertices connected by edges.

Question 25

In Python, you need to define infinity as a long integer.

Question 26

Which term best describes a neighbor?

A) a path exist between vertices
B) a vertex is reachable from another vertex
C) two vertices have consecutive labels
D) two vertices are adjacent

Question 27

What are edges called that emanate from a given source vertex?

A) incident edges
B) directed edges
C) destination edges
D) cyclical edges

Question 28

The number of edges connected to a vertex describes which of the following?

A) a complete graph
B) the neighbor of a vertex
C) the degree of a vertex
D) whether a graph is connected

Question 29

In the implementation of a graph, the len function returns the number of the graph's vertices.

Question 30

In a breadth-first traversal of a graph, what type of collection is used in the generic algorithm?

A) queue
B) set
C) stack
D) heap

Question 31

A graph has a single length attribute, similar to the lists, queues, and stacks.

Question 32

In graph terms, what is a path that begins and ends at the same vertex?

A) a simple path
B) an undirected path
C) a cycle
D) a directed path

Question 33

In a complete undirected graph with five vertices how many cells will contain a value of 1 in an adjacency matrix?

A) 15
B) 10
C) 25
D) 125

Question 34

Which of the following is true about an undirected graph?

A) a graph-processing algorithm can move in only one direction along an edge that connects two vertices
B) their edges do not indicate direction
C) there can be multiple edges connecting any two vertices
D) there is a source vertex and a destination vertex

Question 35

What makes a graph complete?

A) when there is an edge from each vertex to all other vertices
B) when there is a path from each vertex to all other vertices
C) when there is a path between at least half the vertices
D) when there are two or more edges between vertices

Question 36

Which of the following is true about graph traversals?

A) a single path to each item is assumed
B) all algorithms are nonrecursive
C) the algorithm should find the shortest path to a given item
D) the type of collection used is irrelevant to the traversal algorithm

Question 37

If vertex Penguins can reach vertex Capitals and vertex Capitals can reach vertex Islanders, but none of them can reach vertices Sharks or Ducks, what can you say about the set of vertices Penguins, Capitals, and Islanders?

A) the set is a connected component
B) the set describes a complete graph
C) the vertices in the set are all adjacent to each other
D) the set describes a connected graph

Question 38

Removing a vertex also entails removing any edges connecting it to other vertices.

Question 39

What is the performance behavior of a linked adjacency list for determining whether an edge exists between two vertices?

A) constant time
B) O( N ²) where N is the number of vertices
C) linear with the length of the list
D) logarithmic with the total number of vertices

Question 40

Which of the following is NOT true about an adjacency matrix?

A) it stores information about the graph in a grid
B) the grid cell contains a 0 if there is no edge between vertices
C) a graph with four vertices contains 16 cells
D) it can be represented by an array of lists

Question 41

Which of the following is NOT true after the initialization step in Dijkstra's algorithm?

A) the cells in the included list are all False, except for the cell that corresponds to the row of the source vertex in the results grid
B) the distance in a row's distance cell is either 0, infinity, or a positive number
C) the shortest path from the source to a vertex is found and the vertex's cell is marked in the included list
D) the vertex in a row's parent cell is either the source vertex or undefined

Question 42

What is the output of Dijkstra's algorithm?

A) a three-dimensional array
B) a two-dimensional grid
C) a source vertex
D) the number of vertices in the graph

Question 43

What can be described as the assignment of a rank to each vertex in a graph such that the edges go from lower-to higher-ranked vertices?

A) directed acyclic graph
B) sparse graph
C) topological order
D) shortest-path problem

Question 44

In the following code to add an edge in the LinkedDirectedGraph class, what is the missing code? def addEdge(self, fromLabel, toLabel, weight):
FromVertex = self.getVertex(fromLabel)
< missing code >
FromVertex.addEdgeTo(toVertex, weight)
Self.edgeCount += 1

A) self.getVertex(toLabel) = fromVertex
B) fromVertex.addEdgeTo(fromVertex, weight)
C) self.weight += 1
D) toVertex = self.getVertex(toLabel)

Question 45

In a component with n vertices, how many edges are in the spanning tree?

A) n
B) n ²
C) n + 1
D) n - 1

Question 46

In the __init__ method code for the LinkedVertex class, what is the missing code? def __init__(self, label):
Self.label = label
Self.edgeList = list()
< missing code >

A) self.size += 1
B) self.mark = False
C) return iter(result)
D) result = self.label

Question 47

What is the minimum sum of all weights in a spanning tree of a weighted graph?

A) spanning forest
B) minimum spanning tree
C) shortest path spanning tree
D) topological spanning tree

Question 48

In the LinkedDirectedGraph class, which of the following methods is an iterator?

A) incidentEdges
B) getEdge
C) containsEdge
D) sizeEdges

Question 49

The smallest sum of edge weights between two vertices describes which of the following?

A) the shortest path
B) topological order
C) topological sort
D) maximum spanning tree

Question 50

In the pseudocode for the dfs function for partitioning the vertices in a graph into disjointed components, what is the missing pseudocode statement? dfs(graph, v, s):
Mark v as visited
S.add(v)
For each vertex, w, adjacent to v:
If w is unvisited:

A) s.add(w)
B) dfs(graph, v, s)
C) s.add(v)
D) dfs(graph, w, s)