В математической теории направленных графов граф называется сильно связным, если каждая вершина достижима из любой другой вершины. Сильно связные компоненты направленного графа образуют разбиение на подграфы , которые сами по себе сильно связны. Можно проверить сильную связность графа или найти его сильно связные компоненты за линейное время (то есть Θ( V + E )).
Направленный граф называется сильно связанным , если между каждой парой вершин графа существует путь в каждом направлении. То есть, существует путь от первой вершины в паре ко второй, и существует другой путь от второй вершины к первой. В направленном графе G, который сам по себе может не быть сильно связанным, пара вершин u и v называются сильно связанными друг с другом, если между ними существует путь в каждом направлении.
Бинарное отношение быть сильно связанным является отношением эквивалентности , а индуцированные подграфы его классов эквивалентности называются сильно связанными компонентами . Эквивалентно, сильно связанный компонент ориентированного графа G является подграфом, который сильно связан и является максимальным с этим свойством: никакие дополнительные ребра или вершины из G не могут быть включены в подграф, не нарушая его свойства быть сильно связанным. Набор сильно связанных компонентов образует разбиение множества вершин G. Сильно связанный компонент C называется тривиальным , когда C состоит из одной вершины, которая не связана сама с собой ребром, и нетривиальным в противном случае. [1]
Если каждый сильно связный компонент стягивается в одну вершину, то полученный граф является направленным ациклическим графом , конденсацией G. Направленный граф является ациклическим тогда и только тогда, когда он не имеет сильно связных подграфов с более чем одной вершиной, поскольку направленный цикл сильно связен, а каждый нетривиальный сильно связный компонент содержит по крайней мере один направленный цикл.
Несколько алгоритмов, основанных на поиске в глубину, вычисляют сильносвязанные компоненты за линейное время.
Хотя алгоритм Косараджу концептуально прост, алгоритм Тарьяна и алгоритм на основе пути требуют только одного поиска в глубину вместо двух.
Предыдущие алгоритмы линейного времени основаны на поиске в глубину, который обычно считается сложным для распараллеливания. Флейшер и др. [7] в 2000 году предложили подход «разделяй и властвуй», основанный на запросах достижимости , и такие алгоритмы обычно называются алгоритмами SCC на основе достижимости. Идея этого подхода заключается в выборе случайной опорной вершины и применении прямых и обратных запросов достижимости из этой вершины. Два запроса разбивают множество вершин на 4 подмножества: вершины, достигнутые обоими поисками, либо одним, либо ни одним из поисков. Можно показать, что сильно связанный компонент должен содержаться в одном из подмножеств. Подмножество вершин, достигнутое обоими поисками, образует сильно связанный компонент, и затем алгоритм рекурсивно применяется к остальным 3 подмножествам.
Ожидаемое последовательное время выполнения этого алгоритма составляет O( n log n ), что на O(log n ) больше, чем у классических алгоритмов. Параллелизм возникает из-за: (1) запросов достижимости можно распараллелить проще (например, с помощью поиска в ширину (BFS), и это может быть быстро, если диаметр графа невелик); и (2) независимости между подзадачами в процессе «разделяй и властвуй». Этот алгоритм хорошо работает на реальных графах [3] , но не имеет теоретической гарантии параллелизма (представьте, что если граф не имеет ребер, алгоритм требует O( n ) уровней рекурсий).
Blelloch et al. [8] в 2016 году показали, что если запросы достижимости применяются в случайном порядке, ограничение стоимости O( n log n ) все еще сохраняется. Более того, запросы затем могут быть объединены в пакеты в префиксно-удвоенном виде (т. е. 1, 2, 4, 8 запросов) и запущены одновременно в одном раунде. Общий охват этого алгоритма составляет log 2 n запросов достижимости, что, вероятно, является оптимальным параллелизмом, которого можно достичь с помощью подхода, основанного на достижимости.
Питер М. Маурер описывает алгоритм для генерации случайных сильно связанных графов, [9] основанный на модификации алгоритма для увеличения сильной связности , проблемы добавления как можно меньшего количества ребер, чтобы сделать граф сильно связанным. При использовании в сочетании с моделями Гилберта или Эрдёша-Реньи с перемаркировкой узлов алгоритм способен генерировать любой сильно связанный граф на n узлах, без ограничений на виды структур, которые могут быть сгенерированы.
Алгоритмы поиска сильно связанных компонентов могут использоваться для решения задач 2-выполнимости (систем булевых переменных с ограничениями на значения пар переменных): как показали Аспвалл, Пласс и Тарьян (1979), экземпляр 2-выполнимости невыполним тогда и только тогда, когда существует переменная v такая, что v и ее отрицание содержатся в одном и том же сильно связанном компоненте графа импликации экземпляра. [10]
Сильно связанные компоненты также используются для вычисления разложения Дульмейджа–Мендельсона , классификации ребер двудольного графа в соответствии с тем, могут ли они быть частью идеального паросочетания в графе. [11]
Ориентированный граф является сильно связным тогда и только тогда, когда он имеет ушную декомпозицию — разбиение ребер на последовательность ориентированных путей и циклов, такое, что первый подграф в последовательности является циклом, а каждый последующий подграф — это либо цикл, разделяющий одну вершину с предыдущими подграфами, либо путь, разделяющий две свои конечные точки с предыдущими подграфами.
Согласно теореме Роббинса , неориентированный граф может быть ориентирован таким образом, что он станет сильно связанным, если и только если он 2-рёберно связан . Один из способов доказать этот результат — найти разложение уха базового неориентированного графа, а затем сориентировать каждое ухо последовательно. [12]