![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Отделимость и бисвязность
Чтобы продемонстрировать широкие возможности поиска в глубину как основы алгоритмов обработки графов, мы обратимся к задачам, имеющим отношение к обобщенному понятию связности в графах. Мы займемся изучением проблем такого рода: пусть заданы две вершины, существуют ли два различных пути, связывающих эти вершины? В некоторых ситуациях, когда важно, чтобы граф был связным, может оказаться существенным тот факт, что он остается связным, если убрать из него какую-либо вершину Часть 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. Алгоритмы на графах
Свойство 18.6. Мосты графа обнаруживаются за линейное время Доказательство: Программа 18.7 представляет собой незначительную модификацию поиска в глубину, при этом добавляются несколько проверок, требующие постоянных затрат времени. В результате из свойств 18. 3 и 18.4 непосредственно следует, что поиск мостов в графе требует время, пропорциональное V2 для представления графа в виде матрицы смежности и V + Е для представления графа в виде списков смежных вершин. ■ Программа 18.7. Реберная связность_________________________________________ Класс DFS производит подсчет мостов заданного графа. Клиентская программа может использовать объект ЕС для выявления количества реберно-связных компонент. Добавление функции-элемента, осуществляющей проверку, содержатся ли какие-либо две вершины в одной и той же реберно-связной компоненте, мы оставляем на самостоятельную проработку (упражнение 18.36). Вектор low отслеживает минимальный номер вершины при прямом порядке обхода вершин графа, который может быть достигнут из каждой вершины через некоторую последовательность древесных ребер, за которой следует обратное ребро. template < class Graph> class EC: public SEARCH< Graph> { int bent; vector < int> low; void searchC(Edge e) { int w = e.w; ord[w] = cnt++; low[w] = ord[w]; typename Graph:: adjIterator A(G, w); for (int t = A.beg();! A.end(); t = A.nxt()) if (ord[t] == -1) {
|