graph-theorydirected-graphcyclic-graphstrongly-connected-graph

Difference between a directed cycle and a strongly connected component


Direced Graoh

I have this graph. The SCCs in this Graph are {a, b, e}, {d, g}, and {c, d, h}. But the cycles in this graph are the same components, right?

So what exactly is the difference between SCCs and directed cycles? Do they only differ in specific cases?


Solution

  • In a directed graph G(V,E):


    The difference is that:

    If you have the strongly connected component:

     A → B
     ↓ ↖ ↓
     C → D
    

    Then there is a directed path C → D → A → B and a directed path B → D → A → C but there is no directed cycle that contains both B and C as the edge D → A would have to be visited twice in the cycle.


    Additionally, there is another (technical) difference that if the directed cycle visits all the vertices then it is a strongly connected directed graph and not a strongly connected component (as a component is a strict sub-graph).