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

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

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

Определения

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

Приложения

Алгоритмы поиска сильно связанных компонент могут использоваться для решения 2-выполнимость задачи (системы булевых переменных с ограничениями на значения пар переменных): как Аспвалл, Пласс и Тарьян (1979) показал, 2-выполнимость экземпляр неудовлетворителен тогда и только тогда, когда есть переменная v такой, что v и его дополнение содержатся в одной и той же компоненте сильной связности граф импликации экземпляра.[9]

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

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

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

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

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

использованная литература

  1. ^ Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, и Клиффорд Штайн. Введение в алгоритмы, Второе издание. MIT Press и McGraw-Hill, 2001. ISBN  0-262-03293-7. Раздел 22.5, стр. 552–557.
  2. ^ а б Хун, Сунгпак; Родия, Николь С .; Олукотун, Кунле (2013), «О быстром параллельном обнаружении сильно связанных компонентов (SCC) в графах малого мира» (PDF), Труды Международной конференции по высокопроизводительным вычислениям, сетям, хранению данных и анализу - SC '13, стр. 1–11, Дои:10.1145/2503210.2503246, ISBN  9781450323789
  3. ^ Шарир, Миха (1981), "Алгоритм сильной связи и его приложения в анализе потока данных", Компьютеры и математика с приложениями, 7: 67–72, Дои:10.1016/0898-1221(81)90008-0
  4. ^ Тарьян, Р.Э. (1972), "Поиск в глубину и алгоритмы линейного графа", SIAM Журнал по вычислениям, 1 (2): 146–160, Дои:10.1137/0201010
  5. ^ Дейкстра, Эдсгер (1976), Дисциплина программирования, Нью-Джерси: Prentice Hall, Ch. 25.
  6. ^ Флейшер, Лиза К .; Хендриксон, Брюс; Пынар, Али (2000), «О параллельном выявлении прочно связанных компонентов» (PDF), Параллельная и распределенная обработка, Конспект лекций по информатике, 1800, стр. 505–511, Дои:10.1007/3-540-45591-4_68, ISBN  978-3-540-67442-9
  7. ^ Blelloch, Guy E .; Гу, Ян; Шун, Джулиан; Сунь, Ихан (2016), «Параллелизм в рандомизированных инкрементальных алгоритмах» (PDF), Материалы 28-го симпозиума ACM по параллелизму в алгоритмах и архитектурах - SPAA '16, стр. 467–478, Дои:10.1145/2935764.2935766, ISBN  9781450342100.
  8. ^ Маурер, П. М., Создание сильносвязных случайных графов (PDF), Междунар. Конф. Моделирование, Сим. и Vis. Методы MSV'17, CSREA Press, ISBN  1-60132-465-0, получено 27 декабря, 2019
  9. ^ Аспвалл, Бенгт; Plass, Майкл Ф .; Тарджан, Роберт Э. (1979), «Алгоритм линейного времени для проверки истинности определенных количественных булевых формул», Письма об обработке информации, 8 (3): 121–123, Дои:10.1016/0020-0190(79)90002-4.
  10. ^ Dulmage, A. L. & Мендельсон, Н.С. (1958), «Покрытия двудольных графов», Мочь. J. Math., 10: 517–534, Дои:10.4153 / cjm-1958-052-0.
  11. ^ Роббинс, Х. (1939), «Теорема о графах в приложении к проблеме управления движением», Американский математический ежемесячный журнал, 46 (5): 281–283, Дои:10.2307/2303897, HDL:10338.dmlcz / 101517, JSTOR  2303897.

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