Undirected connectivity¶
Connected component¶
An undirected graph is called connected if there exists a path between any pair of nodes. In undirected graphs, a connected component is a maximal set of connected nodes.
Directed connectivity¶
Weakly connected¶
A directed graph is weakly connected if the graph becomes connected when edge directions are ignored.
Strongly connected¶
A directed graph is strongly connected if every node can reach every other node while following edge directions. A strongly connected graph must also be weakly connected.
A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.
Giant component¶
Connectivity & robustness¶
Connectivity is often the first structural lens for understanding robustness. A system that depends on a small number of bridges, articulation points, or inter-component links may remain connected under normal conditions but fragment quickly under node or edge failures.