13-06-2023
Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Компонентами сильной связности орграфа называются его максимальные по включению сильно связные подграфы.
Содержание |
Орграф, не принадлежащий к классу сильно связных графов, содержит некоторый набор сильно связных компонент, и некоторый набор ориентированных ребер, идущих от одной компоненты к другой.
Любая вершина орграфа сильно связана сама с собой.
Простейший алгоритм решения задачи о поиске сильно связных компонент в орграфе работает следующим образом:
Очевидно основное время работы данного алгоритма приходится на реализацию транзитивного замыкания.
Также существует три алгоритма, решающих данную задачу за линейное время, то есть в V раз быстрее, чем приведенный выше алгоритм. Это алгоритмы Косарайю, Габова и Тарьяна.
На данном примере изображен орграф, для которого найдены все три компоненты сильной связности (закрашенные области, обведенные пунктиром).
Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её. |
Сильно связная компонента.