Сильно связанный компонент
| Соответствующие темы по |
| Графовая связность |
|---|
В математической теории ориентированных графов граф называется сильно связным, если каждая вершина достижима из любой другой вершины. Сильно связные компоненты ориентированного графа образуют разбиение на подграфы , которые сами по себе сильно связны. Можно проверить сильную связность графа или найти его сильно связные компоненты за линейное время (т. е. Θ( V + E )).
Определения
[ редактировать ]называется Ориентированный граф сильно связным существует путь , если между каждой парой вершин графа в каждом направлении. То есть существует путь от первой вершины пары ко второй, и существует другой путь от второй вершины к первой.В ориентированном графе G, который сам по себе может не быть сильно связным, пара вершин u и v называется сильно связанной друг с другом, если между ними существует путь в каждом направлении.
Бинарное отношение сильной связности является отношением эквивалентности , и индуцированные подграфы его классов эквивалентности называются компонентами сильной связности .Эквивалентно, сильно связный компонент ориентированного графа G - это подграф, который сильно связен и является максимальным с этим свойством: никакие дополнительные ребра или вершины из G не могут быть включены в подграф, не нарушая его свойства сильно связности. Набор сильно связных компонент образует разбиение множества вершин G . Сильно связная компонента C называется тривиальной, если C состоит из единственной вершины, не соединенной сама с собой ребром, и нетривиальной в противном случае. [1]
Если каждый сильно связный компонент сжимается до одной вершины, результирующий граф представляет собой граф , конденсацию G. ориентированный ациклический Ориентированный граф является ациклическим тогда и только тогда, когда он не имеет сильно связных подграфов с более чем одной вершиной, поскольку ориентированный цикл сильно связен и каждая нетривиальная сильно связная компонента содержит хотя бы один ориентированный цикл.
Алгоритмы
[ редактировать ]Алгоритмы линейного времени на основе DFS
[ редактировать ]Несколько алгоритмов, основанных на поиске в глубину, вычисляют сильно связанные компоненты за линейное время.
- Алгоритм Косараджу использует два прохода поиска в глубину. Первый, в исходном графе, используется для выбора порядка, в котором внешний цикл второго поиска в глубину проверяет вершины на предмет уже посещенных вершин и рекурсивно исследует их, если нет. Второй поиск в глубину выполняется на графе транспонирования исходного графа, и каждое рекурсивное исследование находит один новый сильно связный компонент. [2] [3] Назван в честь С. Рао Косараджу , описавшего его (но не опубликовавшего своих результатов) в 1978 г.; Миша Шарир позже опубликовал его в 1981 году. [4]
- Алгоритм сильно связанных компонентов Тарьяна , опубликованный Робертом Тарьяном в 1972 году, [5] выполняет один проход поиска в глубину. Он поддерживает стек вершин, которые были исследованы в ходе поиска, но еще не назначены компоненту, и вычисляет «низкие номера» каждой вершины (индексный номер самого высокого предка, достижимого за один шаг от потомка вершины), который он используется для определения того, когда набор вершин следует извлечь из стека в новый компонент.
- Алгоритм сильной компоненты на основе пути использует поиск в глубину, как и алгоритм Тарьяна, но с двумя стеками. Один из стеков используется для отслеживания вершин, еще не назначенных компонентам, а другой — для текущего пути в дереве поиска в глубину. Первая версия этого алгоритма с линейным временем была опубликована Эдсгером В. Дейкстрой в 1976 году. [6]
Хотя алгоритм Косараджу концептуально прост, алгоритм Тарьяна и алгоритм, основанный на путях, требуют только одного поиска в глубину, а не двух.
Алгоритмы, основанные на достижимости
[ редактировать ]Предыдущие алгоритмы с линейным временем основывались на поиске в глубину, который обычно считается трудным для распараллеливания. Флейшер и др. [7] в 2000 году предложил подход «разделяй и властвуй», основанный на запросах достижимости , и такие алгоритмы обычно называют алгоритмами SCC, основанными на достижимости. Идея этого подхода состоит в том, чтобы выбрать случайную опорную вершину и применить к ней запросы прямой и обратной достижимости. Два запроса делят набор вершин на 4 подмножества: вершины, достигнутые обоими, либо одним, либо ни одним из поисков. Можно показать, что сильно связная компонента должна содержаться в одном из подмножеств. Подмножество вершин, достигнутое в результате обоих поисков, образует сильно связный компонент, а затем алгоритм рекурсивно обращается к остальным трем подмножествам.
Показано, что ожидаемое последовательное время работы этого алгоритма составляет O( n log n ), что в O(log n ) больше, чем у классических алгоритмов. Параллелизм обусловлен: (1) запросы о достижимости можно распараллелить легче (например, с помощью поиска в ширину (BFS), и это может быть быстро, если диаметр графа мал); и (2) независимость между подзадачами в процессе «разделяй и властвуй».Этот алгоритм хорошо работает на реальных графиках. [3] но не имеет теоретической гарантии параллелизма (учтите, что если в графе нет ребер, алгоритм требует O( n ) уровней рекурсии).
Блелох и др. [8] в 2016 году показывает, что если запросы о достижимости применяются в случайном порядке, граница стоимости O( n log n ) по-прежнему сохраняется. Кроме того, запросы затем могут быть объединены в пакеты с удвоением префикса (т. е. 1, 2, 4, 8 запросов) и выполняться одновременно в одном раунде. Общий диапазон этого алгоритма составляет log 2 n запросов достижимости, что, вероятно, является оптимальным параллелизмом, которого можно достичь с помощью подхода, основанного на достижимости.
Генерация случайных сильно связных графов
[ редактировать ]Питер М. Маурер описывает алгоритм генерации случайных сильно связных графов: [9] основанный на модификации алгоритма усиления связности , задача добавления как можно меньшего количества ребер, чтобы сделать граф сильно связным. При использовании в сочетании с моделями Гилберта или Эрдеша-Реньи с перемаркировкой узлов алгоритм способен генерировать любой сильно связный граф на n узлах без ограничений на типы генерируемых структур.
Приложения
[ редактировать ]Алгоритмы поиска сильно связанных компонентов могут использоваться для решения задач 2-выполнимости (систем булевых переменных с ограничениями на значения пар переменных): как показали Аспвалл, Пласс и Тарьян (1979) , экземпляр 2-выполнимости невыполним, если и только если существует переменная v такая, что v и ее отрицание содержатся в одном и том же сильно связном компоненте графа импликации экземпляра. [10]
Сильно связные компоненты также используются для вычисления разложения Дулмаджа-Мендельсона , классификации ребер двудольного графа , в зависимости от того, могут ли они быть частью идеального паросочетания в графе. [11]
Связанные результаты
[ редактировать ]Ориентированный граф является сильно связным тогда и только тогда, когда он имеет ушную декомпозицию — разбиение ребер на последовательность направленных путей и циклов такое, что первый подграф в последовательности является циклом, а каждый последующий подграф — либо циклом, разделяющим одна вершина с предыдущими подграфами или путь, разделяющий две конечные точки с предыдущими подграфами.
Согласно теореме Роббинса , неориентированный граф может быть ориентирован таким образом, что он станет сильно связным тогда и только тогда, когда он 2-реберно-связен . Один из способов доказать этот результат — найти разложение уха основного неориентированного графа, а затем последовательно сориентировать каждое ухо. [12]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Нуутила, Эско; Сойсалон-Сойнинен, Эльяс (1994), «О поиске сильно связанных компонентов в ориентированном графе», Information Processing Letters , 49 (1): 9–14, doi : 10.1016/0020-0190(94)90047-7
- ^ Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 22.5, стр. 552–557.
- ^ Перейти обратно: а б Хонг, Сунгпак; Родия, Николь С.; Олукотун, Кунле (2013), «О быстром параллельном обнаружении сильно связанных компонентов (SCC) в графах малого мира» (PDF) , Материалы Международной конференции по высокопроизводительным вычислениям, сетям, хранению и анализу - SC '13 , стр. . 1–11, номер домена : 10.1145/2503210.2503246 , ISBN. 9781450323789 , S2CID 2156324
- ^ Шарир, Миха (1981), «Алгоритм сильной связности и его приложения в анализе потоков данных», Computers & Mathematics with Applications , 7 : 67–72, doi : 10.1016/0898-1221(81)90008-0
- ^ Тарьян, Р.Э. (1972), «Алгоритмы поиска в глубину и линейные графы», SIAM Journal on Computing , 1 (2): 146–160, doi : 10.1137/0201010 , S2CID 16467262
- ^ Дейкстра, Эдсгер (1976), Дисциплина программирования , Нью-Джерси: Прентис Холл, гл. 25 .
- ^ Флейшер, Лиза К.; Хендриксон, Брюс; Пинар, Али (2000), «Об определении сильно связанных компонентов в параллельном режиме» (PDF) , Параллельная и распределенная обработка , Конспекты лекций по информатике, том. 1800, стр. 505–511, номер документа : 10.1007/3-540-45591-4_68 , ISBN. 978-3-540-67442-9
- ^ Блеллок, Гай Э.; Гу, Ян; Шун, Джулиан; Сунь, Ихан (2016), «Параллелизм в рандомизированных инкрементных алгоритмах» (PDF) , Материалы 28-го симпозиума ACM по параллелизму в алгоритмах и архитектурах - SPAA '16 , стр. 467–478, doi : 10.1145/2935764.2935766 , hdl : 21.1 /146176 , ISBN 9781450342100 .
- ^ Маурер, П.М. (февраль 2018 г.), Генерация сильно связных случайных графов (PDF) , Int'l Conf. Моделирование, Сим. и Вис. Методы MSV'17, CSREA Press, ISBN 978-1-60132-465-8 , получено 27 декабря 2019 г.
- ^ Аспвалль, Бенгт; Пласс, Майкл Ф.; Тарьян, Роберт Э. (1979), «Алгоритм линейного времени для проверки истинности некоторых количественных логических формул», Information Processing Letters , 8 (3): 121–123, doi : 10.1016/0020-0190(79)90002 -4 .
- ^ Дулмейдж, А.Л. и Мендельсон, Н.С. (1958), «Покрытия двудольных графов», Can. Дж. Математика. , 10 : 517–534, doi : 10.4153/cjm-1958-052-0 , S2CID 123363425 .
- ^ Роббинс, HE (1939), «Теорема о графах с применением к задаче управления дорожным движением», American Mathematical Monthly , 46 (5): 281–283, doi : 10.2307/2303897 , JSTOR 2303897 .
Внешние ссылки
[ редактировать ]- Реализация Java для вычисления сильно связанных компонентов в библиотеке jBPT (см. класс StronglyConnectedComponents).
- C++ реализация сильно связанных компонентов