For each of the following two statements, decide whether it is true or false. If
ID: 3620732 • Letter: F
Question
For each of the following two statements, decide whether it is true or false. If It Is true, give a short explanation. If it is false, give a counterexample. Suppose we are given an instance of the Minimum Spanning Tree Problem on a graph C, with edge costs that are all positive and distinct. Let T be a minimum spanning tree for this instance. Now suppose we replace each edge cost ce by its square, c2e. thereby creating a new instance of the problem with the same graph but different costs. True or false? T must still be a minimum spanning tree for this new instance. Suppose we are given an instance of the Shortest s-t Path Problem on a directed graph G. We assume that all edge costs are positive and distinct. Let P be a minimum-cost s-t path for this instance. Now suppose we replace each edge cost ce by its square, c2e, thereby creating a new instance of the problem with the same graph but different costs. True or false? P must still be a minimum-cost s-t path for this new instance.Explanation / Answer
if the costs C2e into Kruskal's algorithm it will sort them in teh same order ? put the same subset of edges in the MST. b) False. let G have edges (a,b),(b,c) and (d,c) where the first 2 edges have cost 6 and the last cost 10.the shortest path is the edge (d,c) but after squaring the costs the shortest path would go through b.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.