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

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

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

Другими словами, это подграф ${\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)}$-цепи.

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

Алгоритм

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

См. также

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

Ссылки

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