27

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!

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Delup
  • 285
  • 1
  • 3
  • 6

3 Answers3

77

A cut of a connected graph is a minimal set of edges whose removal separate the graph into two components (pieces). The minimal cut property says that if one of the edges of the cut has weight smaller than any other edge in the cut then it is in the MST. To see this, assume that there is an MST not containing the edge. If we add the edge to the MST we get a cycle that crosses the cut at least twice, so we can break the cycle by removing the other edge from the MST, thereby making a new tree with smaller weight, thereby contradicting the minimality of the MST.

deinst
  • 18,402
  • 3
  • 47
  • 45
  • 8 years later on this answer and I'm still lost with this. Can you please explain this to me as I was a child? – Alexander Falk Jun 15 '18 at 15:37
  • @AlexanderFalk Where in the explanation are you having trouble? – deinst Jun 16 '18 at 16:37
  • 1
    Sorry, I have two question: (1) Why the 'cut' would cross the newly added edge twice? (2) If the weight of the newly added edge is smaller than the weight of 'other' edge to be removed, then it would still be a MST, why there is a contradiction? – user2994783 Feb 25 '20 at 01:46
  • @user2994783: (1) One of the edges of the MST must already be in ( = "cross") the cut, because otherwise there would be no way to get from vertices on one side of the cut to vertices on the other side, and in an MST you can get from any vertex to any other vertex; after adding the new smaller edge, there are now 2 edges in ( = "crossing") the cut. (2) The contradiction is that *it could not have been* an MST in the first place, since we just reduced its weight. – j_random_hacker Jul 07 '21 at 11:49
  • Does a MST not contain every edge in the cut? – Foobar Feb 23 '22 at 22:17
  • 1
    @Roymunson Assume that we break the graph into two sets with our cut P and Q. Visualize two circles labeled P and Q, and between those two circles you have 4 lines for example representing our cut set. Imagine if two of those lines were included in the minimum spanning tree. Then we could go from P to Q and back to P which makes a cycle. By definition of a tree (which is acyclic), this is not allowed. This means that the edges in the cut set are mutually exclusive. This means we should choose the smallest one (which we can prove by contradiction). – Neel Sandell Mar 30 '22 at 21:02
1

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

LED Fantom
  • 1,229
  • 1
  • 12
  • 32
1

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.

Chaitanya Kiran Gubbala
  • 61
  • 1
  • 4