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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Несвязный граф с тремя компонентами связности

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

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

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

Алгоритм[править | править вики-текст]

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

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

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