Двусоединенный компонент
-
Двусвязные компоненты и блочное дерево
- Двусвязный компонент — максимальный двусвязный подграф графа.
- Связный граф распадается на дерево двусвязных компонентов (блочное дерево).
- Блоки соединяются в общих вершинах (вырезанные вершины).
-
Алгоритмы для вычисления двусвязных компонентов
- Линейный поиск в глубину: алгоритм Хопкрофта и Тарьяна (1973).
- Цепные разложения: альтернатива линейному времени.
- Онлайн-версия задачи: структура данных Уэстбрука и Тарьяна (1992).
- Параллельный алгоритм Вишкина и Тарьяна (1985).
-
Связанные структуры
- Отношение эквивалентности: разделение ребер на классы эквивалентности.
- Блок-график: граф пересечений блоков графа.
- Вырубленное из блоков дерево: дерево, описывающее структуру блоков и точек отсечения.