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

---

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

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

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

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

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

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

---