Двусвязный компонент
В теории графов или двусвязный компонент блок ( иногда называемый 2-связным компонентом ) является максимальным двусвязным подграфом . Любой связный граф разлагается на дерево двусвязных компонентов, называемое блочным деревом графа. Блоки прикреплены друг к другу общими вершинами, называемыми разрезанными вершинами или разделяющими вершинами или точками сочленения . В частности, разрезанная вершина — это любая вершина, удаление которой увеличивает количество компонентов связности . [1] Блок, содержащий не более одной вырезанной вершины, называется листовым блоком , он соответствует листовой вершине в дереве разрезания блоков.
Алгоритмы [ править ]
Линейный поиск в глубину по времени [ править ]
Классический последовательный алгоритм вычисления двусвязных компонентов в связном неориентированном графе принадлежит Джону Хопкрофту и Роберту Тарджану (1973). [2] Он работает в линейном времени и основан на поиске в глубину . Этот алгоритм также обозначен как задача 22-2 книги « Введение в алгоритмы» (2-е и 3-е издания).
Идея состоит в том, чтобы выполнить поиск в глубину, сохраняя при этом следующую информацию:
- глубину каждой вершины в дереве поиска в глубину (после ее посещения) и
- для каждой вершины v — наименьшая глубина среди соседей всех потомков v (включая саму v ) в дереве поиска в глубину, называемая нижней точкой .
Глубина является стандартной и должна поддерживаться во время поиска в глубину. Нижняя точка v может быть вычислена после посещения всех потомков v (т. е. непосредственно перед тем, как v поиска в глубину будет извлечена из стека ) как минимальная глубина v , глубина всех соседей v (кроме родительский элемент v в дереве поиска в глубину) и нижнюю точку всех дочерних элементов v в дереве поиска в глубину.
Ключевой факт заключается в том, что некорневая вершина v является разрезной вершиной (или точкой сочленения), разделяющей два двусвязных компонента тогда и только тогда, когда существует дочерний элемент y от v такой, что lowpoint( y ) ≥ глубина( v ) . Это свойство можно проверить, как только поиск в глубину вернет результат от каждого дочернего элемента v (т. е. непосредственно перед тем, как v будет извлечен из стека поиска в глубину), и если оно истинно , v разделяет граф на различные двусвязные компоненты. Это можно представить, вычислив один двусвязный компонент из каждого такого y (компонент, который содержит y, будет содержать поддерево y плюс v ), а затем удалив поддерево y из дерева.
Корневую вершину необходимо обрабатывать отдельно: она является вырезанной вершиной тогда и только тогда, когда у нее есть как минимум два дочерних элемента в дереве DFS. Таким образом, достаточно просто построить по одному компоненту из каждого дочернего поддерева корня (включая корень).
Псевдокод [ править ]
GetArticulationPoints(i, d)
visited[i] := true
depth[i] := d
low[i] := d
childCount := 0
isArticulation := false
for each ni in adj[i] do
if not visited[ni] then
parent[ni] := i
GetArticulationPoints(ni, d + 1)
childCount := childCount + 1
if low[ni] ≥ depth[i] then
isArticulation := true
low[i] := Min (low[i], low[ni])
else if ni ≠ parent[i] then
low[i] := Min (low[i], depth[ni])
if (parent[i] ≠ null and isArticulation) or (parent[i] = null and childCount > 1) then
Output i as articulation point
Обратите внимание, что термины «потомок» и «родитель» обозначают отношения в дереве DFS, а не в исходном графе.
Другие алгоритмы [ править ]
Простая альтернатива приведенному выше алгоритму использует цепные разложения , которые представляют собой специальные ушные разложения, зависящие от DFS -деревьев. [3] цепные разложения можно вычислить за линейное время С помощью этого правила обхода . Пусть C — цепное разложение G. группы Тогда G 2-вершинно связен тогда и только тогда, когда G имеет минимальную степень 2 и C 1 — единственный цикл в C . Это немедленно дает тест 2-связности за линейное время и может быть расширено для перечисления всех разрезанных вершин G за линейное время, используя следующее утверждение: Вершина v в связном графе G (с минимальной степенью 2) является разрезаемой вершиной, если и только если v инцидентен мосту или v является первой вершиной цикла в C – C 1 . Список вырезанных вершин можно использовать для создания блочного дерева за G линейное время.
В онлайн- версии задачи вершины и ребра добавляются (но не удаляются) динамически, а структура данных должна поддерживать двусвязные компоненты. Джеффри Уэстбрук и Роберт Тарджан (1992) [4] разработал эффективную структуру данных для этой проблемы на основе структур данных с непересекающимися множествами . В частности, он обрабатывает n вершин и добавление m ребер за общее время O ( mα добавление ( m , n )) , где α — обратная функция Аккермана . Эта временная граница оказалась оптимальной.
Узи Вишкин и Роберт Тарьян (1985) [5] разработал параллельный алгоритм на CRCW PRAM , который работает за время O (log n ) на n + m процессорах.
Связанные структуры [ править ]
Отношение эквивалентности [ править ]
Можно определить бинарное отношение на ребрах произвольного неориентированного графа, согласно которому два ребра e и f связаны тогда и только тогда, когда либо e = f , либо граф содержит простой цикл через e и f . Каждое ребро связано само с собой, а ребро e связано с другим ребром f тогда и только тогда, когда f связано таким же образом с e . Менее очевидно, что это транзитивное отношение : если существует простой цикл, содержащий ребра e и f , и другой простой цикл, содержащий ребра f и g , то можно объединить эти два цикла, чтобы найти простой цикл через e и g . Следовательно, это отношение эквивалентности , и его можно использовать для разделения ребер на классы эквивалентности, подмножества ребер со свойством, что два ребра связаны друг с другом тогда и только тогда, когда они принадлежат одному и тому же классу эквивалентности. Подграфы, образованные ребрами каждого класса эквивалентности, являются двусвязными компонентами данного графа. Таким образом, двусвязные компоненты разбивают ребра графа; однако они могут иметь общие вершины друг с другом. [6]
Блок-график [ править ]
Граф блоков данного графа G — это граф пересечений его блоков. Таким образом, он имеет одну вершину для каждого блока G и ребро между двумя вершинами всякий раз, когда соответствующие два блока имеют общую вершину. Граф H является блочным графом другого графа G в точности тогда, когда все блоки H являются полными подграфами. Графы H с этим свойством известны как блочные графы . [7]
Вырубленное дерево [ править ]
Точка разреза , вершина разреза или точка сочленения графа G — это вершина, которая является общей для двух или более блоков. Структура блоков и точек разреза связного графа может быть описана деревом, называемым деревом разреза блоков или BC-деревом . Это дерево имеет вершину для каждого блока и каждой точки сочленения данного графа. В дереве вырезания блоков есть ребро для каждой пары блоков и точки сочленения, принадлежащей этому блоку. [8]
Блоки :
б 1 = [1,2]
б 2 = [2,3,4]
б 3 = [2,5,6,7]
б 4 = [7,8,9,10,11]
б 5 = [8,12,13,14,15]
б 6 = [10,16]
б 7 = [10,17,18]
Точки разреза:
с 1 = 2
с 2 = 7
с 3 = 8
с 4 = 10
См. также [ править ]
- Трехсвязный компонент
- Мост (теория графов)
- Одиночный вход и один выход Противоположная часть двусвязных компонентов в ориентированных графах
Примечания [ править ]
- ^ АЛЬ-ТАИ, МОХАММЕД ЗУХАЙР. КАДРИ, СЕЙФЕДИН (2019). «3. Теория графов». PYTHON ДЛЯ ГРАФИЧЕСКОГО И СЕТЕВОГО АНАЛИЗА . Спрингер. ISBN 978-3-319-85037-5 . OCLC 1047552679 .
Cut-вершина — это вершина, при удалении которой количество компонентов сети увеличивается.
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Хопкрофт, Дж.; Тарьян, Р. (1973). «Алгоритм 447: эффективные алгоритмы манипуляции графами» . Коммуникации АКМ . 16 (6): 372–378. дои : 10.1145/362248.362272 .
- ^ Шмидт, Йенс М. (2013), «Простой тест на связность 2 вершин и 2 ребер», Information Processing Letters , 113 (7): 241–244, arXiv : 1209.0700 , doi : 10.1016/j.ipl .2013.01.016 .
- ^ Уэстбрук, Дж.; Тарьян, Р.Э. (1992). «Поддержание мостовых и двусвязных компонентов в рабочем состоянии». Алгоритмика . 7 (1–6): 433–464. дои : 10.1007/BF01758773 .
- ^ Тарьян, Р.; Вишкин Ю. (1985). «Эффективный алгоритм параллельной бисвязности». СИАМ Дж. Компьютер. 14 (4): 862–874. CiteSeerX 10.1.1.465.8898 . дои : 10.1137/0214061 .
- ^ Тарьян и Вишкин (1985) приписывают определение этого отношения эквивалентности Харари (1969) ; однако Харари, похоже, не описывает это явно.
- ^ Харари, Фрэнк (1969), Теория графов , Аддисон-Уэсли, с. 29 .
- ^ Больной (1969) , с. 36.
Ссылки [ править ]
- Юджин К. Фрейдер (1985). «Достаточное условие для поиска с возвратом» . Журнал Ассоциации вычислительной техники . 32 (4): 755–761. дои : 10.1145/4221.4225 .