Компонента сильной связности

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Ориентированный граф (орграф) называется сильно связным (англ. strongly connected), если любые две его вершины s и t сильно связны, то есть если существует ориентированный путь из в и одновременно ориентированный путь из в

Компонентами сильной связности орграфа называются его максимальные по включению сильно связные подграфы. Областью сильной связности называется множество вершин компонентов сильной связности.

Определения[править | править код]

Орграф, не принадлежащий к классу сильно связных графов, содержит некоторый набор сильно связных компонент, и некоторый набор ориентированных ребер, идущих от одной компоненты к другой.

Любая вершина орграфа сильно связна сама с собой.

Алгоритмы[править | править код]

Простейший алгоритм решения задачи о поиске сильно связных компонент в орграфе работает следующим образом:

  1. При помощи транзитивного замыкания проверяем, достижима ли из и из для всех пар и
  2. Затем определяем такой неориентированный граф, в котором для каждой такой пары содержится ребро.
  3. Поиск компонент связности такого неориентированного графа даёт компоненты сильной связности орграфа.

Очевидно основное время работы данного алгоритма занимает транзитивное замыкание.

Также существует три алгоритма, решающих данную задачу за линейное время, то есть в V раз быстрее, чем приведенный выше алгоритм. Это алгоритмы Косарайю, поиска компонент сильной связности с двумя стеками и Тарьяна.

Пример[править | править код]

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

На рисунке изображен орграф, для которого показаны все три компоненты сильной связности (закрашенные области, обведённые пунктиром).

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

Литература[править | править код]

  • Роберт Седжвик. Алгоритмы на графах = Graph algorithms. — 3-е изд. — Россия, Санкт-Петербург: «ДиаСофтЮП», 2002. — С. 496. — ISBN 5-93772-054-7.