В теории графов , A двусвязные компоненты (иногда известные как 2-связная компонента ) являются максимальным двухсвязным подграфом . Любой связный граф распадается на дерево двусвязных компонентов, которое называется блочно-разрезным деревом графа. Блоки прикреплены друг к другу в общих вершинах, называемых вершинами разреза или точками сочленения . В частности, разрезанная вершина - это любая вершина, удаление которой увеличивает количество связанных компонентов .
Алгоритмы
Линейный поиск по времени в глубину
Классический последовательный алгоритм для вычисления двусвязных компонентов в связном неориентированном графе разработан Джоном Хопкрофтом и Робертом Тарьяном (1973). [1] Он работает с линейным временем и основан на поиске в глубину . Этот алгоритм также обозначен как проблема 22-2 Введение в алгоритмы (как 2-е, так и 3-е издания).
Идея состоит в том, чтобы выполнить поиск в глубину, сохраняя при этом следующую информацию:
- глубина каждой вершины в дереве поиска в глубину (после посещения) и
- для каждой вершины 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, а не в исходном графе.
Другие алгоритмы
Простая альтернатива вышеупомянутому алгоритму использует цепные разложения , которые представляют собой специальные разложения на ухо, зависящие от 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]
Смотрите также
Заметки
- ^ Hopcroft, J .; Тарьян, Р. (1973). «Алгоритм 447: эффективные алгоритмы манипулирования графами». Коммуникации ACM . 16 (6): 372–378. DOI : 10.1145 / 362248.362272 .
- ^ Шмидт, Йенс М. (2013), «Простой тест на связность с двумя вершинами и двумя ребрами », Письма об обработке информации , 113 (7): 241–244, arXiv : 1209.0700 , doi : 10.1016 / j.ipl .2013.01.016.
- ^ Westbrook, J .; Tarjan, RE (1992). «Поддержание мостовых и двусвязных компонентов в оперативном режиме». Алгоритмика . 7 (1–6): 433–464. DOI : 10.1007 / BF01758773 .
- ^ Tarjan, R .; Вишкин, У. (1985). «Эффективный параллельный алгоритм двусвязности». SIAM J. Comput. 14 (4): 862–874. CiteSeerX 10.1.1.465.8898 . DOI : 10.1137 / 0214061 .
- ^ Гоцзин Конг и Дэвид А. Бадер (2005). «Экспериментальное исследование алгоритмов параллельных двусвязных компонентов на симметричных мультипроцессорах (SMP)». Труды 19-го симпозиума Международной конференции IEEE по параллельной и распределенной обработке . стр. 45b. DOI : 10.1109 / IPDPS.2005.100 .
- ^ Эдвардс, JA; Вишкин, У. (2012). «Повышение скорости за счет более простого параллельного программирования для связности графов и двусвязности». Труды Международного семинара 2012 года по моделям программирования и приложениям для многоядерных и многоядерных процессоров - PMAM '12 . п. 103. DOI : 10,1145 / 2141702,2141714 . ISBN 9781450312110.
- ^ Тарджан и Вишкин (1985) приписывают определение этого отношения эквивалентности Харари (1969) ; однако, похоже, Харари не описывает это явным образом.
- ^ Харари, Франк (1969), теория графов , Addison-Wesley, p. 29.
- ^ Harary (1969) , стр. 36.
Рекомендации
- Юджин К. Фрейдер (1985). «Достаточное условие для поиска с ограничением возврата». Журнал Ассоциации вычислительной техники . 32 (4): 755–761. DOI : 10.1145 / 4221.4225 .
Внешние ссылки
- Реализация двухсвязных компонентов на C ++