MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hey,

given $G = (V,E)$ a directed Graph. Is there any way to calculate the maximum number of strongly connected components $k$, only based on $n$ nodes and $e$ edges?

share|cite|improve this question
1  
I do not understand the question. You want to have an upper bound for the number of strongly connected components for all graphs with $n$ vertices and $e$ edges? Such a bound is certainly provided by $n.$ – Igor Rivin Oct 10 '11 at 11:05
    
Moreover, as long as $e \leq \binom{n}{2}$, this bound is best possible, as your graph could always be acyclic. – David Speyer Oct 10 '11 at 13:37
    
If $e$ is greater than that, you can still get up to $n-m$ SCCs, where $m$ is the least integer such that $n(n-1)+m(m+1)\leq 2e$, by starting with the maximal acyclic graph and adding all back edges into a single SCC of minimal size. – Klaus Draeger Oct 10 '11 at 13:50
    
Sorry, cannot edit my comment - that should of course be $n(n-1) + m(m+1)\geq 2e$. – Klaus Draeger Oct 10 '11 at 15:17

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.