CS6515 EXAM 2 UPDATED ACTUAL QUESTIONS AND CORRECT ANSWERS

CS6515 EXAM 2 UPDATED ACTUAL QUESTIONS AND
CORRECT ANSWERS

Question:
1. 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
Answer:
False, because the unique heaviest edge may not be part of a cycle

Question:
2. If G has a cycle with a unique heaviest edge e, then e cannot be part of any MST.
Answer:
True, if the unique heaviest edge is part of a cycle then it will be removed first.

Question:
3. Let e be any edge of minimum weight in G. Then e must be part of some MST.
Answer:
True, in order create the MST we use the edges with minimum weight.

Question:
4. If the lightest edge in a graph is unique, then it must be part of every MST.
Answer:
True, we always choose the lightest edge when building the MST.

Question:
5. If e is part of some MST of G, then it must be a lightest edge across some cut of G.
Answer:
True, due to cut property

Question:
6. If G has a cycle with a unique lightest edge e, then e must part of every MST.
Answer:
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

Question:
7. The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST
Answer:
False, the shortest path may not visit all the nodes in the MST tree

Question:
8. The shortest path between two nodes is necessarily an MST
Answer:
False, the shortest path between two nodes may not visit all the nodes in that make up an MST

, Question:
9. 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.
Answer:
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

Question:
10. What is the input for DFS?
Answer:
Directed or undirected graph

Question:
11. What is the output for DFS?
Answer:
Pre/post/ccnum

Question:
12. What information can you get from post numbers?
Answer:
In a directed graph, highest post numbers are sinks and lowest post numbers are sources

Question:
13. What information can you get from ccnum?
Answer:
Connected components (undirected) or SCCs (directed)

Question:
14. What is the input for Explore?
Answer:
Directed or undirected graph, start vertex v

Question:
15. What is the output for Explore?
Answer:
Pre/post/ccnum visited

Question:
16. What is the runtime for DFS?
Answer:
O(n+m)

Question:
17. What is the runtime for Explore?
Answer:
O(n+m)