Информатика / Алгоритмы и анализ данных

Точки сочленения: критерий low и отдельное правило корня

Точка сочленения — вершина, удаление которой вместе с инцидентными рёбрами увеличивает число компонент связности. Для некорневой вершины DFS использует нестрогое сравнение low ребёнка с временем входа.

Опубликовано: 21 октября 2026 г.Обновлено: 21 октября 2026 г.

Формула

v\ne root:\quad v\text{ — точка сочленения}\iff\exists u\text{ — ребёнок}:low(u)\ge t_{in}(v)

Схема Общая вершина C: мостов нет

Удаление C разделяет граф на AB и DE

Обозначения

$v$: проверяемая некорневая вершина DFS, не применяется
$u$: ребёнок v в дереве обхода, не применяется
$t_{in}(v)$: время входа в проверяемую вершину, целый счётчик
$low(u)$: минимальный номер входа, доступный из поддерева u через спуск и не более одного обратного ребра, целый счётчик
$root$: корень одного дерева полного леса DFS, не применяется

Условия применения

Граф неориентированный; нужен полный DFS с корректным вычислением low. Для некорневой вершины достаточно одного ребёнка с low(u) ≥ t_in(v). Для корня критерий отдельный: он является точкой сочленения тогда и только тогда, когда у него не менее двух детей именно в дереве обхода.

Ограничения

Число детей DFS не совпадает со степенью вершины исходного графа. Нестрогое сравнение нельзя заменить строгим критерием моста. Удаление изолированной вершины уменьшает число компонент и не делает её точкой сочленения. Ориентированные графы и сильные точки сочленения требуют другого анализа.

Подробное объяснение

Для некорневой вершины существует часть дерева над ней и поддеревья детей ниже. После удаления вершины v ребёнок u сохранит связь с верхней частью только при наличии обратного пути к строгому предку v. Именно это проверяет значение low(u). Связь обратно к самой v уже не помогает: удаляемая вершина исчезает вместе со всеми рёбрами.

Поэтому условие имеет знак ≥, а не >. Равенство означает, что обход из поддерева доходит до v, но не выше. Родительское ребро может входить в цикл и не быть мостом, однако удаление общей вершины разорвёт соединение частей. Это ключевое различие между отказом ребра и отказом вершины.

У корня нет верхней части дерева, поэтому прежний довод неприменим. Если у корня один ребёнок, все остальные вершины его компоненты лежат в одном поддереве и после удаления корня остаются связными рёбрами дерева. При двух или более детях между поддеревьями не может быть ребра: иначе DFS открыл бы их в одной ветви.

Пример двух треугольников с общей вершиной показывает разницу особенно ясно. Каждое ребро лежит на цикле, поэтому мостов нет. Но общая вершина — единственный переход между треугольниками, и её удаление создаёт две компоненты.

Каждую подходящую вершину нужно помечать один раз, даже если условие выполнено для нескольких детей. В несвязном графе отдельное правило корня применяется к каждому дереву леса. При списках смежности общий проход и обновления low имеют сложность O(|V|+|E|).

Как пользоваться формулой

Постройте полный лес DFS, сохраняя время входа, low, родителя и количество детей в дереве для каждой вершины.
Для каждого некорневого родителя после возврата ребёнка проверьте low ребёнка ≥ времени входа родителя.
Проверьте каждый корень отдельно: нужны как минимум два DFS-ребёнка, а не два соседа в исходном графе.
Удалите найденную вершину на небольшом тестовом графе и пересчитайте компоненты, не считая удалённую вершину изолированной.

Историческая справка

Анализ точек сочленения связан с задачей двусвязности: можно ли разорвать компоненту удалением одной вершины. В статье Тарьяна 1972 года поиск в глубину используется для линейных структурных алгоритмов, включая работу с двусвязными компонентами неориентированного графа. Современная реализация Biconnected в Принстонском курсе отдельно проверяет некорневое условие и количество детей корня; это различие отражает саму структуру дерева, а не техническую поправку к программе. Исторический переход от многократного пересчёта связности к одному обходу состоит в сохранении информации о доступных предках. В учебной записи она сведена к low, что позволяет объяснить и нестрогое сравнение, и пример двух циклов с общей вершиной.

