Strongly Connected Components Flashcards
(10 cards)
What is a Strongly Connected Component (SCC)?
A subset of vertices in a directed graph where every vertex is reachable from every other vertex in the subset.
What is the condition for a subset of vertices to be an SCC?
For every pair of vertices (u, v), there is a path from u to v and from v to u, and all paths lie within the subset.
What is a Maximal Strongly Connected Component (MSCC)?
An SCC that cannot be extended by adding any other vertex from the graph without losing the strong connectivity.
How can you tell if an SCC is maximal?
If for every vertex not in the SCC, adding it results in a set that is not an SCC.
What is the difference between an SCC and an MSCC?
An SCC may be extendable, while an MSCC is the largest possible SCC that cannot be extended.
Can a single vertex be an SCC?
Yes, if there are no outgoing or incoming edges, or it forms a self-loop.
What is the SCC decomposition of a graph?
A partitioning of the graph into its maximal strongly connected components.
Why are SCCs important in graph algorithms?
They serve as a starting point for solving many graph problems and analyzing graph structure.
Is the entire graph always a strongly connected component?
No, only if there is a path between every pair of nodes in both directions.
Do all vertices belong to an SCC?
Yes, every vertex belongs to exactly one maximal SCC.
