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

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

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

Другими словами, это подграф , порождённый множеством  вершин, в котором для любой пары вершин в графе  существует -цепь и для любой пары вершин , не существует -цепи.

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

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

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

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

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

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