§ 54. Мосты и точки сочленения

Определения и обозначения

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

Компонента связности — максимальная связная часть графа, то есть набор вершин, внутри которого между любыми двумя есть путь. При удалении моста число компонент увеличивается на единицу, а при удалении точки сочленения может увеличиться на несколько единиц. Сравнение этого числа до и после удаления даёт точное определение уязвимости.

Мост — ребро, удаление которого увеличивает число компонент связности графа. Такое ребро является единственным соединением между некоторыми частями сети. В обозначении ребра u–v его проверяют не по степеням концов, а по наличию обходного пути между u и v.

Точка сочленения — вершина, удаление которой вместе со всеми инцидентными рёбрами увеличивает число компонент связности. Она может соединять несколько самостоятельных частей графа. Если после удаления вершины остальные вершины по-прежнему образуют столько же компонент, точкой сочленения она не является.

Как это устроено

Удаление моста разрывает граф, потому что между его концами нет другого пути. Все маршруты из одной стороны в другую обязательно проходят по этому ребру, поэтому после его удаления вершины оказываются в разных компонентах. Немостовое ребро имеет обходной путь, и по нему можно сохранить связь после удаления исходного ребра.

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

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

Последствия удаления ребра и вершины различаются. Мост разрывает конкретную связь между частями, но его концы остаются в графе. Точка сочленения исчезает вместе со всеми инцидентными рёбрами и может отделить целую группу вершин, поэтому её влияние иногда значительно шире.

Поиск в глубину строит дерево посещения и нумерует вершины временем входа tin. Для поддерева вершины u вычисляют low[u] — самое раннее время, до которого можно добраться из этого поддерева по рёбрам дерева и обратным рёбрам. Для ребра родитель–потомок (u, v) условие low[v] > tin[u] означает мост, а low[v] ≥ tin[u] — признак точки сочленения u; для корня действует отдельное условие по числу детей.

Сравнение мостов и точек сочленения

Сначала определите, что именно удаляется: ребро или вершина. Затем сравните число компонент до и после удаления, а для больших графов используйте критерии обхода в глубину. Строка о циклах помогает быстро находить мосты, но для точек сочленения одного этого признака недостаточно.

Разбор задач

Задача 1

Дан граф с рёбрами AB, BC, CA и CD. Нужно найти все мосты и точки сочленения. Первые три ребра образуют треугольник, а вершина D присоединена к нему единственным ребром CD.

1. Рёбра AB, BC и CA входят в цикл ABC, поэтому удаление любого из них оставляет обходной путь между его концами.
2. Ребро CD в цикл не входит. После его удаления вершина D отделяется от остальных вершин.
3. Проверим вершины: удаление C отделяет D, а удаление A, B или D не разделяет оставшуюся часть графа.

Ответ: мост — CD; точка сочленения — C. Треугольник защищён от разрыва альтернативными маршрутами, а ребро CD является единственным каналом к D.

Задача 2

Дан граф с рёбрами AB, BC, CA, CD, DE, EF и FD. Нужно определить, какие элементы можно удалить без увеличения числа компонент связности. Граф состоит из двух треугольников ABC и D EF, соединённых ребром CD.

1. Рёбра AB, BC, CA входят в первый цикл, а DE, EF, FD — во второй, поэтому все они немостовые.
2. Ребро CD не входит ни в один цикл и при удалении разрывает связь между треугольниками.
3. Удаление A, B, E или F не разъединяет граф: в своём треугольнике каждая такая вершина имеет обход через две другие.
4. Удаление C или D разрывает соединение двух частей, значит, эти вершины являются точками сочленения.

Ответ: без увеличения числа компонент можно удалить рёбра AB, BC, CA, DE, EF, FD и вершины A, B, E, F. Мост — CD, точки сочленения — C и D.

Задача 3

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

1. При входе в вершину u запишите tin[u] и первоначально положите low[u] = tin[u].
2. Для дочерней вершины v после её обработки обновите low[u] = min(low[u], low[v]); для обратного ребра к уже посещённой вершине используйте её tin.
3. Ребро (u, v) объявите мостом, если low[v] > tin[u].
4. Некорневую u объявите точкой сочленения, если для некоторого ребёнка low[v] ≥ tin[u]; корень проверяйте по числу дочерних поддеревьев.

Ответ: один DFS находит все нужные элементы за время порядка числа вершин и рёбер, O(V + E). Ключевая идея — выяснить, может ли поддерево вернуться к предку без ребра или вершины своего соединения.

Типичные ошибки

Ошибка: считать мостом любое ребро, соединяющее вершины разной степени. Степень показывает число соседей, но не наличие обходного пути. Проверяйте, увеличится ли число компонент после удаления, или ищите цикл.

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

Ошибка: удалять только саму вершину, оставляя её рёбра. По определению вместе с вершиной исчезают все инцидентные рёбра. Поэтому мысленно уберите вершину и пересчитайте компоненты оставшегося графа.

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

Связь с другими темами

Для темы нужны понятия графа, вершины, ребра, пути, циклы, связность и компоненты связности. Без них трудно точно описать, что именно меняется после удаления элемента.

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

На практике эти понятия применяют для анализа транспортных, компьютерных и коммуникационных сетей. Они помогают находить критические дороги, каналы, узлы и пункты, отказ которых нарушит работу системы.

Что запомнить

• Мост — ребро, удаление которого увеличивает число компонент связности.
• Точка сочленения — вершина, удаление которой увеличивает число компонент связности.
• Ребро является мостом тогда и только тогда, когда оно не входит ни в один цикл.
• Удаление моста разрывает связь между частями графа.
• Для поиска мостов и точек сочленения удобно применять поиск в глубину.
• При анализе точки сочленения нужно удалять вершину вместе со всеми инцидентными рёбрами.