Minimum Spanning Tree algorithm with n connected components

26 Views Asked by At

During the process of Kruskal, the number of connected components in the graph decreases by 1 each time we add an edge. Let's say during the running of Kruskal, there are 3 connected components and there are a bunch of edges Kruskal picks. Is it true that the sum of these edges is also the minimum number we can get for forming any possible 3 connected components on the graph?

How to prove/disprove this?

0

There are 0 best solutions below