0

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?

flag
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 2011 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 2011 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 2011 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 2011 at 15:17

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.