CS6515 Exam 2 || 100% Error-free Answers.
If graph G has more than |V | − 1 edges, and there is a unique heaviest edge, then this edge
cannot be part of a minimum spanning tree correct answers False, because the unique heaviest
edge may not be part of a cycle
If G has a cycle with a unique heaviest edge e, then e cannot be part of any MST. correct answers
True, if the unique heaviest edge is part of a cycle then it will be removed first.
Let e be any edge of minimum weight in G. Then e must be part of some MST. correct answers
True, in order create the MST we use the edges with minimum weight.
If the lightest edge in a graph is unique, then it must be part of every MST. correct answers True,
we always choose the lightest edge when building the MST.
If e is part of some MST of G, then it must be a lightest edge across some cut of G. correct
answers True, due to cut property
If G has a cycle with a unique lightest edge e, then e must part of every MST. correct answers
False, lightest edge in a cycle may not be necessary to create an MST because the remaining
edges may be necessary to connect to the other vertices
The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST correct answers
False, the shortest path may not visit all the nodes in the MST tree
The shortest path between two nodes is necessarily an MST correct answers False, the shortest
path between two nodes may not visit all the nodes in that make up an MST
If G contains an r-path from node s to t, then every MST of G must also contain an r-path from
node s to node t.
For any r > 0, an r-path is a path whose edges all have weight < r. correct answers True, if an r-
path exists between s and t then we are guaranteed to get either this path or another r-path with
weight < this r-path in the MST
What is the input for DFS? correct answers Directed or undirected graph
What is the output for DFS? correct answers Pre/post/ccnum
What information can you get from post numbers? correct answers In a directed graph, highest
post numbers are sinks and lowest post numbers are sources
What information can you get from ccnum? correct answers Connected components (undirected)
or SCCs (directed)
What is the input for Explore? correct answers Directed or undirected graph, start vertex v
If graph G has more than |V | − 1 edges, and there is a unique heaviest edge, then this edge
cannot be part of a minimum spanning tree correct answers False, because the unique heaviest
edge may not be part of a cycle
If G has a cycle with a unique heaviest edge e, then e cannot be part of any MST. correct answers
True, if the unique heaviest edge is part of a cycle then it will be removed first.
Let e be any edge of minimum weight in G. Then e must be part of some MST. correct answers
True, in order create the MST we use the edges with minimum weight.
If the lightest edge in a graph is unique, then it must be part of every MST. correct answers True,
we always choose the lightest edge when building the MST.
If e is part of some MST of G, then it must be a lightest edge across some cut of G. correct
answers True, due to cut property
If G has a cycle with a unique lightest edge e, then e must part of every MST. correct answers
False, lightest edge in a cycle may not be necessary to create an MST because the remaining
edges may be necessary to connect to the other vertices
The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST correct answers
False, the shortest path may not visit all the nodes in the MST tree
The shortest path between two nodes is necessarily an MST correct answers False, the shortest
path between two nodes may not visit all the nodes in that make up an MST
If G contains an r-path from node s to t, then every MST of G must also contain an r-path from
node s to node t.
For any r > 0, an r-path is a path whose edges all have weight < r. correct answers True, if an r-
path exists between s and t then we are guaranteed to get either this path or another r-path with
weight < this r-path in the MST
What is the input for DFS? correct answers Directed or undirected graph
What is the output for DFS? correct answers Pre/post/ccnum
What information can you get from post numbers? correct answers In a directed graph, highest
post numbers are sinks and lowest post numbers are sources
What information can you get from ccnum? correct answers Connected components (undirected)
or SCCs (directed)
What is the input for Explore? correct answers Directed or undirected graph, start vertex v
