Ориентированный граф (орграф) называется сильно связным (Шаблон:Lang-en), если любые две его вершины s и t сильно связны, то есть если существует ориентированный путь из <math>s</math> в <math>t</math> и одновременно ориентированный путь из <math>t</math> в <math>s.</math>
Компонентами сильной связности орграфа называются его максимальные по включению сильно связные подграфы. Областью сильной связности называется множество вершин компонентов сильной связности.
Орграф, не принадлежащий к классу сильно связных графов, содержит некоторый набор сильно связных компонент, и некоторый набор ориентированных рёбер, идущих от одной компоненты к другой.
Любая вершина орграфа сильно связна сама с собой.
Алгоритмы
Простейший алгоритм решения задачи о поиске сильно связных компонент в орграфе работает следующим образом:
При помощи транзитивного замыкания проверяем, достижима ли <math>t</math> из <math>s,</math> и <math>s</math> из <math>t,</math> для всех пар <math>s</math> и <math>t.</math>
Затем определяем такой неориентированный граф, в котором для каждой такой пары содержится ребро.
Поиск компонент связности такого неориентированного графа даёт компоненты сильной связности орграфа.
Очевидно основное время работы данного алгоритма занимает транзитивное замыкание.
