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

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

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

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

Формула

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

Схема Мосты CD и DE выделены цветом

Рёбра треугольника лежат на цикле

Обозначения

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

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

Используется неориентированный граф и полный лес DFS. При завершении ребёнка его low передают родителю; обратное ребро обновляет low временем входа другого конца. Родительское ребро исключают по идентификатору. Для простого графа достаточно исключения родительской вершины, но при параллельных рёбрах это неверно.

Ограничения

Критерий относится к рёбрам дерева DFS; нет необходимости отдельно проверять каждое обратное ребро. Для ориентированных графов задача сильных мостов другая. Петля не является мостом, а два параллельных ребра не могут быть мостами по отдельности. Не следует применять строгий критерий моста к точкам сочленения.

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

Удаление ребра дерева между родителем v и ребёнком u отделило бы всё поддерево u, если у него нет другой связи наружу. В неориентированном DFS такая связь обнаруживается обратным ребром из поддерева к предку. Значение low суммирует нужную информацию и избавляет от повторного просмотра всего поддерева.

В начале low(u) равно времени входа в u. Для обратного ребра берут минимум с временем входа его другого конца. После возврата из ребёнка берут минимум с low этого ребёнка. Таким образом, к моменту проверки родительского ребра уже известна лучшая обходная связь всей нижней части дерева.

Если low(u) меньше времени входа в v, поддерево связано с более ранним предком. Если равно, есть обходная связь непосредственно к v. В обоих случаях удаление одного дерева-ребра не разрывает связность. Лишь строгое неравенство low(u) > t_in(v) означает отсутствие такого обхода.

Ребро, лежащее на цикле, не может быть мостом: после его удаления остаётся путь по остальной части цикла. Это даёт независимый способ проверить ответ на небольшом графе. Напротив, в дереве циклов нет и любое ребро является мостом.

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

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

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

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

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

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

Используется критерий мостов на основе DFS и минимальных достижимых времён входа. Он входит в семейство линейных алгоритмов анализа связности, связанное с работами Тарьяна. Точный программный вариант здесь уточнён для идентификаторов рёбер, чтобы корректно различать параллельные связи.

Пример

В простом неориентированном графе есть треугольник AB, BC, CA и хвост C–D–E. DFS из A по алфавиту даёт времена входа A = 1, B = 2, C = 3, D = 4, E = 5. Обратное ребро C–A снижает low(C) до 1; затем low(B) также становится 1. У E нет обхода: low(E) = 5 > t_in(D) = 4, значит DE — мост. У D значение low(D) = 4 > t_in(C) = 3, значит CD тоже мост. Для BC условие 1 > 2 неверно, для AB условие 1 > 1 неверно. Удаление CD увеличивает число компонент с 1 до 2, а удаление любого ребра треугольника оставляет граф связным. Ответ: два моста CD и DE.

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

Не заменяйте > на ≥: обратная связь к родителю уже спасает ребро от статуса моста. Не обновляйте low по времени выхода. Не игнорируйте все рёбра к родителю в мультиграфе. Не переносите критерий без изменений на ориентированные дуги. Не проверяйте только первую компоненту несвязного графа.

Практика

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

Дерево

Условие. В связном дереве 7 вершин. Сколько мостов?

Решение. У дерева 7−1 = 6 рёбер. Для любого ребра отсутствует альтернативный путь между концами, иначе возник бы цикл.

Ответ. 6 мостов.

Параллельная связь

Условие. Две вершины соединены двумя разными параллельными рёбрами. Есть ли мост?

Решение. После удаления любого одного ребра второе сохраняет связность. Исключать при DFS нужно только входное ребро, а другое учитывать как обход.

Ответ. Мостов нет.

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

https://algs4.cs.princeton.edu/41graph/Bridge.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\ne root:\quad v\text{ — точка сочленения}\iff\exists u\text{ — ребёнок}:low(u)\ge t_{in}(v)$

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