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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

Задача 1

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

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

Ответ: мосты — CD и DE; точки сочленения — C и D.

Задача 2

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

1. Удалим общую вершину вместе с инцидентными рёбрами и проверим оставшиеся части.
2. Каждый исходный цикл потеряет общую вершину, но его остальные вершины останутся отдельной связной частью. Значит, граф распадётся как минимум на две компоненты.
3. Каждое ребро обоих циклов принадлежит циклу. Следовательно, удаление любого одного ребра сохраняет связь внутри соответствующего цикла и не создаёт разрыва.

Ответ: общая вершина является точкой сочленения, мостов в графе нет.

Задача 3

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

1. При входе в вершину v записывают tin[v]. Для её поддерева вычисляют low[v], учитывая дочерние вершины и обратные рёбра.
2. Для каждого ребра дерева v—to проверяют условие low[to] > tin[v]. Если оно выполняется, ребро является мостом, поскольку поддерево to не может вернуться выше v.
3. Для внутренней вершины проверяют low[to] ≥ tin[v]. При выполнении условия v — точка сочленения; для корня нужно посчитать число его детей в дереве обхода.

Ответ: мосты и точки сочленения определяются указанными сравнениями за один обход графа, то есть без отдельного удаления каждого объекта.

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

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

Мост часто путают с точкой сочленения, потому что оба объекта могут разрывать граф. Причина — смешение названий «ребро» и «вершина». Перед проверкой подпишите объект: удаляется одно ребро или вершина вместе с её рёбрами.

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

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

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

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

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

На практике критические элементы ищут в компьютерных сетях, дорожных системах, коммуникациях и электрических схемах. Мост показывает уязвимый канал, а точка сочленения — уязвимый узел.

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

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