Minimal Spanning Tree

This lecture introduces the concept of a weighted graph where each edge is assigned a numerical weight, defining the weight of a graph as the sum of weights of all its edges. The problem of finding a minimum weight spanning tree for a given weighted connected graph is addressed using the Greedy algorithm (or Kruskal's algorithm). The correctness of Kruskal's algorithm is discussed, showing that the resulting graph contains all vertices of the original graph and has no cycles. The process of adding edges to the spanning tree to ensure minimal weight is explained, along with the comparison of different spanning trees based on their weights. The lecture concludes with a detailed explanation of the algorithm's iterative procedure to obtain the minimal spanning tree.