Компонент сильной связи
В математической теории ориентированных графов граф называется сильно связным , если каждая его вершина достижима из любой другой вершины. Сильно связные компоненты произвольного ориентированного графа образуют разбиение на подграфы, которые сами по себе сильно связны. Можно проверить сильную связность графа или найти его сильносвязные компоненты за линейное время (то есть Θ( V + E )).
Ориентированный граф называется сильно связным , если между каждой парой вершин графа существует путь в каждом направлении. То есть существует путь от первой вершины пары ко второй, а другой путь существует от второй вершины к первой. В ориентированном графе G , который сам по себе не может быть сильно связным, говорят, что пара вершин u и v сильно связана друг с другом, если между ними есть путь в каждом направлении.
Бинарное отношение сильной связности является отношением эквивалентности , а индуцированные подграфы его классов эквивалентности называются компонентами сильной связности . Эквивалентно, сильно связная компонента ориентированного графа G - это сильно связный подграф, который максимален с этим свойством: никакие дополнительные ребра или вершины из G не могут быть включены в подграф без нарушения его свойства сильной связности. Набор компонентов сильной связности образует разбиение множества вершин графа G .
Если каждая компонента сильной связности стягивается в одну вершину , результирующий граф является направленным ациклическим графом , сгущением графа G. Ориентированный граф ацикличен тогда и только тогда, когда он не имеет сильно связных подграфов с более чем одной вершиной, так как ориентированный цикл сильно связен и каждая нетривиальная компонента сильной связности содержит хотя бы один ориентированный цикл.
Несколько алгоритмов, основанных на поиске в глубину , вычисляют сильно связанные компоненты за линейное время .
Хотя алгоритм Косараджу концептуально прост, алгоритм Тарьяна и алгоритм на основе пути требуют только одного поиска в глубину, а не двух.
