2
$\begingroup$

Well the title pretty much says it all, I've heard our professor saying that the smallest strongly-connected components in DAG (directed acyclic graph) are its vertices. Sadly I was unable to ask him for explanation and now this is stuck in my head ever since.

$\endgroup$
4
$\begingroup$

This has to do with the definition of Strongly Connected Component in graph theory.

A graph to be said to be Strongly Connected if every vertex is reachable from every other vertex.

The smallest possible graph of any type consists of a single vertex. Since that vertex can reach itself (since it is itself), the graph therefore meets the criteria, and can be considered Strongly Connected.

In this image, the nodes at the bottom right, and the top middle are examples of smallest possible strongly connected components: enter image description here

$\endgroup$
  • $\begingroup$ But isnt directed acyclic graphs graphs without cycle or cycle of one vertex is not considered cycle? I admit I am really bad at graphs and graph theory.. $\endgroup$ – kuskmen Apr 18 '18 at 18:50
  • 2
    $\begingroup$ I added an image that should help. A DAG can have many components which themselves are not acyclic, like in the image. But once you leave a component, you cant go back to the previous component, thus acyclic. But yes, a vertex is not considered a cycle on its own. to have a cycle you have to traverse an edge. $\endgroup$ – Stephan Apr 18 '18 at 18:57
  • $\begingroup$ I think I understand now, thanks a lot, I will try to topologically sort it now :) $\endgroup$ – kuskmen Apr 18 '18 at 19:16

Your Answer

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

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