28-04-2024
Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Сильно связными компонентами орграфа называются его максимальные по включению сильно связные подграфы.
Содержание |
Орграф, не принадлежащий к классу сильно связных графов, содержит некоторый набор сильно связных компонент, и некоторый набор ориентированных ребер, идущих от одной компоненты к другой.
Любая вершина орграфа сильно связана сама с собой.
Простейший алгоритм решения задачи о поиске сильно связных компонент в орграфе работает следующим образом:
Очевидно основное время работы данного алгоритма приходится на реализацию транзитивного замыкания.
Также существует три алгоритма, решающих данную задачу за линейное время, то есть в V раз быстрее, чем приведенный выше алгоритм. Это алгоритмы Косарайю, Габова и Тарьяна.
На данном примере изображен орграф, для которого найдены все три компоненты сильной связности (закрашенные области, обведенные пунктиром).
Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её. |
Компонент сильной связности графа это, компонента сильной связности графа ройвена, компонента сильной связности графа юсупова.
Файл:Burg Rettenberg, Kolsassberg.JPG, Файл:Darmodej a dalsi.gif, Категория:Тяжелоатлеты на летних Олимпийских играх 1960 года.