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?
4
-
1$\begingroup$ 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.$ $\endgroup$– Igor RivinOct 10, 2011 at 11:05
-
$\begingroup$ Moreover, as long as $e \leq \binom{n}{2}$, this bound is best possible, as your graph could always be acyclic. $\endgroup$– David E SpeyerOct 10, 2011 at 13:37
-
$\begingroup$ 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. $\endgroup$– Klaus DraegerOct 10, 2011 at 13:50
-
$\begingroup$ Sorry, cannot edit my comment - that should of course be $n(n-1) + m(m+1)\geq 2e$. $\endgroup$– Klaus DraegerOct 10, 2011 at 15:17
Add a comment
|