Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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:

share|improve this answer
    
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
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.