A minimum spanning tree minimizes total edge weight among spanning trees of a connected weighted graph. It can be computed in polynomial time by repeatedly adding the least-weight edge joining two current components. The cut-exchange argument preserves the existence of an optimum containing every accepted edge. Removing an edge of a travelling-salesman tour gives a spanning tree, so its optimum is a lower bound on optimal tour cost.
Articles by others on the same topic
A Minimum Spanning Tree (MST) is a subset of the edges of a weighted, undirected graph that connects all the vertices together without any cycles and with the minimal possible total edge weight. In other words, it is a tree that includes all the vertices of the graph, has the least total weight among all possible spanning trees, and contains no closed loops. ### Key Characteristics of a Minimum Spanning Tree: 1. **Connected**: An MST connects all vertices in the graph.