# Uses of Strongly Connected Components?

I recently learned about SCCs in directed graphs and how to find them, yet I have no clue what they are useful for.

If you collapse each SCC into a node, you get a new graph that has no cycles. But what - again - is that useful for?

Applications other then in computer science are welcome, too.

-

The strongly connected components of a directed graph identifies those parts (subsets of vertices) of a graph where everybody can reach everybody, so that it can reasonable to think of each of these subsets as a single 'thing'.

So suppose you have a graph with 4 nodes, $a_1,a_2,b_1,b_2$, with edges $a_1\rightarrow a_2$, $a_2\rightarrow a_1$, $a_1\rightarrow b_1$, $b_1\rightarrow b_2$, $b_2\rightarrow b_1$ (that is edges between the $a$'s, edges between the $b$'s and an edge from $a_1$ to $b_1$ (but no other edges).

In this graph, your SCCs are $\{a_1,a_2\}$ and $\{b_1,b_2\}$, and the SCC graph can be represented with two nodes $A\rightarrow B$, where $A$ stands for $\{a_1,a_2\}$ and $B$ stands for $\{b_1,b_2\}$.

The whole idea is that you're collapsing the graph to the essentials, removing redundancy. If you can reach one vertex from another and vice versa, you can treat them as essentially the same vertex. This new graph has no cycles, as you point out, and that might be desired, you might only care when there is no way to get back. Since you may be reducing out many nodes, you may be able to more efficiently find how one vertex is related to another.

More abstractly, this is similar (but not identical) to taking a preorder and finding a partial order that preserves most of the order relationship.

-

Do you mean strongly connected components? There are applications in cell methods for the numerical study of discrete dynamical systems. See for instance these papers:

-
Oh shoot. thanks for the hint – Ronny Brendel Apr 10 '11 at 12:17
mh that's all pretty hardcore. I can't explain well what I expect. Maybe something easier, more abstract. Like for example, in relation to CompSci algorithms or graph properties, or compression of graphs. I don't know. Thanks for your help! – Ronny Brendel Apr 10 '11 at 12:22