patternMinor
Why vertices of directed acyclic graph are considered strongly-connected components?
Viewed 0 times
whygraphacyclicaredirectedconsideredstronglycomponentsconnectedvertices
Problem
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.
Solution
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:
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:
Context
StackExchange Computer Science Q#90861, answer score: 8
Revisions (0)
No revisions yet.