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

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

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

Линейный поиск по глубине времени [ править ]

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

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

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

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

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

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

Псевдокод [ править ]

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

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

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


Другие алгоритмы [ править ]

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

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

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

Связанные структуры [ править ]

Отношение эквивалентности [ править ]

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

Блочная диаграмма [ править ]

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

Блокированное дерево [ править ]

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

Граф и его блочное дерево.
Блоки: b 1 = [1,2], b 2 = [2,3,4], b 3 = [2,5,6,7], b 4 = [7,8,9,10,11 ], b 5 = [8,12,13,14,15], b 6 = [10,16] и b 7 = [10,17,18];
точки отсечения: c 1 = 2, c 2 = 7, c 3 = 8 и c 4 = 10.

См. Также [ править ]

  • Трехкомпонентный компонент
  • Мост (теория графов)

Заметки [ править ]

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

Ссылки [ править ]

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

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

  • Реализация на C ++ двусвязных компонентов