Алгоритм Каргера для нахождения минимального разреза

Алгоритм Каргера — рандомизированный алгоритм для нахождения минимального разреза в связном графе. Он был разработан Дэвидом Каргером (англ. David Karger) в 1993 году.

Основные определения

Пусть [math]G[/math] — неориентированный мультиграф с множеством вершин [math]V[/math] и множеством ребер [math]E[/math], и [math]|V| = n[/math], [math]|E| = m[/math].

Определение:

Стягиванием (англ. contraction) ребра [math]uv[/math] называется следующая последовательность действий: Добавляем новую вершину [math]w[/math]. Для всех ребер [math]xu[/math] и [math]xv[/math] (где [math]x \in V, x \neq v, x \neq u[/math]) добавляем новые ребра [math]xw[/math]. При этом, если получаются кратные ребра - оставляем их. Удаляем вершины [math]u[/math] и [math]v[/math] и все инцидентные им ребра.

Определение:

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

Определение:

Стянутым графом (англ. contracted graph) называется граф, состоящий из двух мультивершин, полученный из исходного графа последовательным стягиванием произвольных ребер.

Определение:

Разрезом (англ. cut) [math]\langle A, B \rangle[/math] называется разбиение множества [math]V[/math] на два множества [math]A[/math] и [math]B[/math], удовлетворяющее следующим условиям: [math]A, B \subset V[/math]; [math]A, B \neq \emptyset[/math]; [math]A \cap B = \emptyset[/math]; [math]A \cup B = V[/math].

Такой разрез часто называют также глобальным разрезом, чтобы отличать его от [math](s,t)[/math]-разреза.

Определение:

Вес разреза [math]\langle A, B \rangle[/math] обозначается [math]w(A, B)[/math] и вычисляется по формуле: для взвешенного графа - [math]w(A, B) =[/math] [math]\sum\limits_{uv \in E, u \in A, v \in B} w(uv)[/math]; для невзвешенного графа - [math]w(A, B) = |\{uv: u \in A, v \in B\}|[/math].

Задача поиска разреза минимальной веса (англ. min-cut problem) заключается в поиске разреза минимального веса среди всех возможных разрезов исходного графа. Эту задачу можно решить с помощью любого из алгоритмов поиска максимального потока, зафиксировав произвольную вершину [math]s[/math] в качестве истока и запуская его [math]O(n)[/math] раз для всех возможных стоков. Если использовать быстрый алгоритм поиска максимального потока, работающий за [math]O(mn)[/math], то время работы такого алгоритма поиска минимального разреза будет [math]O(n^2m)[/math]. Однако ниже описан существенно более простой в реализации и более быстрый алгоритм Каргера.

Алгоритм

Пусть нам дан граф [math]G = \{V, E\}[/math].

minCut():
  answer = INF;
  for i = 1..c
    curCut = getCut();
    if curCut < answer
      answer = curCut;
  return answer;

Так как алгоритм вероятностный и функция [math]getCut[/math] возвращает вес случайного потока, а не минимального, то для того, чтобы наверняка найти вес минимального, необходим вызвать эту функцию [math]c[/math] раз. Какое конкретное значение [math]c[/math] выбрать будет описано ниже. Реализация функции [math]getCut[/math] — это и есть основа алгоритма. Будем действовать следующим образом: пока вершин больше двух, будем выбирать случайное ребро и стягивать его. Когда в графе останется две вершины, то количество ребер между этими вершинами будет равно весу некоторого разреза исходного графа.

getCut():
  n = количество вершин в G;
  while n > 2
    e = случайное ребро из G;
    contract(e);
    n--;
  m = количество ребер в G;
  return m;

Корректность алгоритма

Докажем корректность алгоритма. Для удобства доказательства и оценок вероятностей, будем считать, что мы ищем не просто вес минимального разреза, а величину конкретного минимального разреза. То есть зафиксируем какой-то один из минимальных разрезов, и если функция [math]getCut[/math] вернет правильный вес, но посчитает его на другом минимальном разрезе, то будем считать, что ответ получен неверный. Это условие не ухудшает оценки вероятностей и время работы алгоритма.

Лемма (1):

Пусть [math]w[/math] — некоторая мультивершина, [math]u[/math] и [math]v[/math] - какие-то две из вершин, которые были стянуты в вершину [math]w[/math]. Тогда существует такой путь [math]p[/math] в исходном графе [math]G[/math] между вершинами [math]u[/math] и [math]v[/math], что ко всем ребрам этого пути была применена операция стягивания.

Доказательство:

[math]\triangleright[/math]

Рассмотрим подграф [math]G'[/math] исходного графа [math]G[/math] в который входят все ребра, которые были стянуты в вершину [math]w[/math]. Очевидно, что [math]G'[/math] связен, а значит в нем существует путь между его любыми двумя вершина. Следовательно, существует путь между [math]u[/math] и [math]v[/math], состоящий из стянутых ребер. Лемма доказана.

[math]\triangleleft[/math]

Лемма (2):

Если стянуть некоторое ребро [math]e = uv[/math] в графе G, то вес минимального разреза в графе [math]G' = G\setminus e[/math] будет не меньше чем вес минимального разреза в исходном графе [math]G[/math].

Доказательство:

[math]\triangleright[/math]

Составим биекцию между ребрами графов [math]G[/math] и [math]G'[/math], не рассматривая ребра между вершинами [math]u[/math] и [math]v[/math] в графе [math]G[/math]. Очевидно, что это возможно, исходя из следующих соображений. Все ребра в [math]G[/math], не инцидентные вершинам [math]u[/math] и [math]v[/math], остались без изменений, а всем ребрам, инцидентным этим вершинам, по определению стягивания можно сопоставить новое ребро в [math]G'[/math]. Пусть [math]\langle A', B' \rangle[/math] — минимальный разрез в графе [math]G'[/math], и, не уменьшая общности, [math]w \in A'[/math]. Рассмотрим разрез [math]\langle A, B' \rangle[/math] в графе [math]G[/math]. Исходя из биекции между ребрами и тем, что все ребра вида [math]uv[/math] не пересекают разрез (так как [math]u \in A, v \in A[/math]), то [math]w(A', B') = w(A, B')[/math]. Тогда если разрез [math]\langle A, B' \rangle[/math] в графе [math]G[/math] — минимален, вес минимального разреза в [math]G'[/math] совпадает с весом минимального размера в [math]G[/math]. Если в [math]G[/math] существует разрез меньшего веса, то вес минимального разреза в [math]G'[/math] больше чем в [math]G[/math]. Лемма доказана.

[math]\triangleleft[/math]

Лемма (3):

Пусть [math]c[/math] — вес минимального потока в графе [math]G[/math]. Тогда [math]m \geq nc/2[/math].

Доказательство:

[math]\triangleright[/math]

Заметим, что, чтобы выполнялось условие, степень каждой вершины должна быть не менее, чем [math]c[/math]. Действительно, пусть [math]deg(v) \lt c[/math] для некоторой вершины [math]v \in V[/math]. Тогда [math]w(v, G \setminus v) = deg(v) \lt c[/math], что противоречит условию. Далее, по лемме о рукопожатиях имеем, что [math]m \geq nc/2[/math]. Лемма доказана.

[math]\triangleleft[/math]

Лемма (4):

Функция [math]getCut[/math] после своего выполнения получит стянутый граф [math]G'[/math] соответствующий конкретному разрезу [math]\langle A, B \rangle[/math] исходного графа [math]G[/math] тогда и только тогда, когда ни одно ребро, принадлежащее разрезу [math]\langle A, B \rangle[/math], не будет стянуто.

Доказательство:

[math]\triangleright[/math]

Необходимость: От противного. Если некоторое ребро [math]uv[/math], принадлежащее разрезу [math]\langle A, B \rangle[/math] в [math]G[/math] будет стянуто, то обе вершины [math]u[/math] и [math]v[/math] будут принадлежать одной мультивершине, а значит [math]G'[/math] не соответствует разрезу [math]\langle A, B \rangle[/math]. Противоречие. Достаточность: Пусть ни одно ребро, принадлежащее разрезу [math]\langle A, B \rangle[/math] не было стянуто. Рассмотри произвольную пару вершин [math]u \in A[/math] и [math]v \in B[/math] в графе [math]G[/math]. Если алгоритм стянул [math]u[/math] и [math]v[/math] в одну мультивершину в [math]G'[/math], тогда по лемме 1.

[math]\triangleleft[/math]