Нахождение глобального минимального разреза - Рандомизированные алгоритмы

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

Задача

Для заданного ненаправленного графа G = (V, E) разрез определяется как разбиение V на два непустых подмножества A и B. Ранее, при рассмотрении сетевых потоков, мы работали с похожим определением разреза s-t. тогда для направленного графа G = (V, E) с выделенными узлами источника и стока s и t, разрез s-t определялся как разбиение V на такие множества A и B, что s ∈ Aи t ∈ B. Наше новое определение отличается от того. граф стал ненаправленным, и в нем нет ни источника, ни стока.

Для разреза (A, B) в ненаправленном графе G размер (A, B) равен количеству ребер, один конец которых принадлежит A, а другой принадлежит B. Глобальным минимальным разрезомназывается разрез минимального размера. Термин “глобальный” указывает на то, что разрешены любые разрезы графа; нет ни источника, ни стока. Таким образом, глобальный минимальный разрез может рассматриваться как естественная характеристика “надежности”; это минимальное количество ребер, удаление которых приводит к потере связности графом. Сначала мы убедимся в том, что методы сетевого потока действительно достаточны для нахождения глобального минимального разреза.

(13.4) Существует алгоритм с полиномиальным временем для нахождения глобального минимального разреза в ненаправленном графе G.

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

Заданный ненаправленный граф G = (V, E) необходимо преобразовать так, чтобы в нем были направленные ребра, источник и сток. Каждое ненаправленное ребро e = (u, v) ∈ E заменяется двумя противоположно ориентированными направленными ребрами, e' = (u, v) и e" = (v, u), каждое из которых имеет пропускную способность 1. Обозначим полученный направленный граф G'.

Теперь допустим, что мы выбрали два произвольных узла s, t ∈ V и нашли минимальный разрез s-t в G'. Легко убедиться в том, что если (A, B) является минимальным разрезом в G', то (A, B) также является разрезом минимального размера в G среди всех разрезов, отделяющих s от t. Но мы знаем, что глобальный минимальный разрез в G должен отделять s от чего-то, так как обе стороны A и B не пусты, и s принадлежит только одной из них. Соответственно мы фиксируем любой узел s ∈ V и вычисляем минимальный разрез s-t в G' для всех остальных узлов t ∈ V - {s}. Это требует n - 1 вычислений направленного минимального разреза, лучшим из которых будет глобальный минимальный разрез графа G. ■

Алгоритм в (13.4) создает сильное впечатление, что нахождение глобального минимального разреза в ненаправленном графе в каком-то смысле является более сложной задачей, чем поискминимального разреза s-t в потоковой сети, так как нам приходится n - 1 раз вызывать процедуру для решения последней задачи в нашем методе для решения первой. Но оказывается, это всего лишь иллюзия. Серия все более простых алгоритмов, разработанных в конце 1980-х и начале 1990-х годов, показала, что глобальные минимальные разрезы в ненаправленных графах могут вычисляться так же эффективно, как разрезы s-t, и даже еще эффективнее, причем для этого не нужны ни улучшающие пути, ни даже концепция потока. Кульминационным моментом в этой области стало открытие Дэвидом Каргером в 1992 году алгоритма стягивания — рандомизированного метода, качественно более простого по сравнению со всеми предшествующими алгоритмами нахождения глобальных минимальных разрезов. В самом деле, алгоритм настолько прост, что на первый взгляд даже трудно поверить, что он действительно работает.

Разработка алгоритма

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

Алгоритм стягивания работает со связным мультиграфомG = (V, E); это ненаправленный граф, который может иметь несколько “параллельных” ребер между одной парой узлов. Сначала он случайным образом выбирает в G ребро e = (u, v) и “стягивает” его, как показано на рис. 13.1. В результате появляется новый граф G', в котором u и v порождают новый узел w; все остальные узлы сохраняют свою исходную “личность”. Все ребра, у которых один конец равен u, а другой равен v, удаляются из G'. Все остальные ребра e остаются в G', но если один конец ребра равен u или v, то этот конец заменяется новым узлом w. Обратите внимание: даже если в G любые два узла соединены не более чем одним ребром, в G' могут появиться параллельные ребра.

Рис. 13.1. Применение алгоритма стягивания к графу из четырех узлов

Алгоритм стягивания продолжает рекурсивно выполняться с G', случайно выбирая ребра (с равномерным распределением) и стягивая их. По мере продолжения рекурсии вершины G' должны рассматриваться как суперузлы: каждый суперузел w соответствует подмножеству S(w) ⊆ V, “поглощенному” в результате стягиваний, породивших w. Алгоритм завершается при достижении графа G', состоящего из двух суперузлов v₁ и v₂ (предположительно соединенных несколькими параллельными ребрами). Каждый суперузел v_i имеет соответствующее подмножество S(v_i) ⊆ V, которое состоит из стянутых в него узлов, и эти два множества S(v₁) и S(v₂) образуют разбиение V. Далее (S(v₁), S(v₂)) выводится как разрез, найденный алгоритмом.

Анализ алгоритма

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

(13.5) Алгоритм стягивания возвращает глобальный минимальный разрез графа G с вероятностью не менее

