Question

In the correctness proof of Kruskal's algorithm (taught in lecture), an important step is to show the greedy choice of the algorithm leads to an optimal solution. In order to show this, an induction is performed. The algorithm progressively adds more edges to the final solution. Assume by certain point, the algorithm has selected and added a few edges to T, T CT*, where T* is an assumed minimum spanning tree. Now the algorithm selects an edge e=(x,y) based its greedy choice. We need to show T is still a part of a minimum spanning tree. Which of the following statement is true? A. e is a minimum weight edge in T. OB.e is a minimum weight edge in T*. OC. Let T'= TU{e}, T' I* must be true. OD. Let T= TU{e}, T'CT* may not be true. E. Let T= TU{e}, T'may not be a part of a minimum spanning tree.

Answer 1

The correct option is B because the slected edge should have the minimum weight for every T in order to be minimum spanning tree.