What is a minimum spanning forest? [closed]

Question

A minimum spanning tree gives the cheapest way an undirected graph. But what is a minimum spanning forest? Is it defined for connected graphs or unconnected graphs?

Ousley

Answer 1

Minimum spanning forest is a generalization of minimum spanning tree for unconnected graphs. For every component of the graph, take its MST and the resulting collection is a minimum spanning forest.

Splice

Excuse me, but I am not sure about what you are saying. If you have a minimum spanning forest, aka a subset of the vertices such that every vertex has at least an adjacent edge in the forest, then it will almost never match your definition which leads to a far bigger forest. – Tahoe

@Tahoe are you saying that forest is a subset of vertices? That just doesn't make sense – Splice

A minimal subset of vertices IS a forest, since it is a graph without cycle. I am not saying your definition is false, just that it could be defined in an other way. – Tahoe

That would be a forest, but by no means a spanning one. Where there's a path in the (disconnected) graph, there must be one in the spanning forest as well. The wording of the definition may of course differ, but the essence won't. – Splice

From the definition, I assume that the minimum spanning forest does not contain the isolated vertices of the graph, which are not connected to any other vertices? – Gourmet

There are two competing definitions. A spanning forest is either (1) a forest which is a subgraph retaining all vertices (as Labo says), or (2) a forest which is a subgraph consisting of a spanning tree for each component (as voidengine says). Definition (1) is more common in maths. This may be confusing, but remember that "spanning" really just means "subgraph retaining all vertices", and makes no guarantee about which nodes remain connected. The only reason a spanning tree retains connectivity is that otherwise it wouldn't be a tree anymore. Also, minimum just means smallest sum of weights. – Piscatory