Двозв'язна компонента
 | Було запропоновано приєднати цю статтю або розділ до Шарнір (теорія графів), але, можливо, це варто додатково обговорити. Пропозиція з травня 2016. |
 | Ця стаття є сирим перекладом з іншої мови. Можливо, вона створена за допомогою машинного перекладу або перекладачем, який недостатньо володіє обома мовами. (березень 2016) |
В теорії графів, двозв'язний компонент (також відомий як блок або 2-приєднаний компонент) є максимальним двозв'язним підграфом. Будь-який зв'язний граф розпадається в дерево двозв'язних компонентів, званих блок-дерева графу. Блоки скріплені один з одним в загальних вершинах, званих зрізані вершини або точки шарнірного з'єднання. Зокрема, скороченна вершина є будь-яка вершина видалення якої збільшує число підключених компонентів.
Класичний послідовний алгоритм[en] для обчислення двозв'язних компонентів в зв'язний неорієнтований граф було обумовлено Джоном Хопкрофтом і Робертом Тар'яном(1973).[1] Він працює за лінійний час, а також ґрунтується на пошуку в глибину. Цей алгоритм також змальованний як проблема 22-2 "Введення в Алгоритми" (як 2-го і 3-го видання). Ідея полягає в тому, щоб запустити пошук в глибину, зберігаючи при цьому наступну інформацію:
- глибина кожної вершини в глибину першого дерева пошуку (як тільки його відвідали),
- і для кожної вершини V, найменша глибина сусідів всіх нащадків V в глибину першого дерева пошуку, називається низькою точкою.
Глибина є стандартною під час пошуку в глибину. Низька точка 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]
- ↑ Hopcroft, J.; Tarjan, R. (1973). Algorithm 447: efficient algorithms for graph manipulation. Communications of the ACM. 16 (6): 372—378. doi:10.1145/362248.362272.
- ↑ Schmidt (2013), A Simple Test on 2-Vertex- and 2-Edge-Connectivity, Information Processing Letters, 113 (7): 241—244, doi:10.1016/j.ipl.2013.01.016.
- ↑ Westbrook, J.; Tarjan, R. E. (1992). Maintaining bridge-connected and biconnected components on-line. Algorithmica. 7: 433—464. doi:10.1007/BF01758773.
- ↑ Tarjan, R.; Vishkin, U. (1985). An Efficient Parallel Biconnectivity Algorithm. SIAM J. Comput. 14 (4): 862—874. doi:10.1137/0214061.
- ↑ Guojing Cong and David A. Bader, (2005). An Experimental Study of Parallel Biconnected Components Algorithms on Symmetric Multiprocessors (SMPs). Proceedings of the 19th IEEE International Conference on Parallel and Distributed Processing Symposium. с. 45b. doi:10.1109/IPDPS.2005.100.
- ↑ Edwards, J. A.; Vishkin, U. (2012). Better speedups using simpler parallel programming for graph connectivity and biconnectivity. Proceedings of the 2012 International Workshop on Programming Models and Applications for Multicores and Manycores - PMAM '12. с. 103. doi:10.1145/2141702.2141714. ISBN 9781450312110.
- ↑ Tarjan та Vishkin, (1985) credit the definition of this equivalence relation to Harary, (1969); however, Harary does not appear to describe it in explicit terms.
- ↑ Harary, Frank (1969), Graph Theory, Addison-Wesley, с. 29.
- ↑ Harary, (1969), p. 36.
- The tree of the biconnected components Java implementation [Архівовано 29 квітня 2011 у Wayback Machine.] in the jBPT library (see BCTree class).
- C implementation of Biconnected Components [Архівовано 20 листопада 2016 у Wayback Machine.]