![]() | Було запропоновано приєднати цю статтю або розділ до Шарнір (теорія графів), але, можливо, це варто додатково обговорити. Пропозиція з травня 2016. |
![]() | Ця стаття є сирим перекладом з іншої мови. Можливо, вона створена за допомогою машинного перекладу або перекладачем, який недостатньо володіє обома мовами. (березень 2016) |
В теорії графів, двозв'язний компонент (також відомий як блок або 2-приєднаний компонент) є максимальним двозв'язним підграфом. Будь-який зв'язний граф розпадається в дерево двозв'язних компонентів, званих блок-дерева графу. Блоки скріплені один з одним в загальних вершинах, званих зрізані вершини або точки шарнірного з'єднання. Зокрема, скороченна вершина є будь-яка вершина видалення якої збільшує число підключених компонентів.
Класичний послідовний алгоритм[en] для обчислення двозв'язних компонентів в зв'язний неорієнтований граф було обумовлено Джоном Хопкрофтом і Робертом Тар'яном(1973).[1] Він працює за лінійний час, а також ґрунтується на пошуку в глибину. Цей алгоритм також змальованний як проблема 22-2 "Введення в Алгоритми" (як 2-го і 3-го видання). Ідея полягає в тому, щоб запустити пошук в глибину, зберігаючи при цьому наступну інформацію:
Глибина є стандартною під час пошуку в глибину. Низька точка V може бути обчислена після відвідування всіх нащадків V (тобто, безпосередньо перед тим я V буде виштовхнене з глибини першого пошуку) як мінімум глибини V, глибина всіх сусідів V (крім батька V в глибині першого дерева пошуку) і низька точка всіх дітей V в глибину першого дерева пошуку.
Ключ у тому, що некоренева вершина v є зрізанною вершиною(або точкою артикуляції), що розділяє два двохзв'язних компоненти тоді і тільки тоді, коли є дитина Y з V така, що низька точка (Y) глибина ≥ (V). Цю властивість можна буде перевірити, як тільки пошук в глибину повернувся з кожної дитини V (тобто, безпосередньо перед тим як V виштовхнеться з глибини першого пошуку), і якщо це правда, V відокремить граф на різні двохзв'язні компоненти. Це може бути представлено за допомогою обчислення одного двохзв'язного компонента з кожного такого Y (компонент, який містить Y буде містити піддерево Y, плюс V), а потім видалить піддерево Y з дерева.
Коренева вершина повинна бути оброблена окремо: це зрізана вершина тоді і тільки тоді, коли вона має по хоча б , двох дітей. Таким чином, досить просто побудувати один компонент з кожного дочірнього піддерева маршруту (включаючи корінь).
GetArticulationPoints(i, d)
visited[i] = true
depth[i] = d
low[i] = d
childCount = 0
isArticulation = false
for each ni in adj[i]
if not visited[ni]
parent[ni] = i
GetArticulationPoints(ni, d + 1)
childCount = childCount + 1
if low[ni] >= depth[i]
isArticulation = true
low[i] = Min(low[i], low[ni])
else if ni <> parent[i]
low[i] = Min(low[i], depth[ni])
if (parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1)
Output i as articulation point
Проста альтернатива вище представленного алгоритму використовує ланцюги розкладання, які представляють собою спеціальні "розкладальні вуха" в залежності від ДФС-дерев. [2] Ланцюгові розкладання можуть бути обчислені за лінійний час цим правилом переміщення.[2]
Нехай С розкладання ланцюга G. Тоді G є 2-вершинним-зв'язковим тоді і тільки тоді, коли G має мінімальну ступінь 2 і C1 є єдиним циклом в С. Це дає відразу тест 2-зв'язність в лінійний час і може бути продовжений перелічити всі зрізані вершини G в лінійному часу, використовуючи наступну заяву: вершина v в зв'язковому графі G (з мінімальним ступенем 2) є розрізом вершина тоді і тільки тоді, коли v падає на мосту або V є перша вершина цикл в с - С1. Список зрізаних вершин може бути використаний для створення блок-CUT дерево G в лінійному часу.
В інтернет-версії цього завдання, вершини і ребра додаються (але не видаляються) динамічно, а структура даних повинна підтримувати двузв'язні компоненти. Джеффрі Вестбрук і Роберт Тар'ян (1992) [3] розробили ефективну структуру даних для цього завдання, засновану на непересічному наборі структур даних. Зокрема, він обробляє n вершин доповнення і m крайових доповненнь в O(m α(m, n)), де α є зворотнею функцією Аккермана.
Узі Вішкін[en] і Роберт Тар'ян (1985) [4] розробили паралельний алгоритм на CRCW PRAM, який працює в O(log n) з m + n процесорами. Guojing Cong і David A. Bader[en] (2005) [5] розробили алгоритм, який досягає в прискорення у 5 разів з 12 процесорами на МСС. Прискорення, що перевищують 30 на основані на алгоритмі Tarjan-Vishkin були розроблені James A. Edwards та Uzi Vishkin (2012).[6]
Можна визначити бінарне відношення на краях довільного неорієнтованого графу, відповідно до якого два ребра E і F пов'язані тоді і тільки тоді, коли або E = F або граф містить простий цикл як через E і F. Кожне ребро має відношення до себе, а ребро E пов'язано з іншим краєм F тоді і тільки тоді, коли F пов'язана таким же чином як і E, це транзитивне ставлення: якщо існує простий цикл, що містить ребра E і F, і ще один простий цикл, що містить ребра F і G, то можна об'єднати ці два цикли, щоб знайти простий цикл через E і F. Таким чином, це відношення еквівалентності, і воно може бути використано для поділу краю на класи еквівалентності, підмножини ребер з такою властивістю, що два ребра пов'язані одне з одним, якщо і тільки якщо вони належать до одного класу еквівалентності. Підграфи, утворені ребрами в кожному класі еквівалентності є двозв'язними компонентами даного графу. Таким чином, двозв'язні компоненти розбивають ребра графу; проте, вони можуть використовувати спільні вершини одине з одного.[7]
Блок граф заданого графу G є графом перетинів його блоків. Таким чином, він має одну вершину для кожного блоку G, а ребро між двома вершинами, коли відповідні два блоки мають загальну вершину. Граф Н є блок-діаграмою іншого графу G , коли всі блоки H є повними підграфами. Графи H з цією властивістю відомі як блок-графи. [8][8]
Зрізана точка, зрізані вершини, або артикуляція графу G є вершиною, яка поділяється на два або більше блоків. Структуру блоків і зрізаних точок графу можна описати за допомогою дерева яке називається зрізаним деревом або BC-деревом. Це дерево має вершину для кожного блоку і для кожної точки з'єднання даного графу. Існує ребро в зрізаному дереві для кожної пари блоку і артикуляційної точки, що належить до цього блоку.[9]