Доказательство. Возьмем глобальный минимальный разрез (A, B) графа G и предположим, что он имеет размер k; иначе говоря, существует множество Ф из k ребер, один конец которых принадлежит A, а другой принадлежит B. Мы хотим предоставить нижнюю границу вероятности того, что алгоритм стягивания вернет разрез (A, B).

Что может пойти не так на первом шаге алгоритма стягивания? Проблема возникнет при стягивании ребра из Ф. В этом случае узел из A и узел из B будут слиты в один суперузел и разрез (A, B) уже не может быть получен на выходе алгоритма. И наоборот, если стягивается ребро, не входящее в Ф, то остается вероятность того, что разрез (A, B) будет возвращен успешно.

Итак, нам нужна верхняя граница вероятности того, что стягивается ребро из Ф, а для этого потребуется нижняя граница размера Е. Обратите внимание: если любой узел v имеет степень ниже k, то разрез ({v}, V-{v}) будет иметь размер меньше k, а это противоречит нашему предположению о том, что (A, B) является глобальным минимальным разрезом. Тогда степень каждого узла в G не менее k, а значит, [E] ≥ 1/2kn . Следовательно, вероятность того, что стягивается ребро из Ф, не превышает

Теперь рассмотрим ситуацию после j итераций, когда текущий граф G' содержит n - j суперузлов, и предположим, что ни одно ребро в Ф еще не стягивалось. Каждый разрез G' является разрезом G, поэтому каждому суперузлу G' инцидентны не менее k ребер. Следовательно, G' содержит не менее 1/2k(n - j) ребер, а вероятность того, что ребро из Ф будет стянуто на следующей итерации j + 1, не превышает

Разрез (A, B) будет возвращен алгоритмом, если ни одно ребро из Ф не было стянуто на любой из итераций 1, 2, ..., n - 2. Если взять за Е_j событие “ребро из Ф не было стянуто на итерации j”, то мы показали, что и Нас интересует нижняя граница величины и “раскрутка” формулы условной вероятности позволяет убедиться в том, что она равна

Итак, теперь мы знаем, что одно выполнение алгоритма стягивания не найдет глобальный минимальный разрез с вероятностью не более Конечно, это число очень близко к 1, но вероятность успеха можно усилить простым повторением алгоритма с независимым случайным решением и выбором лучшего из найденных разрезов. Согласно (13.1), если выполнить алгоритм раз, то вероятность того, что глобальный минимальный разрез не будет найден ни в одном выполнении, не превышает

Дальнейшие повторения позволяют легко опустить вероятность неудачи ниже 1/е: если повторить алгоритм раз, то вероятность того, что глобальный минимальный разрез не будет найден, не превысит e^{-ln n} = 1/n.

Общее время выполнения, необходимое для обеспечения высокой вероятности успеха, полиномиально по n, так как каждое выполнение алгоритма стягивания занимает полиномиальное время и алгоритм выполняется полиномиальное количество раз. Его время выполнения относительно велико по сравнению с методами нахождения потока, так как Ө(n²) независимых запусков выполняются не менее Ω(n²) раз. Мы решили описать эту версию алгоритма стягивания как самую простую и элегантную; было показано, что некоторые оптимизации организации многократных запусков способны существенно улучшить время выполнения.

Дальнейший анализ: количество глобальных минимальных разрезов

Анализ алгоритма стягивания дает на удивление простой ответ на следующий вопрос: имеется ненаправленный граф G = (V, E) с n узлами, какое максимальное количество глобальных минимальных разрезов он может иметь (как функции от n)?

Очевидно, что для направленной потоковой сети количество минимальных разрезов s-t может быть экспоненциальным по n. Например, возьмем направленный граф с узлами s, t, v₁, v₂, ..., v_n и ребрами с единичной пропускной способностью (s, v_i) и (v_i, t) для каждого i. Тогда s в сочетании с любым подмножеством {v₁, v₂, ..., v_n} образует сторону источника в минимальном разрезе, а следовательно, всего существуют 2ⁿ минимальных разрезов s-t.

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

Сейчас мы покажем, что анализ алгоритма стягивания немедленно дает ответ на этот вопрос и доказывает, что цикл из n узлов в действительности является крайним случаем.

(13.6) Ненаправленный граф G = (V, E) из n узлов содержит не более глобальных минимальных разрезов.

Доказательство. В доказательстве (13.5) установлено даже больше, чем заявлено в утверждении. Допустим, имеется граф G, а C₁, ..., C_r — все его глобальные минимальные разрезы. Пусть Е_iобозначает событие “С_i возвращается алгоритмом стягивания”, а — событие “алгоритм возвращает любой глобальный минимальный разрез”.

Тогда, хотя в (13.5) просто утверждается, что доказательство фактически демонстрирует, что для всех i выполняется События в паре E_i и E_j являются взаимоисключающими (так как при любом выполнении алгоритма возвращается только один разрез), поэтому, согласно границе объединения для взаимоисключающих событий (13.49), имеем

Но очевидно, что Рr[E] ≤ 1, а следовательно, должно выполняться