Введение

Разделение графа, компоненты которого достижимы из любой вершины

В математической теории ориентированных графов граф называется сильно связным, если из каждой вершины можно достичь любую другую вершину. Сильно связные компоненты ориентированного графа образуют разделение на подграфы, которые сами по себе являются сильно связными. Возможно проверить сильную связность графа или найти его сильно связные компоненты за линейное время (то есть Θ(V + E)).

Определения

Направленный граф называется сильно связным, если между каждой парой его вершин существует путь в обоих направлениях. То есть, существует путь от первой вершины в паре ко второй, и другой путь – от второй вершины к первой. В направленном графе G, который может быть и не сильно связным, пара вершин u и v называется сильно связанной, если между ними есть путь в обоих направлениях. Отношение сильной связности является отношением эквивалентности, а индуцированные подграфы его классов эквивалентности называются сильно связными компонентами. Эквивалентно, сильно связная компонента направленного графа G – это подграф, который является сильно связным и максимальным по этому свойству: нельзя добавить к этому подграфу ни ребро, ни вершину из G, не нарушив его свойство быть сильно связным. Множество сильно связных компонент образует разбиение множества вершин G. Сильно связная компонента C называется тривиальной, если C состоит из единственной вершины, не имеющей петли, и нетривиальной – в противном случае. Если каждую сильно связную компоненту сжать до одной вершины, то полученный граф будет направленным ациклическим графом, называемым конденсацией G. Направленный граф является ациклическим тогда и только тогда, когда он не содержит сильно связных подграфов, состоящих более чем из одной вершины, поскольку направленный цикл является сильно связным, и каждая нетривиальная сильно связная компонента содержит хотя бы один направленный цикл.

Алгоритмы линейного времени на основе DFS

Несколько алгоритмов, основанных на поиске в глубину, вычисляют сильно связные компоненты за линейное время. Алгоритм Косараджу использует два прохода поиска в глубину. Первый, в исходном графе, используется для выбора порядка, в котором внешний цикл второго поиска в глубину проверяет, были ли вершины посещены ранее, и рекурсивно исследует их, если нет. Второй поиск в глубину выполняется на транспонированном графе исходного графа, и каждое рекурсивное исследование находит одну новую сильно связную компоненту. Алгоритм Тарджана для поиска сильно связных компонент, опубликованный Робертом Тарджаном в 1972 году, выполняет один проход поиска в глубину. Он поддерживает стек вершин, которые были исследованы в ходе поиска, но еще не отнесены к компоненте, и вычисляет "низкие номера" для каждой вершины (индекс самого высокого предка, достижимого за один шаг от потомка вершины), который используется для определения момента, когда набор вершин следует извлечь из стека в новую компоненту. Алгоритм поиска сильно связных компонент на основе путей использует поиск в глубину, как и алгоритм Тарджана, но с двумя стеками. Один стек используется для отслеживания вершин, еще не отнесенных к компонентам, а другой – для отслеживания текущего пути в дереве поиска в глубину. Первая версия этого алгоритма, работающая за линейное время, была опубликована Эдсгером В. Дейкстрой в 1976 году. Хотя алгоритм Косараджу концептуально прост, алгоритм Тарджана и алгоритм на основе путей требуют только одного поиска в глубину, а не двух.

Алгоритмы, основанные на доступности

Предыдущие алгоритмы линейного времени основаны на поиске в глубину, который обычно считается сложным для параллелизации. Флейшер и др. в 2000 году предложили подход "разделяй и властвуй" на основе запросов достижимости, и такие алгоритмы обычно называют SCC-алгоритмами, основанными на достижимости. Идея этого подхода заключается в выборе случайной опорной вершины и выполнении запросов достижимости в прямом и обратном направлениях из этой вершины. Два запроса разбивают множество вершин на 4 подмножества: вершины, достигнутые обоими поисками, одним из них или ни одним. Можно показать, что сильно связный компонент должен содержаться в одном из этих подмножеств. Подмножество вершин, достигнутое обоими поисками, формирует сильно связный компонент, а затем алгоритм рекурсивно применяется к другим 3 подмножествам. Показано, что ожидаемое последовательное время работы этого алгоритма составляет O(n log n), что на O(log n) больше, чем у классических алгоритмов. Параллелизм обеспечивается: (1) запросы достижимости могут быть параллелизованы более легко (например, с помощью поиска в ширину (BFS), который может быть быстрым, если диаметр графа мал); и (2) независимостью между подзадачами в процессе "разделяй и властвуй". Этот алгоритм хорошо работает на реальных графах, но не имеет теоретических гарантий параллелизма (например, если граф не имеет ребер, алгоритму требуется O(n) уровней рекурсии). Блелох и др. в 2016 году показали, что если запросы достижимости выполняются в случайном порядке, то оценка стоимости O(n log n) остаётся в силе. Кроме того, запросы можно выполнять пакетами, удваивая их количество на каждом шаге (т.е. 1, 2, 4, 8 запросов) и выполнять одновременно за один раунд. Общая сложность этого алгоритма составляет log₂n запросов достижимости, что, вероятно, является оптимальным уровнем параллелизма, достижимым при использовании подхода, основанного на достижимости.

Генерация случайных сильно связанных графиков

Питер М. Маурер описывает алгоритм генерации случайных сильно связных графов, основанный на модификации алгоритма для повышения сильной связности – задачи добавления минимального количества ребер для обеспечения сильной связности графа. В сочетании с моделями Гильберта или Эрдоша — Реньи с перенумерацией вершин, алгоритм способен генерировать любой сильно связный граф на n вершинах, без каких-либо ограничений на типы генерируемых структур.

Приложения

Алгоритмы поиска сильно связанных компонентов могут быть использованы для решения задач 2-удовлетворимости (системы булевых переменных с ограничениями на значения пар переменных): как было показано, экземпляр 2-удовлетворимости является неудовлетворимым тогда и только тогда, когда существует переменная v, такая что v и её отрицание одновременно содержатся в одном и том же сильно связном компоненте импликационного графа этого экземпляра. Сильно связанные компоненты также используются для вычисления разложения Дулмажа — Мендельсона, которое представляет собой классификацию рёбер двудольного графа в зависимости от того, могут ли они входить в состав совершенного паросочетания в этом графе.

Сопутствующие результаты

Направленный граф сильно связен тогда и только тогда, когда у него существует ушная декомпозиция – разбиение ребер на последовательность ориентированных путей и циклов, при этом первый подграф в последовательности является циклом, а каждый последующий подграф является либо циклом, имеющим общую вершину с предыдущими подграфами, либо путем, имеющим обе конечные точки общими с предыдущими подграфами. Согласно теореме Роббинса, ненаправленный граф можно ориентировать так, чтобы он стал сильно связным, тогда и только тогда, когда он 2-реберно связен. Один из способов доказать этот результат – найти ушную декомпозицию лежащего в основе ненаправленного графа и затем последовательно ориентировать каждое ухо.