Question

Variation on MST-finding Algorithms

Recall Kruskal's and Prim's algorithms we studied in class. Consider a similar algorithm that works as follows.
Given an undirected graph G = (V,E):
0. T all edges in E
1. L = edges sorted in non-increasing order by weight
2. for each (u, v) in L:
3. T' T (u, v)
:
4. if T' is connected:
5.
T = T'
6. return T
Prove, with the same level of rigour as in our lecture proofs, that this algorithm produces a MST, or show that
it does not.

Answer 1

The algorithm described is a variation of Prim's algorithm that produces a minimal spanning tree. The algorithm works by iteratively adding the edge with the highest weight that connects a vertex in the tree to a vertex outside the tree. The correctness of the algorithm can be proven by showing that the trees generated at each step are connected and that the final tree is a spanning tree with minimal weight.

Step-by-step explanation:

The algorithm described is actually a variation of Prim's algorithm, not Kruskal's algorithm. This algorithm works by starting with a tree containing a single vertex and then iteratively adding the edge with the highest weight that connects a vertex in the tree to a vertex outside the tree. The algorithm stops when all vertices are included in the tree, resulting in a minimum spanning tree (MST).

To prove the correctness of this algorithm, we need to show two things: (1) the trees generated at each step are always connected, and (2) the final tree is a spanning tree with minimal weight.

For (1), we can prove that the trees generated at each step are connected by contradiction. Suppose there exists a step where the tree generated is not connected. This means there must exist a vertex v outside the tree such that all edges connecting v to the tree have already been considered.

For (2), we can prove that the final tree is a spanning tree with minimal weight by contradiction as well. Suppose there exists a spanning tree T' with a weight less than T (the final tree generated by the algorithm). This means there must exist an edge (u, v) in T but not in T'. Since (u, v) was part of L and the algorithm considers edges in non-increasing order of weight, (u, v) would have been considered in one of the steps, and since T' is connected, the algorithm would have included it in the tree.