Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.