Graph Theory37 sections · 1633 units
Open in Course

The Condensation Graph

(DAG of SCCs)

The condensation graph (or meta-graph) is a DAG where each node represents one SCC from the original graph. Add a directed edge from component AA to component BB in the condensation graph if there exists at least one edge from any node in SCC AA to any node in SCC BB in the original graph.

This condensation graph is always a DAG (no cycles). You can run topological sort on it, compute longest paths, or apply dynamic programming. It reveals the high-level structure of the original graph.