Лабораторная работа № 25 (к § 54) Мосты и точки сочленения

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

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

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

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

Обход в глубину (DFS) последовательно углубляется в ещё не посещённые вершины. Время входа tin фиксирует момент первого посещения, а low показывает, до какого предка можно добраться из поддерева без возврата по родительскому ребру. Эти две величины позволяют искать мосты и точки сочленения без перебора вариантов удаления.

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

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

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

Для вершины v значение low[v] равно минимальному времени входа в вершину, достижимую из её поддерева по рёбрам дерева и одному обратному ребру. При встрече обратного ребра к предку low уменьшается до времени входа этого предка. Ребро к родителю в обычном неориентированном графе не учитывают, потому что оно лишь отменяет шаг, которым алгоритм пришёл в вершину.

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

Для некорневой вершины u достаточно найти ребёнка v, для которого low[v] ≥ tin[u]: поддерево v не может подняться к предкам u и отделится после удаления u. У корня нет предка, поэтому сравнение с его временем входа неприменимо. Корень является точкой сочленения только при наличии более одного ребёнка в дереве обхода.

Как распознать мост и точку сочленения при обходе в глубину

Сначала определите, является ли рассматриваемое ребро ребром дерева DFS, и найдите значения tin и low. Затем применяйте разные знаки неравенства для моста и точки сочленения. Отдельно проверяйте корень дерева обхода.

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

Разбор задач

Цепь из четырёх вершин

Условие: дан граф 1—2—3—4. Найдём все мосты и точки сочленения непосредственно по определениям. В цепи нет циклов, поэтому для каждого соединения нужно проверить, остаётся ли обходной путь.

1. Удалим ребро 1—2. Вершина 1 отделится от 2, 3 и 4, значит, число компонент увеличится.
2. Аналогично удаление 2—3 разделит цепь на 1—2 и 3—4, а удаление 3—4 отделит вершину 4.
3. Удалим вершину 2 вместе с рёбрами. Получатся компоненты {1} и {3, 4}; при удалении 3 получатся {1, 2} и {4}.
4. Удаление 1 или 4 оставляет оставшиеся вершины связными, поэтому эти вершины не являются точками сочленения.

Ответ: мосты — 1—2, 2—3 и 3—4; точки сочленения — 2 и 3. Здесь каждый мост очевиден, потому что ни одно ребро не входит в цикл.

Граф с циклом и ответвлением

Условие: рассмотрим цикл 1—2—3—1 и ответвление 3—4. Выполним DFS из вершины 1, выбирая соседей по порядку, и найдём мосты по значениям tin и low. Такой пример показывает, почему цикл защищает одни рёбра, но не защищает ответвление.

1. Порядок входа может быть таким: tin[1]=1, tin[2]=2, tin[3]=3, tin[4]=4. Рёбра 1—2, 2—3 и 3—4 входят в дерево, а 3—1 становится обратным.
2. Из вершины 3 по обратному ребру можно попасть в 1, поэтому low[3]=1 и low[2]=1. Для вершины 4 обратных рёбер нет, значит, low[4]=4.
3. Для 2—3 проверяем 1 > 2 — условие ложно, поэтому ребро не мост. Для 1—2 проверяем 1 > 1 — тоже ложно.
4. Для 3—4 имеем 4 > 3, поэтому это ребро является мостом: вершина 4 не может вернуться в цикл.

Ответ: единственный мост — 3—4. Точкой сочленения является вершина 3, поскольку после её удаления вершина 4 отделяется от цикла.

Алгоритм по списку смежности

Условие: разработайте алгоритм, который получает список смежности неориентированного графа и выводит все мосты и точки сочленения. Граф может быть несвязным, поэтому одной стартовой вершины недостаточно. Для каждой вершины будем хранить родителя, tin, low и признак посещения.

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

Ответ: алгоритм находит все объекты за линейное время O(V + E), если список смежности хранится без повторного перебора рёбер. В графе с кратными рёбрами нужно передавать и проверять идентификатор ребра, а не только вершину-родителя.

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

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

Ошибка: использовать для моста условие low ≥ tin. При равенстве поддерево может вернуться к самому родителю по другому ребру, поэтому удаление не разрывает граф. Для самопроверки подставьте равенство в пример с циклом.

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

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

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

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

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

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

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

• Мост — ребро, удаление которого увеличивает число компонент связности.
• Точка сочленения — вершина, удаление которой увеличивает число компонент связности.
• Время входа фиксирует момент первого посещения вершины в DFS.
• low отражает возможность добраться из поддерева до предка в обход родительского ребра.
• Ребро дерева обхода является мостом, если low потомка больше времени входа родителя.
• Некорневая вершина является точкой сочленения, если у неё есть потомок с low не меньше времени входа вершины.
• Корень дерева обхода является точкой сочленения при наличии более одного ребёнка.