WikiSort.ru - Не сортированное

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

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

Алгоритм

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

См. также

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

Ссылки

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

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.

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