Компонента связности графа

Компонента связности графа ${\displaystyle G}$ (или просто компонента графа ${\displaystyle G}$) — максимальный (по включению) связный подграф графа ${\displaystyle G}$.

Несвязный граф с тремя компонентами связности

Другими словами, это подграф ${\displaystyle G(U)}$, порождённый множеством ${\displaystyle U\subseteq V(G)}$ вершин, в котором для любой пары вершин ${\displaystyle u,v\in U}$ в графе ${\displaystyle G}$ существует ${\displaystyle (u,v)}$-цепь и для любой пары вершин ${\displaystyle u\in U}$, ${\displaystyle w\notin U}$ не существует ${\displaystyle (u,w)}$-цепи.

Для ориентированных графов определено понятие компоненты сильной связности.