What is the difference between a forest and a spanning forest?

4.8k Views Asked by At

If a graph is labelled as a forest it does not contain any cycles, meaning it consists of all trees, which I realize can even be a single node (since that is technically a tree).

If a graph is labelled as a spanning forest, it is a forest that contains every vertex of G such that two vertices are in the same tree of the forest when there is a path in G between these two vertices.

Aren't these basically the exact same? I am having a bit of trouble telling the difference between the two.

2

There are 2 best solutions below

6
On BEST ANSWER

So suppose I have three disjoint sets of vertices: $\{v_{1}\} \cup \{v_{2}\} \cup V(C_{3})$. Here, $\{v_{1} \} \cup \{v_{2}\}$ is a forest which does not span, while $\{v_{1}\} \cup \{v_{2}\} \cup (C_{3} - e)$ is a spanning forest, for $e \in E(C_{3})$.

0
On

A forest is subset of undirected graph and is a collection of trees across its connected components.

A spanning forest is subset of undirected graph and is a collection of spanning trees across its connected components.

To clarify, lets use a simple example. Say we have an undirected graph A that has two acyclic components ( spanning tree A1, and spanning tree A2) and one cyclic component A3. In this case collection of A1 and A2 will comprise a spanning forest.

If we make a modification to component A3 and make it acyclic(i.e. it will become a spanning tree ) then we can have a spanning forest comprising of the collection of A1, A2 and A3