Историческая линия формулы

Критерий точек сочленения относится к линейным DFS-методам анализа двусвязности, исторически связанным с работами Тарьяна. Приведённая реализация различает корень и остальные вершины. Эту задачу нельзя подменять поиском мостов: критичным элементом здесь служит вершина вместе со всеми её рёбрами.

Пример

Пусть граф состоит из треугольников A–B–C–A и C–D–E–C. DFS из A по алфавиту даёт входы A = 1, B = 2, C = 3, D = 4, E = 5. У C есть обратное ребро к A, а у E — к C. После возврата low(E) = low(D) = 3. Для некорневой C выполнено low(D) = 3 ≥ t_in(C) = 3, поэтому C — точка сочленения. У B значение low(C) = 1 < 2, значит B не подходит. Корень A имеет одного ребёнка B в дереве DFS, хотя в исходном графе два соседа, поэтому A не является точкой сочленения. Удаление C оставляет компоненты {A,B} и {D,E}; удаление любого ребра сохраняет связность, то есть мостов здесь нет.

Частая ошибка

Не используйте для точки сочленения строгое сравнение из задачи о мостах. Не считайте всех соседей детьми дерева DFS. Не применяйте некорневой критерий к корню. Не увеличивайте ответ несколько раз за одну вершину с несколькими подходящими детьми. Не оставляйте удалённую вершину в пересчёте компонент как отдельную изолированную.

Практика

Задачи с решением

Корень звезды

Условие. В графе A–B, A–C, A–D старт DFS из A. Какие точки сочленения?

Решение. У корня A три DFS-ребёнка; его удаление оставляет три изолированные вершины вместо одной компоненты. Удаление любого листа связность остальных не нарушает.

Ответ. Только A.

Один цикл

Условие. В цикле A–B–C–D–A есть ли точки сочленения?

Решение. После удаления любой вершины остаётся путь из трёх вершин. Число компонент остаётся равным одному, поэтому точек сочленения нет.

Ответ. Нет.

Дополнительные источники

https://algs4.cs.princeton.edu/41graph/Biconnected.java.html
https://www.cs.cmu.edu/~cdm/resources/Tarjan1972-sccs.pdf
https://algs4.cs.princeton.edu/41graph/index.php

Связанные формулы

Информатика

Поиск в глубину: дерево обхода и времена входа и выхода

$u\text{ — предок }v\iff t_{in}(u)<t_{in}(v)<t_{out}(v)<t_{out}(u),\quad u\ne v$

Поиск в глубину, или DFS, полностью исследует одну ветвь графа перед возвратом к следующей. Времена входа и выхода образуют вложенные интервалы и позволяют проверять родство в дереве обхода.

Информатика

Топологическая сортировка Кана по входящим степеням

$d_{in}(v)\leftarrow d_{in}(v)-1\quad\text{при удалении дуги }u\to v;\qquad |L|=|V|\iff G\text{ ацикличен}$

Алгоритм Кана упорядочивает вершины ориентированного графа, последовательно выбирая вершину без входящих дуг. Если вывести все вершины не удалось, оставшаяся часть содержит ориентированный цикл.

Информатика

Сильные компоненты: два обхода алгоритма Косарайю

$u\sim v\iff(u\leadsto v)\land(v\leadsto u),\qquad T=O(|V|+|E|)$

Сильная компонента ориентированного графа объединяет вершины, достижимые друг из друга в обоих направлениях. Алгоритм Косарайю находит такие группы двумя обходами в глубину с разворотом всех дуг.

Информатика

Мосты графа: критерий через времена входа и low

$(v,u)\text{ — мост}\iff low(u)>t_{in}(v),\quad u\text{ — ребёнок }v\text{ в DFS}$

Мост — ребро неориентированного графа, удаление которого увеличивает число компонент связности. DFS обнаруживает его, если поддерево ребёнка не имеет обходного ребра к родителю или его предкам.