25.1 MSTs and Cut Property
Last updated
Last updated
Before we dive into the chapter, let's hear a couple words from Professor Hug on MSTs
A minimum spanning tree (MST) is the lightest set of edges in a graph possible such that all the vertices are connected. Because it is a tree, it must be connected and acyclic. And it is called "spanning" since all vertices are included.
In this chapter, we will look at two algorithms that will help us find a MST from a graph.
Before we do that, let's introduce ourselves to the Cut Property, which is a tool that is useful for finding MSTs.
We can define a cut as an assignment of a graph’s nodes to two non-empty sets (i.e. we assign every node to either set number one or set number two).
We can define a crossing edge as an edge which connects a node from one set to a node from the other set.
With these two definitions, we can understand the Cut Property; given any cut, the minimum weight crossing edge is in the MST.
The proof for the cut property is as follows: Suppose (for the sake of contradiction) that the minimum crossing edge e were not in the MST. Since it is not a part of the MST, if we add that edge, a cycle will be created. Because there is a cycle, this implies that some other edge f must also be a crossing edge (for a cycle, if e crosses from one set to another, there must be another edge that crosses back over to the first set). Thus, we can remove f and keep e, and this will give us a lower weight spanning tree. But this is a contradiction because we supposedly started with a MST, but now we have a collection of edges which is a spanning tree but that weighs less, thus the original MST was not actually minimal. As a result, the cut property must hold.
