Компонента связности графа ${\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)}$ - цепи .

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

Алгоритм

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

См. также

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

Ссылки

Примечания

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