Chapter 7 Flashcards
In a directed graph, what does the term “out-degree” of a vertex represent?
a) The total number of edges in the graph
b) The number of edges directed away from the vertex
c) The number of edges directed towards the vertex
d) The number of vertices connected to the graph
b) The number of edges directed away from the vertex
Which of the following is true for a directed graph?
a) Every edge has an associated direction.
b) It cannot have cycles.
c) It is always connected.
d) It is equivalent to an undirected graph.
a) Every edge has an associated direction.
What does the (i, j) entry in an adjacency matrix of a graph represent?
a) The degree of vertex i
b) The presence or absence of an edge between vertices i and j
c) The weight of the edge between i and j
d) The total number of edges in the graph
b) The presence or absence of an edge between vertices i and j
What is the value of a_ij in the adjacency matrix of an undirected graph?
a) 1 if there is an edge between i and j; 0 otherwise
b) The weight of the edge between i and j
c) Sum of the degrees of i and j
d) The number of cycles in the graph involving i and j
a) 1 if there is an edge between i and j; 0 otherwise
The reachability matrix of a directed graph tells us:
a) The shortest path between any two vertices
b) Which vertices can be reached from a given vertex
c) The in-degree of all vertices in the graph
d) The minimum spanning tree of the graph
b) Which vertices can be reached from a given vertex
How is the reachability matrix derived from the adjacency matrix?
a) By multiplying the adjacency matrix by itself until no changes occur
b) By subtracting the adjacency matrix from the identity matrix
c) By transposing the adjacency matrix
d) By inverting the adjacency matrix
a) By multiplying the adjacency matrix by itself until no changes occur
Warshall’s Algorithm is used to compute:
a) The shortest path between vertices
b) The transitive closure of a graph
c) The minimum spanning tree
d) The maximum flow in a network
b) The transitive closure of a graph
A graph has an Euler path if and only if:
a) Every vertex has an even degree
b) Exactly two vertices have an odd degree
c) All vertices have an odd degree
d) All vertices are connected
b) Exactly two vertices have an odd degree
A Hamiltonian Circuit in a graph is:
a) A cycle that visits every vertex exactly once
b) A path that visits every vertex exactly once
c) A cycle that uses every edge exactly once
d) A path that uses every edge exactly once
a) A cycle that visits every vertex exactly once
Dijkstra’s Algorithm is used to find:
a) The shortest path from one vertex to all other vertices
b) The minimum spanning tree of the graph
c) All possible paths between two vertices
d) The transitive closure of a graph
a) The shortest path from one vertex to all other vertices
What is the time complexity of Dijkstra’s Algorithm using a priority queue for a graph with n vertices and m edges?
Depth-First Search is most commonly implemented using:
a) A queue
b) A stack
c) A priority queue
d) A linked list
b) A stack
DFS is particularly useful for finding:
a) The shortest path in a graph
b) Cycles in a graph
c) The minimum spanning tree
d) The reachability matrix
b) Cycles in a graph
Breadth-First Search is most commonly implemented using:
a) A queue
b) A stack
c) A priority queue
d) A linked list
a) A queue
BFS is particularly useful for finding:
a) The shortest path in an unweighted graph
b) The shortest path in a weighted graph
c) The minimum spanning tree
d) All simple cycles in a graph
a) The shortest path in an unweighted graph
