Сильносвязная компонента - Strongly connected component

График с отмеченными сильно связными компонентами
Актуальные темы на
Связность графиков

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

Определения

Ориентированный граф называется сильно связным , если существует путь в каждом направлении между каждой парой вершин графа. То есть существует путь от первой вершины пары ко второй, а другой путь существует от второй вершины к первой. В ориентированном графе G, который сам по себе не может быть сильно связным, пара вершин u и v называется сильно связанными друг с другом, если между ними существует путь в каждом направлении.

Бинарное отношение быть тесно связано это отношение эквивалентности , и индуцированные подграфы ее классов эквивалентности называются сильно связанные компоненты . Эквивалентно сильно связная компонента ориентированного графа G является сильно связным подграфом и максимальна с этим свойством: никакие дополнительные ребра или вершины из G не могут быть включены в подграф без нарушения его свойства сильной связности. Коллекция сильно связных компонент образует разбиение множества вершин G .

Желтый ориентированный ациклический граф - это сгущение синего ориентированного графа. Он формируется путем сжатия каждой сильно связной компоненты синего графа в одну желтую вершину.

Если каждый сильно подключенный компонент по контракту с одной вершиной, полученный граф является ориентированный ациклический граф , то конденсат из G . Ориентированный граф является ацикличным тогда и только тогда, когда он не имеет сильно связных подграфов с более чем одной вершиной, потому что ориентированный цикл сильно связен и каждая нетривиальная сильно связная компонента содержит хотя бы один ориентированный цикл.

Алгоритмы

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

Несколько алгоритмов, основанных на поиске в глубину, вычисляют сильно связанные компоненты за линейное время .

  • Алгоритм Косараджу использует два прохода поиска в глубину . Первый в исходном графе используется для выбора порядка, в котором внешний цикл второго поиска в глубину проверяет вершины на предмет того, что они уже были посещены, и рекурсивно исследует их, если нет. Второй поиск в глубину выполняется на транспонированном графе исходного графа, и каждое рекурсивное исследование находит один новый сильно связный компонент. Он назван в честь С. Рао Косараджу , который описал его (но не опубликовал свои результаты) в 1978 году; Позже Миха Шарир опубликовал его в 1981 году.
  • Алгоритм сильносвязных компонентов Тарьяна , опубликованный Робертом Тарьяном в 1972 году, выполняет поиск в глубину за один проход. Он поддерживает стек вершин, которые были исследованы поиском, но еще не назначены компоненту, и вычисляет «низкие числа» каждой вершины (порядковый номер самого высокого предка, достижимого за один шаг от потомка вершины), который он используется, чтобы определить, когда набор вершин должен быть извлечен из стека в новый компонент.
  • Сильный алгоритм компонента траектории на основе использует глубину первый поиск, как алгоритм Tarján, но с двумя стеками. Один из стеков используется для отслеживания вершин, еще не назначенных компонентам, а другой отслеживает текущий путь в дереве поиска в глубину. Первая линейная версия этого алгоритма была опубликована Эдсгером В. Дейкстра в 1976 году.

Хотя алгоритм Косараджу концептуально прост, алгоритм Тарьяна и алгоритм на основе путей требуют только одного поиска в глубину, а не двух.

Алгоритмы на основе достижимости

Предыдущие алгоритмы с линейным временем основывались на поиске в глубину, который обычно трудно распараллелить. Fleischer et al. в 2000 г. предложил подход « разделяй и властвуй», основанный на запросах о достижимости , и такие алгоритмы обычно называют алгоритмами SCC на основе достижимости. Идея этого подхода состоит в том, чтобы выбрать случайную сводную вершину и применить запросы прямой и обратной достижимости от этой вершины. Два запроса разбивают набор вершин на 4 подмножества: вершины, достигнутые обоими поисками, либо одним, либо ни одним из поисков. Можно показать, что компонента сильной связности должна содержаться в одном из подмножеств. Подмножество вершин, достигнутое обоими поисками, образует компоненты сильной связности, а затем алгоритм рекурсивно обрабатывает остальные 3 поднабора.

Показано, что ожидаемое время последовательной работы этого алгоритма составляет O ( n  log  n ), что в O (log  n ) раз больше, чем у классических алгоритмов. Параллелизм проистекает из: (1) запросы о достижимости могут быть более легко распараллелены (например, с помощью поиска в ширину (BFS), и он может быть быстрым, если диаметр графа небольшой); и (2) независимость между подзадачами в процессе «разделяй и властвуй». Этот алгоритм хорошо работает на реальных графах, но не имеет теоретической гарантии параллелизма (подумайте, если граф не имеет ребер, алгоритм требует O ( n ) уровней рекурсий).

Blelloch et al. в 2016 году показывает, что если запросы о достижимости применяются в случайном порядке, граница стоимости O ( n  log  n ) по-прежнему сохраняется. Кроме того, запросы затем могут быть объединены в пакеты способом удвоения префикса (т. Е. 1, 2, 4, 8 запросов) и выполняться одновременно в одном цикле. Общий диапазон этого алгоритма составляет log 2 n запросов о достижимости, что, вероятно, является оптимальным параллелизмом, который может быть достигнут с использованием подхода, основанного на достижимости.

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

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

Приложения

Алгоритмы поиска сильно связных компонентов могут использоваться для решения задач 2-выполнимости (системы булевых переменных с ограничениями на значения пар переменных): как показали Aspvall, Plass & Tarjan (1979) , пример 2-выполнимости является неудовлетворительным, если и только если существует переменная v такая, что v и ее дополнение содержатся в одном и том же сильно связном компоненте графа импликации экземпляра.

Компоненты сильной связности также используются для вычисления разложения Далмажа – Мендельсона , классификации ребер двудольного графа , в зависимости от того, могут ли они быть частью идеального паросочетания в графе.

Связанные результаты

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

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

Смотрите также

Рекомендации

Внешние ссылки