Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
График с отмеченными сильно связными компонентами
Актуальные темы на
Связь с графиком

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

Определения [ править ]

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

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

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

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

Алгоритмы [ править ]

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

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

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

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

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

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

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

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

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

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

Приложения [ править ]

Алгоритмы поиска сильно связных компонентов могут использоваться для решения задач 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, DOI : 10,1145 / 2503210,2503246 , ISBN  9781450323789
  3. ^ Шарир, Миха (1981), «Алгоритм сильной связи и его применение в данном анализе поток», Компьютеры и Математика с приложениями , 7 : 67-72, DOI : 10,1016 / 0898-1221 (81) 90008-0
  4. ^ Тарьян, RE (1972), "Поиск в глубину и линейный график алгоритмы", SIAM журнал по вычислениям , 1 (2): 146-160, DOI : 10,1137 / 0201010
  5. ^ Дейкстра, Эдсгер (1976), дисциплина программирования , NJ: Prentice Hall, гл. 25.
  6. ^ Флейшер, Лиза К .; Хендриксон, Брюс; Пынар, Али (2000), «Идентификация сильно связанных компонентов в параллельном режиме» (PDF) , Параллельная и распределенная обработка , Лекционные заметки по информатике, 1800 , стр. 505–511, DOI : 10.1007 / 3-540-45591-4_68 , ISBN  978-3-540-67442-9
  7. ^ Blelloch, Guy E .; Гу, Ян; Шун, Джулиан; Sun, Yihan (2016), «Параллелизм в рандомизированных инкрементальных алгоритмах» (PDF) , Материалы 28-го симпозиума ACM по параллелизму в алгоритмах и архитектурах - SPAA '16 , стр. 467–478, doi : 10.1145 / 2935764.2935766 , ISBN  9781450342100.
  8. ^ Maurer, PM, Генерация сильно связанных случайных графов (PDF) , Int'l Conf. Моделирование, Сим. и Vis. Методы MSV'17, CSREA Press, ISBN  1-60132-465-0, получено 27 декабря 2019 г.
  9. ^ Аспвалл, Бенгт; Plass, Майкл Ф .; Тарьян, Роберт Э. (1979), «Алгоритм линейного времени для проверки истинности определенных количественных булевых формул», Письма об обработке информации , 8 (3): 121–123, DOI : 10.1016 / 0020-0190 (79) 90002 -4.
  10. ^ Dulmage, AL & Mendelsohn, NS (1958), "Накрытия двудольных графов", Can. J. Math. , 10 : 517-534, DOI : 10,4153 / CJM-1958-052-0.
  11. ^ Роббинс, HE (1939), "Теорема о графах, с приложением к проблеме управления движением", American Mathematical Monthly , 46 (5): 281–283, DOI : 10.2307 / 2303897 , JSTOR 2303897 .

Внешние ссылки [ править ]

  • Реализация Java для вычисления сильно связанных компонентов в библиотеке jBPT (см. Класс StronglyConnectedComponents).
  • Реализация сильно связанных компонентов на C ++