CS6515 Study Guide Questions with Verified
Correct 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
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.
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.
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.
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.
True, due to cut property
If G has a cycle with a unique lightest edge e, then e must part of every MST.
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
False, the shortest path may not visit all the nodes in the MST tree
The shortest path between two nodes is necessarily an MST
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.
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?
Directed or undirected graph
What is the output for DFS?
Pre/post/ccnum
What information can you get from post numbers?
In a directed graph, highest post numbers are sinks and lowest post numbers are sources
What information can you get from ccnum?
Connected components (undirected) or SCCs (directed)
What is the input for Explore?
Directed or undirected graph, start vertex v
What is the output for Explore?
Pre/post/ccnum
visited
What is the runtime for DFS?
O(n+m)
What is the runtime for Explore?
Correct 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
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.
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.
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.
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.
True, due to cut property
If G has a cycle with a unique lightest edge e, then e must part of every MST.
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
False, the shortest path may not visit all the nodes in the MST tree
The shortest path between two nodes is necessarily an MST
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.
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?
Directed or undirected graph
What is the output for DFS?
Pre/post/ccnum
What information can you get from post numbers?
In a directed graph, highest post numbers are sinks and lowest post numbers are sources
What information can you get from ccnum?
Connected components (undirected) or SCCs (directed)
What is the input for Explore?
Directed or undirected graph, start vertex v
What is the output for Explore?
Pre/post/ccnum
visited
What is the runtime for DFS?
O(n+m)
What is the runtime for Explore?
