В теории графов двусвязный компонент или блок ( иногда называемый 2-связным компонентом ) является максимальным двусвязным подграфом . Любой связный граф распадается на дерево двусвязных компонентов, называемое деревом блочного разреза графа. Блоки прикреплены друг к другу в общих вершинах, называемых вершинами разреза или разделяющими вершинами или точками сочленения . В частности, вершина разреза — это любая вершина, удаление которой увеличивает количество связных компонентов . [1] Блок, содержащий не более одной вершины разреза, называется листовым блоком , он соответствует листовой вершине в дереве блочного разреза.
Классический последовательный алгоритм для вычисления двусвязных компонентов в связном неориентированном графе принадлежит Джону Хопкрофту и Роберту Тарьяну (1973). [2] Он работает за линейное время и основан на поиске в глубину . Этот алгоритм также описан как задача 22-2 Введения в алгоритмы (как 2-го, так и 3-го издания).
Идея состоит в том, чтобы выполнить поиск в глубину, сохраняя при этом следующую информацию:
Глубина является стандартной для поддержания во время поиска в глубину. Нижняя точка v может быть вычислена после посещения всех потомков v (т. е. непосредственно перед тем, как v будет вытолкнута из стека поиска в глубину ) как минимум глубины v , глубины всех соседей v (кроме родителя v в дереве поиска в глубину) и нижней точки всех потомков v в дереве поиска в глубину.
Ключевым фактом является то, что некорневая вершина v является вершиной разреза (или точкой сочленения), разделяющей два двусвязных компонента, если и только если есть дочерний элемент y v такой , что lowpoint( y ) ≥ depth( v ) . Это свойство можно проверить, как только поиск в глубину вернет каждый дочерний элемент v (т. е. непосредственно перед тем, как v будет вытолкнут из стека поиска в глубину), и если true , v разделяет граф на различные двусвязные компоненты. Это можно представить, вычислив один двусвязный компонент из каждого такого y (компонент, содержащий y , будет содержать поддерево y , плюс v ), а затем удалив поддерево y из дерева.
Корневая вершина должна обрабатываться отдельно: она является вершиной разреза тогда и только тогда, когда у нее есть по крайней мере два потомка в дереве DFS. Таким образом, достаточно просто построить один компонент из каждого дочернего поддерева корня (включая корень).
GetArticulationPoints(i, d) посетил[i] := true глубина[i] := d низкий[i] := d Количество детей := 0 isArticulation := ложь для каждого ni в adj[i] сделать если не посетил[ni] тогда родитель[ni] := i ПолучитьТочкиАртикуляции(ni, d + 1) Количество детей := Количество детей + 1 если low[ni] ≥ depth[i] , то isArticulation := true низкий[i] := Мин (низкий[i], низкий[ni]) иначе если ni ≠ parent[i] тогда низкий[i] := Мин (низкий[i], глубина[ni]) если (parent[i] ≠ null и isArticulation) или (parent[i] = null и childCount > 1) тогда Выход i как точка сочленения
Обратите внимание, что термины «ребенок» и «родитель» обозначают отношения в дереве 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]
при удалении которой число компонентов сети увеличивается.
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )