Мосты и точки сочленения
Также: Bridges and articulation points · cut edges · cut vertices · мосты графа · шарниры · двусвязные компоненты · biconnected components · блоки графа
Мост — улица, без которой часть города остаётся отрезанной; точка сочленения — такой же перекрёсток. Перебирать улицы по одной и каждый раз проверять связность — квадрат от размера сети. Один поиск в глубину находит всё сразу: хватает двух чисел на вершину — когда в неё вошли и как высоко можно подняться из её поддерева.
В сентябре 2024 года участок улицы Керей-Жанибек хандар — дороги к катку «Медеу» — несколько ночей подряд перекрывали на ремонт, с одиннадцати вечера до шести утра; пропускали только скорую и другие экстренные службы. Объехать было нельзя: в ущелье ведёт одна дорога. Таких улиц в большом городе тысячи, просто обычно за ними тупик, а не долина. Ниже — улицы Алматы из OpenStreetMap, от вокзала Алматы-2 до Большого Алматинского озера, и один проход поиска в глубину, который находит все такие улицы разом. Нажмите на улицу, чтобы её перекрыть, или на кнопку под картой — там самые крупные находки.
Красным горят две дороги в горы. Проспект Дулати, переходящий в улицу Алма-Арасан, — единственный въезд в Большое Алматинское ущелье: перекройте его на выезде из города, и без связи с городом останутся 128 перекрёстков и 44 км улиц вместе с Алма-Арасаном и дорогой к озеру. Улица Керей-Жанибек хандар держит столько же перекрёстков, 128, и 32,7 км улиц до «Медеу». В самом городе картина другая. Из 3005 мостов 2201 ведёт к единственному тупиковому перекрёстку, остальные отрезают двор, переулок, коттеджный посёлок. Перекройте почти любую улицу сетки в центре — найдётся объезд в пару кварталов, он появится синим.
Идея
Две вещи, которые ищет эта статья, определяются одинаково. Мост — ребро, после удаления которого граф распадается: какие-то две вершины, связанные раньше, больше не связаны. Точка сочленения — такая же вершина. Ребро — мост ровно тогда, когда оно не лежит ни на одном цикле: цикл и есть объезд.
Прямой способ — убрать ребро и проверить, связаны ли его концы, — стоит одного обхода графа на каждое ребро. Для 15 169 кусков улиц это 15 169 обходов, а в сети побольше — квадрат от её размера. Поиск в глубину справляется со всеми рёбрами за один проход, потому что в неориентированном графе он оставляет после себя очень простую картину. Рёбра, по которым он прошёл, образуют дерево. Каждое из остальных рёбер соединяет вершину с её предком в этом дереве, с вершиной выше по той же ветке. Рёбер между разными ветками не бывает — это доказано ниже.
Пусть ребро дерева ведёт из u вниз в v. Поддерево v — вершины, до которых поиск дошёл через v, — связано с остальным графом этим ребром и, может быть, обратными рёбрами, уходящими вверх. Если хоть одно из них поднимается к u или выше, это объезд. Если ни одно — ребро u–v мост. Чтобы ответить сразу за все рёбра, достаточно знать для каждой вершины, как высоко можно подняться из её поддерева.
Отметим каждую вершину временем входа tin — номером, под которым до неё дошёл поиск. Для вершины v посчитаем low — самое раннее время входа, до которого можно дотянуться из её поддерева одним обратным ребром. Ребро дерева u–v — мост, если low(v) > tin(u): из поддерева не подняться даже до u. Вершина u — точка сочленения, если у неё есть ребёнок v с low(v) ≥ tin(u): из его поддерева не подняться выше u, и без u оно отрежется. Выше корня поиска никого нет, и правило для него своё: корень — точка сочленения, если у него в дереве больше одного ребёнка.
low считается тем же поиском, снизу вверх: это минимум из tin самой вершины, tin концов обратных рёбер, которые из неё выходят, и low её детей. Когда поиск возвращается из v в u, low(v) уже окончательный, и обе проверки делаются тут же.
Как это работает по шагам
Маленький квартал у подножия гор: сетка из шести перекрёстков, две параллельные улицы до перекрёстка G, дорога вверх к треугольнику H, I, J и тупик K. Под буквой — tin и low. Сплошные линии — дерево поиска, пунктир — обратные рёбра. Нажмите на любой перекрёсток, чтобы начать поиск с него.
Проследите за перекрёстком H. Поиск входит в него из F с tin = 7, проходит I и J, и обратное ребро J–H опускает low(J) до 7, а дальше семёрка поднимается в low(I). Когда поиск возвращается из I в H, low(I) = tin(H) = 7. Строгое неравенство не выполнено, значит, улица H–I не мост: треугольник обходится. Нестрогое выполнено, значит, H — точка сочленения: всё, что ниже, держится на самом H. В этом и разница между > и ≥. Мост — вопрос, можно ли обойти ребро, точка сочленения — можно ли обойти вершину. Обратное ребро, которое приходит ровно в H, обходит ребро H–I, но не саму H.
Корень A — особый случай. Условие low(B) ≥ tin(A) для него выполнено всегда, ведь выше корня никого нет, но точкой сочленения он от этого не становится: в дереве у A один ребёнок, и без A всё остальное держится на нём. Начните поиск с F — у корня окажутся три ребёнка, по одному в сторону сетки, G и H, и F станет точкой сочленения уже по правилу корня. Мосты и точки при этом те же, хотя все числа под буквами другие: ответ не зависит от того, откуда начали.
Почему условие верное
В неориентированном графе каждое ребро, которое не попало в дерево поиска в глубину, соединяет вершину с её предком.
Пусть ребро соединяет x и y, и в x поиск вошёл раньше. Из x он не выйдет, пока не рассмотрит ребро x–y. К этому моменту y либо уже найдена — после x и пока x открыта, то есть среди её потомков, — либо будет найдена прямо сейчас, по этому ребру. В обоих случаях y — потомок x. В ориентированном графе рассуждение ломается: ребро y → x из x не видно, и поэтому там бывают перекрёстные рёбра (о них — в статье о поиске в глубину).
Пусть поиск прошёл по ребру дерева из u в v. Это ребро — мост тогда и только тогда, когда low(v) > tin(u). Вершина u, если она не корень, — точка сочленения тогда и только тогда, когда у неё есть ребёнок v с low(v) ≥ tin(u). Корень — точка сочленения тогда и только тогда, когда у него не меньше двух детей.
Вершины выше v по дереву имеют меньшее время входа, вершины поддерева v — не меньшее, чем tin(v), и оно больше tin(u). По лемме любое ребро из поддерева v наружу, кроме самого u–v, ведёт к предку v, то есть к u или выше. Значит, такое ребро есть тогда и только тогда, когда из поддерева можно дотянуться до времени входа ≤ tin(u), то есть low(v) ≤ tin(u). Если ребра нет, поддерево держится только на u–v, и это мост. Если есть, вместе с путём по дереву оно замыкает цикл через u–v, и это не мост.
Для вершины рассуждение то же, только объезд должен миновать саму u: ребро из поддерева v должно вести строго выше u, к времени входа < tin(u). Если у какого-то ребёнка v такого ребра нет, после удаления u поддерево v не связано с корнем — u точка сочленения. Если у каждого ребёнка оно есть, каждое поддерево связано с частью дерева выше u, а та держится на рёбрах дерева и содержит корень, так что граф не распадается. Корень: по лемме между поддеревьями разных детей рёбер нет, поэтому два ребёнка — две части после удаления корня, а один ребёнок — одна.
Вся работа держится на лемме: в неориентированном поиске в глубину нет рёбер вбок, и одного числа low хватает. Возьмите другое остовное дерево, например дерево поиска в ширину, и рёбра из поддерева смогут уходить в соседние ветки. Тогда придётся следить и за самым ранним, и за самым поздним номером, до которого дотягивается поддерево. Именно так устроен первый линейный алгоритм для мостов — о нём в истории.
Ловушка: две улицы между одними перекрёстками
Возвращаться по ребру, по которому пришли, нельзя: это не объезд, а то же самое ребро. Очень часто это пишут как «не ходить в родителя» — сравнивают соседа с вершиной-родителем. Пока между двумя вершинами не больше одного ребра, разницы нет. Но в дорожных графах бывают две разные улицы между одними и теми же перекрёстками: две проезжие части разделённого проспекта, полукольцо развязки, улица и параллельный ей проезд. Переключите в сцене выше «Родителя пропускаем» на «по вершине». Поиск выкинет вторую улицу F–G вместе с первой и объявит F–G мостом, хотя, если перекрыть одну из двух улиц, до G можно доехать по второй.
В графе Алматы 81 пара перекрёстков соединена двумя, а то и тремя разными кусками улиц. Поиск с проверкой по вершине находит 3030 мостов вместо 3005, и 25 из них ложные. Правильная проверка помнит номер ребра, по которому пришли, и пропускает только его — так написаны все листинги ниже.
Для точек сочленения эта ошибка, как ни странно, безвредна. Лишнее ребро в родителя дало бы low(v) = tin(u), а нестрогое неравенство low(v) ≥ tin(u) это и так допускает: две улицы в один и тот же перекрёсток не помогают объехать сам перекрёсток. Поэтому код, который ищет только точки сочленения, нередко пишут «по вершине», и он верен. Беда начинается, когда тот же код берут для мостов.
Код
Поиск без рекурсии, со своим стеком кадров: вершина, ребро, по которому в неё пришли, и место в списке соседей. Демо — квартал из сцены выше.
Мосты печатаются в том порядке, в каком их находит поиск: сначала I–K, потом F–H. Вердикт о ребре выносится, когда поиск возвращается по нему наверх, а возвращается он сначала из самых глубоких мест.
Теперь весь город. Корень поиска — вершина «остальной мир»: так у каждого моста сразу видно, какая сторона отрезана от города, — та, где поддерево. По дороге программа считает, сколько перекрёстков и метров улиц в каждом поддереве, и находит места, которые держатся на одной улице: мосты, выше которых на пути к корню мостов больше нет.
bridges: 3005, of them to a single dead-end crossing: 2201 articulation points: 2552 components without bridges: 3006; the one with the world outside: 8450 crossings (72.1%) deepest search: 2453 vertices on the stack
Стек поиска по улицам Алматы дорастает до 2453 вершин, а предел рекурсии Python по умолчанию — тысяча вызовов. Поэтому рекурсивная версия на этом городе упала бы. Подробнее о глубине стека — в статье о поиске в глубину.
Что остаётся между мостами
Мосты и точки сочленения режут граф на куски, и куски бывают двух видов — смотря что разрешено ломать.
Если ломать можно одно ребро, кусками будут компоненты без мостов: уберите все мосты, и то, что осталось связанным, — одна компонента. Внутри неё любую одну улицу можно перекрыть, не отрезав ни одного перекрёстка. В Алматы таких компонент 3006, но почти все они — одинокие перекрёстки на концах тупиков. Главная, вместе с миром за краем карты, — 8450 перекрёстков из 11 723, 72,1 %. Сожмите каждую компоненту в точку, и мосты свяжут точки в дерево: цикл из компонент означал бы, что какой-то мост лежит на цикле.
Если ломать можно одну вершину, кусками будут блоки, или двусвязные компоненты: наибольшие куски, которые не распадаются от удаления любой одной вершины. Каждое ребро лежит ровно в одном блоке, а точка сочленения — сразу в нескольких: она и сшивает блоки между собой. Переключите сцену с маленьким кварталом на «блоки»: их пять — сетка, пара улиц F–G, мост F–H, треугольник H, I, J и мост I–K. Перекрёсток G в одной компоненте без мостов с сеткой — две улицы до него и есть объезд, — но в отдельном блоке: обе улицы сходятся в F, и без F до G не доехать.
У блоков есть точная характеристика. В 1932 году Хасслер Уитни доказал: граф из трёх и более вершин не распадается от удаления одной вершины тогда и только тогда, когда любые две его вершины соединены двумя путями без общих промежуточных вершин. Для рёбер то же самое: компонента без мостов — это место, где между любыми двумя вершинами есть два пути без общих рёбер. Оба утверждения — частные случаи теоремы Менгера о числе непересекающихся путей, которую проще всего доказать потоками.
Блоки находит тот же поиск, если складывать рёбра в стек по мере того, как он их встречает. Когда поиск возвращается из v в u и видит low(v) ≥ tin(u), всё, что лежит в стеке выше ребра u–v, вместе с ним, — один блок.
Сколько это стоит
В каждую вершину поиск входит один раз и каждое ребро рассматривает дважды, с обоих концов. Числа tin и low, размер поддерева и проверки при возврате — O(1) на вершину и ребро. Итого O(V + E) времени и O(V + E) памяти: сам граф плюс несколько массивов по числу вершин; блокам нужен ещё стек рёбер. Наивный способ — убрать ребро и поискать объезд обходом — платит O(V + E) за каждое ребро, то есть O(E(V + E)).
Замер на городе-решётке, где каждая улица уцелела с вероятностью 0,6: много тупиков и мостов, как на окраинах. Наивный способ ищет объезд поиском и останавливается, едва нашёл второй конец, — так его и написал бы человек, который торопится.
Наклон наивного способа около двух: удвоили город — время выросло вчетверо, потому что мостов становится вдвое больше, и каждый мост требует обойти всю отрезанную сторону вместе с остальным городом. Один поиск растёт линейно. На решётке из 4900 перекрёстков разница уже в сотни раз, и она растёт вместе с городом.
Где работает
Сети, которые обязаны пережить отказ. Энергетики проверяют сеть по правилу N−1: она должна выдержать отказ любого одного элемента — линии, трансформатора, генератора — без отключения потребителей. Настоящая проверка считает потоки мощности, но мост — самое грубое нарушение, видное без всяких расчётов: одна линия, за которой целый район. То же правило в магистральных сетях связи: к узлу ведут две независимые линии, чтобы экскаватор, перерубивший одну, не оставил город без связи.
Дороги. Для дорожной сети мосты — список мест, где ремонт, авария или сель отрежут людей от города, и точки сочленения — перекрёстки, где то же самое сделает одна развязка на ремонте. В горах и на окраинах этот список длинный, в сетке центра — почти пустой: там почти любая улица обходится, что видно в первой сцене.
Односторонние улицы. Город без мостов можно сделать целиком односторонним так, чтобы отовсюду можно было доехать куда угодно, — это теорема Роббинса 1939 года. Мосты обязаны остаться двусторонними. Доказательство — тот же поиск в глубину и те же числа low, оно разобрано в статье о компонентах сильной связности.
Разбор графа на части. Граф планарен — рисуется без пересечений рёбер — тогда и только тогда, когда планарен каждый его блок. Поэтому проверки планарности, начиная с линейной проверки Хопкрофта и Тарьяна 1974 года, первым делом режут граф на блоки. Следующий шаг того же разбора — трёхсвязные компоненты, где граф не распадается и от удаления любых двух вершин.
История
Двусвязные графы изучал ещё Хасслер Уитни в начале 1930-х — его статья 1932 года так и называется: «Non-separable and planar graphs», «Неразделимые и планарные графы». Алгоритм для блоков за линейное время на поиске в глубину появился в начале 1970-х у Джона Хопкрофта и Роберта Тарьяна: в статье Тарьяна 1972 года о поиске в глубину и в «Алгоритме 447» Хопкрофта и Тарьяна, напечатанном в Communications of the ACM в июне 1973 года, — там граф делится на компоненты связности и на двусвязные компоненты за время, пропорциональное числу вершин и рёбер. Величину, которую в этой статье зовут low, они называли lowpoint.
Мосты отдельно разобрал Тарьян в двухстраничной заметке 1974 года «A note on finding the bridges of a graph». Её мысль в том, что для мостов поиск в глубину не обязателен: годится любое остовное дерево. Тарьян нумерует вершины дерева в обратном порядке обхода, считает для каждой число потомков и два числа — самый ранний и самый поздний номер, до которых дотягивается поддерево одним ребром не из дерева. Ребро дерева — мост, если оба числа остаются в пределах поддерева. Поиск в глубину избавляет от второго числа: рёбер вбок у него нет.
Задачи
В первой задаче нужно ответить на сотни тысяч вопросов «что отрежет это перекрытие», и среди тестов — тот самый город с параллельными улицами. Во второй перекрывают перекрёсток и считают, сколько пар мест потеряют связь друг с другом; здесь пригодятся и точки сочленения, и размеры поддеревьев, и разница между > и ≥.
Данные: Улицы Алматы от центра до гор © участники OpenStreetMap, ODbL, выгрузка 17.10.2026