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

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

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

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

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

Алгоритм

Для выделения компонент связности можно использовать поиск в ширину или поиск в глубину. При этом затраченное время будет линейным от суммы числа вершин и числа рёбер графа.

См. также

• Связный граф
• Вполне несвязный граф
• Словарь терминов теории графов
• Компонента сильной связности в орграфе
• Теория перколяции

Ссылки

Видеозапись лекции посвященной связности графов (недоступная ссылка)