Отделимость и бисвязность

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

В некоторых ситуациях, когда важно, чтобы граф был связным, может оказаться су­щественным тот факт, что он остается связным, если убрать из него какую-либо вершину

Часть 5. Алгоритмы на графах

или ребро. То есть, мы, возможно, захотим знать более одного пути между каждой па­рой вершин графа с тем, чтобы застраховаться от возможных отказов и неисправностей. Например, мы можем лететь из Нью-Йорка в Сан-Франциско, даже если аэропорт в Чикаго завален снегом, ибо существует рейс через Денвер. Или можно вообразить себе ситуацию во время военных действий, в условиях которой мы хотим проложить такую железнодорожную сеть, когда противник, дабы нарушить железнодорожное сообщение, должен разбомбить, по меньшей мере, две станции. Аналогично, мы вправе рассчитывать, что соединения в интегральной схеме или в сети связи проложены таким образом, что остальная часть схемы продолжает работать, если оборвался какой-либо провод или ка­кое-то соединение перестало работать.

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

Определение 18.1. Мостом (bridge) в графе называется ребро, после удаления которого связный граф распадается на два не связанных между собой подграфа. Граф, у которого нет мостов, называется реберно-связным (edge-connected).

Когда мы говорим об удалении ребра, мы имеем в виду удаление этого ребра из мно­жества ребер, которое определяет граф, даже если после такого удаления одна или обе вершины графа останутся изолированными. Реберно-связный граф остается связным, когда удаляется какое-либо одно ребро. В некоторых контекстах целесообразнее говорить о возможности нарушения связности графа, а не о способности графа оставаться связ­ным. Таким образом, мы будем свободно пользоваться альтернативной терминологией, которая делает акцент на таких моментах: мы называет граф, который относится к кате-

гории реберно-связных, реберно-отделимым {edge-separable) и назовем мосты ребрами отделимости (separation edges). Если мы удалим все мосты в реберно-отделимом графе, мы раз­делим его на реберно-связные компоненты {edge-connected components) или компоненты, связанные мостами (bridge-connected components) — максимальные подграфы, не имею­щие мостов. На рис. 18.16 показан небольшой пример, ко­торый может послужить иллюстрацией этих понятий.

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

Глава 18. Поиск на графе

РИСУНОК 18.17. ДЕРЕВО DFS, ИСПОЛЬЗУЕМОЕ ДЛЯ ПОИСКА МОСТОВ

Узлы 5, 7 и 12 рассматриваемого дерева DFS для графа на рис. 18.16 обладают тем свойством, что никакое обратное ребро не соединяет потомка с предком, и этим свойством не обладают никакие другие узлы. Поэтому, как было указано выше, удаление ребра между одним из этих узлов и их предком отсоединит поддерево с корнем в этом узле от остальной части графа. То есть, ребра 0-5, 11-12 и 6-7 суть мосты. Мы используем массив low, проиндексированный именами вершин, для отслеживания минимального номера при обходе вершин в прямом порядке (значение ord), на который ссылается любое обратное ребро в поддереве, корнем которого является эта вершина. Например, значением low[9] будет 2, поскольку одно из обратных ребер в поддереве с корнем в 9 указывает на 4 (вершина, номер которой при обходе в прямом порядке есть 2), и никакое другое обратное ребро не указывает на вершину более высокого уровня в этом дереве. Узлы 5, 7 и 12 — это узлы, для которых значения low равны значению ord.

Свойство 18.5. В любом дереве DFS ребро v-w есть мост тогда и только тогда, когда не существует обратное ребро, которое соединяет один из потомков w с каким-либо пред-

KOMW.

Доказательство: Если существует такое ребро, то v-w не может быть мостом. С дру­гой стороны, если v-w не есть мост, то в графе должен быть другой путь из w в v, от­личный от w-v. Каждый такой путь должен содержать одно из таких ребер. ■

Провозглашение этого свойства эквивалентно утверждению, что единственная связь поддерева с корнем в w, ведущая в узел, который не входит в это поддерево, есть роди­тельская связь, ведущая из w назад в v. Это условие соблюдается тогда и только тогда, когда каждый путь, соединяющий любой узел в поддереве узла w, с любым узлом, не при­надлежащим поддереву узла w, включает v-w. Другими словами, удаление v-w отделяет подграф, соответствующий поддереву узла w, от остальной части графа.

Программа 18.7 показывает, как можно усовершенствовать поиск в глубину с таким расчетом, чтобы он мог выявлять в графах мосты, используя для этой цели программу 18.5. Для каждой вершины v мы используем рекурсивную функцию, вычисляющую мини­мальный номер в прямом порядке обхода, на который можно выйти через последователь­ность из нулевого или большего числа ребер дерева, за которыми следует одно обратное ребро из любого узла поддерева с корнем в вершине v. Если вычисленное число равно номеру вершины v при прямом порядке обхода, то не существует ребра, связывающего потомок вершины v с ее предком, а это означает, что обнаружен мост. Вычисления для

Часть 5. Алгоритмы на графах