I've been spending a lot of time reading online presentations and textbooks about the cut property of a minimum spanning tree. I don't really get what it's suppose to illustrate or even why it's practical. Supposedly it helps determine what edges to add to a MST, but I fail to see how it accomplishes that. My understanding of the cut property so far is that you split a MST into two arbitrary subsets. Any help here? Thanks!
3 Answers
There's another property up on which this explanation is based.
"For any of the cut, if there are even number of edges crossing the cut then there must be a cycle crossing the cut"
Because MST does not contain any cycle there won't be any even number of edges crossing the cut.
Proof by contradiction: Assume that there's a MST not containing edge with min weight "e". If we add the edge "e" to the MST we get a cycle crossing the cut at least twice. We can remove other edge with more weight and break the cycle which results in an ST containing lesser weighing edge "e". This is in contradiction with the assumption.
I'd like to share what I understand about Cut Property to help. If there're anything to improve in my post, please comment below so I can modify my answer.
Background:
For simplification, suppose there are 2 separate MSTs (T1 and T2) formed in a graph G(V, E). There are edges not yet connected between T1 and T2.
Goal:
We want to show that when T1 and T2 are connected, a newly produced tree is also an MST - an optimal solution.
>> My Understanding of Cut Property:
Among the edges not yet connected between T1 and T2, pick the lightest edge. Adding it to connect T1 and T2 makes a new MST - an optimal solution.
Note: Connecting an edge in the same tree introduces a cycle. But a tree shouldn't contain a cycle
Related