4
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ A spanning forest is a subgraph of a given graph. For example if $G$ is a cycle of three vertices and three edges then it is not a forest. But you get its spanning tree by removing any one of the edges, as the graph is still connected after the removal, and it became a forest (a tree actually) as a consequence of the removal. $\endgroup$
    – Jyrki Lahtonen
    Commented Apr 7, 2014 at 5:56
  • $\begingroup$ @JyrkiLahtonen, yes exactly. A forest is a particuar kind of graph; a spanning forest is particular kind of subgraph. $\endgroup$
    – goblin GONE
    Commented Apr 7, 2014 at 5:58
  • 1
    $\begingroup$ Thank you. I think I get it now. Just to confirm... so a spanning forest is a forest of spanning trees in the subgraph of G? $\endgroup$
    – user3451821
    Commented Apr 7, 2014 at 6:08
  • $\begingroup$ Almost. The connectivity components of a spanning tree must be equal to those of the original graph. So a method of producing all the spanning trees of a given graph $G$ is to first identify all the connectivity components of $G$, then find the spanning trees of those components, and then put them together to a spanning forest (one tree per each component). $\endgroup$
    – Jyrki Lahtonen
    Commented Apr 7, 2014 at 6:54
  • $\begingroup$ I don't see how all connected components are trees? Isn't something like a square (4 vertices, 4 edges) a connected component of graph G? Yet it is not a tree? $\endgroup$
    – user3451821
    Commented Apr 7, 2014 at 9:07

2 Answers 2

Reset to default
2
$\begingroup$

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})$.

$\endgroup$
6
  • 2
    $\begingroup$ I am not a very mathy person sorry. Could you put that in words? :S $\endgroup$
    – user3451821
    Commented Apr 7, 2014 at 5:52
  • $\begingroup$ If I give you two points and a triangle, the two points from a forest. However, if I remove an edge from the triangle, the entire graph becomes a spanning forest. $\endgroup$
    – ml0105
    Commented Apr 7, 2014 at 6:12
  • $\begingroup$ Sorry I don't really understand what you mean by two points and a triangle. By that do you mean 2 isolated points and than 3 more points (vertices) forming a triangle (which has a cycle, so not a tree)? Sorry, thank you $\endgroup$
    – user3451821
    Commented Apr 7, 2014 at 6:28
  • $\begingroup$ Yes. The two isolated points from a forest. And if I remove an edge from the triangle and include the isolated points, that is a spanning forest. To note as well- triangle is a pretty standard name for the graph $C_{3}$. $\endgroup$
    – ml0105
    Commented Apr 7, 2014 at 6:43
  • $\begingroup$ Ok. I think I am starting to get it. In your example, where you start with 2 isolated points and a triangle consisting of 3 nodes which is a cycle, would the number of trees in the spanning forest be 1? If the number of trees in the spanning forest is equal to the number of connected components in the original graph G, that would mean that triangle is the only thing that follows that? Since the 2 original isolated points were not connected components? $\endgroup$
    – user3451821
    Commented Apr 7, 2014 at 7:34
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .