Двусвязный компонент - Biconnected component

Пример графа с отмеченными двусвязными компонентами
Каждый цвет соответствует двусвязному компоненту. Разноцветные вершины - это разрезанные вершины, поэтому они принадлежат нескольким двусвязным компонентам.

В теория графов, а двусвязный компонент (иногда известный как 2-связный компонент) является максимальным двусвязный подграф. Любой связаны граф распадается на дерево двусвязных компонентов, называемых спиленное дерево графа. Блоки прикреплены друг к другу на общем вершины называется вырезать вершины или же точки сочленения. В частности, вырезать вершину - любая вершина, удаление которой увеличивает количество связанные компоненты.

Алгоритмы

Линейный поиск по глубине времени

Классический последовательный алгоритм для вычисления двусвязных компонентов в связном ненаправленный график связан с Джон Хопкрофт и Роберт Тарджан (1973).[1] Он работает в линейное время, и основан на поиск в глубину. Этот алгоритм также обозначен как проблема 22-2 из Введение в алгоритмы (как 2-е, так и 3-е издания).

Идея состоит в том, чтобы выполнить поиск в глубину, сохраняя при этом следующую информацию:

  1. глубина каждой вершины в дереве поиска в глубину (после посещения), и
  2. для каждой вершины v, наименьшая глубина соседей всех потомков v (включая v сам) в дереве поиска в глубину, называемом Низкая точка.

Глубина стандартна для поддержания во время поиска в глубину. Низкая точка v можно вычислить после посещения всех потомков v (т.е. непосредственно перед v выскакивает из поиска в глубину куча ) как минимум глубины v, глубина всех соседей v (кроме родителя v в дереве поиска в глубину) и нижнюю точку всех дочерних элементов v в дереве поиска в глубину.

Ключевой факт в том, что некорневая вершина v это разрезанная вершина (или точка сочленения), разделяющая два двусвязных компонента тогда и только тогда, когда есть дочерний у из v такой, что низкая точка (у) ≥ глубина (v). Это свойство можно проверить после того, как поиск в глубину будет возвращен каждым дочерним элементом v (т.е. непосредственно перед v извлекается из стека поиска в глубину), и если это правда, v разделяет график на разные двусвязные компоненты. Это может быть представлено вычислением одного двусвязного компонента из каждого такого у (компонент, содержащий у будет содержать поддерево у, плюс v), а затем удалив поддерево у из дерева.

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

Псевдокод

GetArticulationPoints (i, d) посещено [i]: = true depth [i]: = d low [i]: = d childCount: = 0 isArticulation: = false для каждого ni в adj [я] делать        если не посещал [ni] тогда            parent [ni]: = i GetArticulationPoints (ni, d + 1) childCount: = childCount + 1 если низкий [ni] ≥ глубина [i] тогда                isArticulation: = true low [i]: = Min (low [i], low [ni]) иначе если ni ≠ parent [я] тогда            low [i]: = Min (low [i], depth [ni]) если (parent [i] ≠ null и isArticulation) или же (parent [i] = null и childCount> 1) тогда        Выход i как точка сочленения

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

Демонстрация алгоритма Тарьяна для поиска вырезанных вершин. D обозначает глубину и L обозначает нижнюю точку.


Другие алгоритмы

Простая альтернатива приведенному выше алгоритму использует цепные разложения, которые представляют собой особые разложения уха в зависимости от DFS -деревья.[2] Цепные разложения могут быть вычислены за линейное время с помощью этого правило обхода. Позволять C - цепное разложение грамм. потом грамм является 2-вершинно-связным тогда и только тогда, когда грамм имеет минимум степень 2 и C1 единственный цикл в C. Это сразу дает тест на 2-связность в линейном времени и может быть расширен, чтобы перечислить все вырезанные вершины грамм за линейное время, используя следующее утверждение: Вершина v в связном графе грамм (с минимальной степенью 2) является разрезанной вершиной тогда и только тогда, когда v инцидент с мост или же v первая вершина цикла в С - С1. Список вырезанных вершин можно использовать для создания спиленное дерево из грамм в линейное время.

в онлайн версии проблемы, вершины и ребра добавляются (но не удаляются) динамически, а структура данных должна поддерживать двусвязные компоненты. Джеффри Уэстбрук и Роберт Тарджан (1992) [3] разработал эффективную структуру данных для этой проблемы на основе непересекающиеся структуры данных. В частности, он обрабатывает п вершинные добавления и м реберные сложения в O (м α(м, п)) полное время, где α - обратная функция Аккермана. Эта временная граница оказалась оптимальной.

Узи Вишкин и Роберт Тарджан (1985) [4] разработал параллельный алгоритм по CRCW PRAM который выполняется в O (журналп) время с п + м процессоры. Гоцзин Конг и Дэвид А. Бадер (2005) [5] разработал алгоритм, который обеспечивает 5-кратное ускорение при включении 12 процессоров. SMP. Джеймс Эдвардс и Джеймс Эдвардс сообщили об ускорении, превышающем 30, на основе исходного алгоритма Тарьяна-Вишкина. Узи Вишкин (2012).[6]

