Cs 6515 Exam 2 Final Paper Verified Questions Accurate Solutions.pdf 1. Document Information

CS 6515 EXAM 2 FINAL PAPER VERIFIED QUESTIONS ACCURATE SOLUTIONS




Question:
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:
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:
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:
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:
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:
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:
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:
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:
What is the input for DFS?

Answer:
Directed or undirected graph



Question: