Page 1 of 1
Consider a graph G, where each of the edges have different weights. Let T₁ be the minimum-weight spanning tree produced
Posted: Sun Jul 03, 2022 11:23 am
by answerhappygod
- Consider A Graph G Where Each Of The Edges Have Different Weights Let T Be The Minimum Weight Spanning Tree Produced 1 (48.36 KiB) Viewed 22 times
Consider a graph G, where each of the edges have different weights. Let T₁ be the minimum-weight spanning tree produced by Kruskal's Algorithm, and let T2 be the minimum-weight spanning tree produced by Prim's Algorithm. I claim that T₁ and T₂ must be identical spanning trees - i.e., the exact same set of edges must appear in both trees. Determine whether this claim is TRUE or FALSE. If your answer is TRUE, see if you can figure out why the claim is true. If your answer is FALSE, see if you can come up with a counterexample.