Связанные структуры

Отношение эквивалентности

Можно определить бинарное отношение на ребрах произвольного неориентированного графа, согласно которому два ребра е и ж связаны тогда и только тогда, когда е = ж или график содержит простой цикл через оба е и ж. Каждое ребро связано с собой, а ребро е относится к другому краю ж если и только если ж таким же образом относится к е. Менее очевидно, что это переходное отношение: если существует простой цикл, содержащий ребра е и ж, и еще один простой цикл, содержащий ребра ж и грамм, то можно объединить эти два цикла, чтобы найти простой цикл через е и грамм. Следовательно, это отношение эквивалентности, и его можно использовать для разделения ребер на классы эквивалентности, подмножества ребер со свойством, что два ребра связаны друг с другом тогда и только тогда, когда они принадлежат одному и тому же классу эквивалентности. Подграфы, образованные ребрами в каждом классе эквивалентности, являются двусвязными компонентами данного графа. Таким образом, двусвязные компоненты разбивают ребра графа; однако они могут иметь общие вершины друг с другом.[7]

Блочный график

В блочный граф данного графа грамм это граф пересечений своих блоков. Таким образом, у него есть одна вершина для каждого блока грамм, и ребро между двумя вершинами, если два соответствующих блока имеют общую вершину. ЧАС является блочным графом другого графа грамм именно тогда, когда все блоки ЧАС полные подграфы. Графики ЧАС с этим свойством известны как блочные графики.[8]

Обрезанное дерево

А точка отсечения, вырезать вершину, или же точка сочленения графа грамм - это вершина, общая для двух или более блоков. Структура блоков и точек сопряжения связного графа может быть описана дерево называется спиленное дерево или же BC-дерево. Это дерево имеет вершину для каждого блока и для каждой точки сочленения данного графа. В дереве вырезки блока есть ребро для каждой пары блока и точки сочленения, принадлежащей этому блоку.[9]

Граф и его блочное дерево.
Блоки: b1= [1,2], b2= [2,3,4], b3= [2,5,6,7], b4= [7,8,9,10,11], b5= [8,12,13,14,15], b6= [10,16] и b7=[10,17,18];
точки отсечения: c1= 2, c2= 7, c3= 8 и c4=10.

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

Примечания

  1. ^ Hopcroft, J .; Тарьян, Р. (1973). «Алгоритм 447: эффективные алгоритмы манипулирования графами». Коммуникации ACM. 16 (6): 372–378. Дои:10.1145/362248.362272.
  2. ^ Шмидт, Йенс М. (2013), «Простой тест на 2-вершинное и 2-реберное соединение», Письма об обработке информации, 113 (7): 241–244, arXiv:1209.0700, Дои:10.1016 / j.ipl.2013.01.016.
  3. ^ Westbrook, J .; Тарьян, Р. Э. (1992). «Поддержание мостовых и двусвязных компонентов в режиме онлайн». Алгоритмика. 7 (1–6): 433–464. Дои:10.1007 / BF01758773.
  4. ^ Tarjan, R .; Вишкин, У. (1985). «Эффективный параллельный алгоритм двусвязности». SIAM J. Comput. 14 (4): 862–874. CiteSeerX  10.1.1.465.8898. Дои:10.1137/0214061.CS1 maint: ref = harv (связь)
  5. ^ Гоцзин Конг и Дэвид А. Бадер (2005). «Экспериментальное исследование алгоритмов параллельных двусвязных компонентов на симметричных мультипроцессорах (SMP)». Материалы 19-го симпозиума Международной конференции IEEE по параллельной и распределенной обработке. стр. 45b. Дои:10.1109 / IPDPS.2005.100.
  6. ^ Эдвардс, Дж. А .; Вишкин, У. (2012). «Повышение скорости за счет более простого параллельного программирования для связности графов и двусвязности». Материалы Международного семинара 2012 г. по моделям программирования и приложениям для многоядерных и многоядерных процессоров - PMAM '12. п. 103. Дои:10.1145/2141702.2141714. ISBN  9781450312110.
  7. ^ Тарьян и Вишкин (1985) доверяют определение этого отношения эквивалентности Харари (1969); однако, похоже, Харари не описывает это явным образом.
  8. ^ Харари, Фрэнк (1969), Теория графов, Эддисон-Уэсли, стр. 29.
  9. ^ Харари (1969), п. 36.

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

  • Юджин К. Фрейдер (1985). «Достаточное условие для поиска с ограничением возврата». Журнал Ассоциации вычислительной техники. 32 (4): 755–761. Дои:10.1145/4221.4225.

внешняя ссылка