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

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

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

Определения

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

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

Алгоритмы

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

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

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

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

Пример

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

См. также

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

Литература

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

Эта страница в последний раз была отредактирована 31 марта 2024 в 12:18.