2
$\begingroup$

Let's have a standard topological ordering algorithm (from CLRS):

Topological_ordering(G)
    foreach vertex v in V do
        v.color = white
    
    for each vertex v in V do
        if v.color = white then
            Stack = DFS(G, v, Stack)
    return Stack

// DFS

DFS (G, v, Stack)
    v.color = gray
    for each u adjacent of v do
        if u.color = white then
            Stack = DFS(G, u, Stack)
    v.color = black
    Stack.push(v)
    return Stack

Now let's apply this to a cyclic graph G.

We will not have a topological ordering of the vertices of G, but we shall have a topological ordering of the graph of the Strongly Connected Components

The graph of the Strongly Connnected Components derived from the graph G is a graph in which each SCC is represented by only one vertex (also called compressed SCC graph or supergraph)

Example

For example let's look at this graph: https://imgur.com/a/0EXOxJt (sorry for the poor drawing skills). In green the SSC of this graph.

Applying the algorithm above, one possible stack configuration is:

head ----> 2 ; 3 ; 4 ; 5 ; 1 ; 6 , 8 ; 7 ; 9

As you can see the vertices of an SCC are "all together". In other words we cannot have in the stack $v_1, v_2, v_3$ where $v_1 \in S_1 \land v_3 \in S_1$ and $v_2 \in S_2$.

How to prove this mathematically? Thank you.

$\endgroup$
2
  • $\begingroup$ You say "How to prove this mathematically?" - what do you want to prove? What does "this" refer to? Please provide in the question a precise mathematical statement that you are looking to prove. Then, show us what progress you've made on trying to prove it yourself. What textbooks have you consulted? I suspect what you're asking for is a standard fact that is already proven in good textbooks. $\endgroup$
    – D.W.
    Dec 19 '21 at 8:22
  • $\begingroup$ I don't think this will produce a topological ordering of the SCCs, since jothing is preventing the DFS from first leaving the current SCC and going to the next one - and afterwards to continue work on the current SCC. Also the example stack configuration you wrote cannot be achieved - one cannot have 4 immediately after 3 in the stack since they are not connected together in a direct edge. $\endgroup$
    – nir shahar
    Dec 19 '21 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.