Generating forests from a graph?
I'm unable to fully understand how a graph could have many forests. I understand that a forest is a graph that has no circuits. So basically what I understood is that we call a graph a forest if it is not connected and it contains no circuits. But then how to generate a forest from a graph?? Do we make a tree for each connected component? If so, do we then call all the generated trees as the forest of the graph OR the forests of the graph?
$\endgroup$ 12 Answers
$\begingroup$Graphs usually have many forests as subgraphs. How to make them? Delete some vertices and/or edges: if there's no cycles, it's a forest.
For example, this disconnected graph
has the forests
(which happens to have a spanning tree in each connected component) and
as subgraphs. [In fact, the two subgraphs above happen to be spanning forests (in the sense that the forest and the original graph have the same vertex set). However, it can also be useful to define "spanning forest" to mean having a spanning tree in each connected component.]
It contains non-spanning forests, such as
and it even contains forests without any edges, such as
and
You can consider K forest where K represents number of sources in the graph. In case you have just one source, you can generate 1-forest or forest with one tree. In case you have 5 sources in the graph. Each of the 5 trees in the 5 forest would have one source. No two sources are connected and there is no cycle or loop. Consider it as a set of Octopus trying to capture food kept at nodes of a graph by sending its arms along the edges. The rule of game is that all food should be consumed while each node can have exactly one arm incident at the node Got it now ? Have a look at 's_theorem this work is also applicable in case of multiple sources, namely K > 1. Google it and help yourself
Nitin Bhagat
$\endgroup$ 1
