4.5. The Minimum Spanning Tree Problem

A Spanning Tree is a tree that spans all the nodes in a graph

Given a connected graph G = (V, E) with positive edge weights c_e, a Minimum Spanning Tree is a subset of the edges T ⊆ E such that T is a spanning tree whose sum of edge weights is minimized.