Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
You've been asking a lot of graph theory questions tonight. Are you working through a book? It might be more productive for you to think about it more yourself and come back with a condensed list of questions. –  Ian Coley Feb 5 at 11:05

2 Answers 2

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

enter image description here

has the forests

enter image description here

(which happens to have a spanning tree in each connected component) and

enter image description here

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

enter image description here

and it even contains forests without any edges, such as

enter image description here

and

enter image description here

share|improve this answer

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 http://en.wikipedia.org/wiki/Kirchhoff's_theorem this work is also applicable in case of multiple sources, namely K > 1. Google it and help yourself

Nitin Bhagat

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.