Maximum Strongly Connected Components Flashcards
Front
Back
What is a strongly connected component (SCC)?
A set of vertices in a directed graph where every vertex is reachable from every other vertex in the set.
What is a maximal strongly connected component (MSCC)?
An SCC that is not part of a larger SCC; it cannot be extended while preserving strong connectivity.
Do MSCCs overlap?
No, MSCCs are disjoint. Each vertex belongs to exactly one MSCC.
Why can’t two MSCCs share a vertex?
Because if they did, the union of those components would also be strongly connected, violating their maximality.
What happens when you compress each MSCC into a node?
You create a super graph, where each MSCC is represented as a single node.
What kind of graph is the MSCC super graph?
A Directed Acyclic Graph (DAG).
Why is the MSCC super graph acyclic?
If it had a cycle, the union of the MSCCs in the cycle would form a larger SCC, contradicting maximality.
What is the reverse graph G^T?
A graph formed by reversing the direction of every edge in the original graph.
How do you form the reverse graph using an adjacency matrix?
By transposing the matrix.
Do MSCCs change when the graph is reversed?
No, the MSCCs of a graph are the same as those of its reverse.
What is a common use of MSCC super graphs in algorithms?
They are used for topological sorting since the super graph is a DAG.
