Информатика · объяснение и практика
Мост графа: удаление какого ребра разрывает связность
Мосты в неориентированном графе: удаление одного ребра, обходной путь, значения tin/low и осторожность с параллельными рёбрами.

В теме Графы и маршруты · Учебная карта
В маршруте Графы, разрезы и динамические запросы · 10 тем
Главная мысль
Мост — ребро неориентированного графа, удаление которого увеличивает число компонент связности. Для мостового ребра нет обходного пути между его концами без этого ребра. В DFS это проверяется сравнением low дочерней вершины со временем входа в родительскую.
Удаляем ребро, сохраняя вершины
В задаче о мостах убирают одну связь, а не обе её конечные вершины. Если остальная сеть всё ещё соединяет эти концы, число компонент не увеличивается. Поэтому ребро, лежащее на цикле простого неориентированного графа, не является мостом: цикл даёт обход в другую сторону.
Возьмём треугольник A−B−C−A и цепочку A−D−E. Внутри треугольника можно обойти удалённую сторону через третью вершину. А связи A−D и D−E являются единственными проходами к соответствующим частям цепочки. Их удаление действительно разделяет сеть на дополнительные компоненты.
Что показывают времена обхода
При поиске в глубину каждой вершине назначают tin — время первого входа. Значение low для вершины хранит самое раннее время входа, достижимое из её поддерева с использованием дерева обхода и подходящего обратного ребра. Оно помогает понять, есть ли путь из поддерева к уже посещённой верхней части сети.
Для ребра дерева от u к v условие low[v]>tin[u]означает, что поддерево v не имеет обходного выхода к u или его предкам. Тогда ребро u−v является мостом. Равенство не подходит: при low[v]=tin[u]возврат к u существует, поэтому удаление одной древесной связи ещё не отрезает поддерево.
Пример
В треугольнике A−B−C−A с цепочкой A−D−E мосты ровно A−D и D−E.
Удаление A−B оставляет путь A−C−B. Удаление A−D отрезает D и E,а удаление D−E отделяет только E; все вершины при этом остаются в графе.
Проверяем кратные связи и несвязный вход
Если между двумя вершинами есть два разных параллельных ребра, удаление одного сохраняет второе. Поэтому оба нельзя автоматически объявить мостами из-за совпавшего родителя обхода. В реализации нужно различать конкретное ребро входа, а не пропускать вообще все связи с родительской вершиной.
Для несвязного графа обход запускают в каждой ещё не посещённой компоненте. Определение моста всё равно использует увеличение общего числа компонент, а не требование, чтобы исходно сеть была единой. Это также отличается от задачи о точке сочленения: там удаляется вершина со всеми её связями, и условие проверки меняется.
От чтения к действию
А теперь — вы
Частые вопросы
Любое ребро дерева является мостом?
Да, в обычном неориентированном дереве удаление любого ребра разделяет его на две компоненты.
Два параллельных ребра между одними вершинами оба мосты?
Нет. Удаление одного сохраняет прямой проход по другому.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Точка сочленения: когда удаление вершины разделяет граф
Точки сочленения: удаление вершины со связями, особое правило корня DFS и отличие от мостового ребра.
Открыть темуСильные компоненты: какие вершины взаимно достижимы
Компоненты сильной связности ориентированного графа: взаимная достижимость, максимальность группы и ациклический граф сжатия.
Открыть тему