Given a connected Graph $G(V,E)$ with $weight:E\rightarrow R^+$ and $d\in N$.How can I find the minimum spanning forest that has at most $d$ trees?
I was thinking of running a simple MST algorithm (Prim or Kruskal). But I was thinking of a case that contradict it: for example if $d > 1$ than I can cut the MST into two diffrent trees by removing the most expensive edge in a graph and crate a better minimum spanning forest.
Construct MST, then remove the $d-1$ most expensive edges. (Or, if using Kruskal, halt the algorithm when there are $d$ connected components)
Why this works: assume, for the sake of contradiction, that there is a spanning forest of $d$ trees with less total weight. Consider the graph $G'$ whose vertices are $V$ and whose edges are the union of the edges of that optimal forest with the edges of the MST of $G$. Consider a MST of $G'$: its total weight less than or equal the total weight of the optimal forest and the $d-1$ most expensive edges of the MST of $G$. But our original minimal spanning tree of $G$ had total weight equal to the weight of its $d-1$ most expensive edges plus the total weight of our non-optimal forest. Therefore, our MST of $G'$ has less total weight than a MST of $G$, but since any spanning tree of $G'$ is also a spanning tree of $G$ that is a contradiction with the minimality of the MST.