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

Необходимые определения

[math]G[/math] - неориентированный взвешенный граф с [math]n[/math] вершинами и [math]m[/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]A[/math], а второй конец - [math]B[/math]. [math]w(A, B) =[/math] [math]\sum\limits_{uv \in E, u \in A, v \in B} w(u, v)[/math]

Эту задачу называют "глобальным минимальным разрезом". Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью любого алгоритма нахождения максимального потока (запуская его [math]O(n^2)[/math] раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (Mechthild Stoer) и Франком Вагнером (Frank Wagner) в 1994 г.

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

Алгоритм

Идея алгоритма довольно проста. Будем [math]n-1[/math] раз повторять следующий процесс: находить минимальный разрез между какой-нибудь парой вершин [math]s[/math] и [math]t[/math], а затем объединять эти две вершины в одну (создавать новую вершину, список смежности которой равен объединению списков смежности [math]s[/math] и [math]t[/math]). В конце концов, после [math]n-1[/math] итерации, останется одна вершина. После этого ответом будет являться минимальный среди всех [math]n-1[/math] найденных разрезов. Действительно, на каждой [math]i[/math]-ой стадии найденный минимальный разрез [math]\langle A,B \rangle[/math] между вершинами [math]s_i[/math] и [math]t_i[/math] либо окажется искомым глобальным минимальным разрезом, либо же, напротив, вершины [math]s_i[/math] и [math]t_i[/math] невыгодно относить к разным множествам, поэтому мы ничего не ухудшаем, объединяя эти две вершины в одну.

Следовательно нам необходимо для данного графа найти минимальный разрез между какой-нибудь парой вершин [math]s[/math] и [math]t[/math]. Для этого вводим некоторое множество вершин [math]A[/math], которое изначально содержит единственную произвольную вершину [math]s[/math]. На каждом шаге находится вершина, наиболее сильно связанная с множеством [math]A[/math], т.е. вершина [math]v \not\in A[/math], для которой следующая величина [math]w(v,A) = \sum\limits_{(v,u) \in E, \atop u \in A} w(v,u)[/math] максимальна (максимальна сумма весов рёбер, один конец которых [math]v[/math], а другой принадлежит [math]A[/math]). Этот процесс завершится, когда все вершины перейдут в множество [math]A[/math].

minCut(граф G):
  v[i] - список вершин, которые были сжаты в i-тую(сначала заполняется i);
  for i = 1..n-1
    обнуляем мн-во A;
    обнуляем w(связности всех вершин);
    for j = 1..n-1
      s = вершина не из A, для которой w[s] - максимальна;
      if (j != n-1)
        добавляем s в A;
        пересчитываем связность w[i] для остальных вершин; 
        prev = s;
      else
        if (w[s] < minCost)
          minCost = w[s];
          minCut = v[s];
        s и prev объединяются в одну вершину;
  return minCut - список вершин в минимальном разрезе;

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

Теорема:

Если добавить в множество [math]A[/math] по очереди все вершины, каждый раз добавляя вершину, наиболее сильно связанную с [math]A[/math], то пусть предпоследняя добавленная вершина — [math]s[/math], а последняя — [math]t[/math]. Тогда минимальный [math]s[/math]-[math]t[/math] разрез состоит из единственной вершины — [math]t[/math]

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

[math]\triangleright[/math]

Рассмотрим произвольный [math]s[/math]-[math]t[/math] разрез [math]C[/math] и покажем, что его вес не может быть меньше веса разреза, состоящего из единственной вершины [math]t[/math]: [math]w(\{t\}) \le w(C)[/math]. Пусть [math]v[/math] - вершина, которую мы хотим добавить в [math]A[/math], тогда [math]A_v[/math] - состояние множества [math]A[/math] в этот момент. Пусть [math]C_v[/math] - разрез множества [math]A_v \cup v[/math], индуцированный разрезом [math]C[/math]. Вершина [math]v[/math] - активная, если она и предыдущая добавленная вершина в [math]A[/math] принадлежат разным частям разреза [math]C[/math], тогда для любой такой вершины: [math]w(v, A_v) \le w(C_v)[/math]. [math]t[/math] - активная вершина, для нее выполняется: [math]w(t,A_t) \le w(C_t)[/math] [math]w(t,A_t) = w(\{t\}), w(C_t) = w(C)[/math] Получили утверждение теоремы. Для доказательства воспользуемся методом математической индукции. Для первой активной вершины [math]v[/math] это неравенство верно, так как все вершины [math]A_v[/math] принадлежат одной части разреза, а [math]v[/math] - другой. Пусть неравенство выполнено для всех активных вершин до [math]v[/math], включая [math]v[/math], докажем его для следующей активной вершины [math]u[/math]. [math] w(u,A_u) \equiv w(u,A_v) + w(u,A_u \setminus A_v)[/math] (*) Заметим, что [math]w(u,A_v) \le w(v,A_v)[/math] (**) вершина [math]v[/math] имела большее значение [math]w[/math], чем [math]u[/math], так как была добавлена в [math]A[/math] раньше. По предположению индукции: [math]w(v,A_v) \le w(C_v)[/math] Следовательно из (**): [math]w(u,A_v) \le w(C_v)[/math] А из (*) имеем: [math]w(u,A_u) \le w(C_v) + w(u,A_u \setminus A_v)[/math] Вершина [math]u[/math] и [math]A_u \setminus A_v[/math] находятся в разных частях разреза [math]C[/math], значит [math]w(u,A_u \setminus A_v)[/math] равна сумме весов ребер, которые не входят в [math]C_v[/math], но входят в [math]C_u[/math]. [math]w(u,A_u) \le w(C_v) + w(u,A_u \setminus A_v) \le w(C_u)[/math] Что и требовалось доказать.

[math]\triangleleft[/math]

Асимптотика

1. Нахождение вершины с наибольшей [math]w[/math] за [math]O(n)[/math], [math]n-1[/math] фаза по [math]n-1[/math] итерации в каждой. В итоге имеем [math]O(n^3)[/math]
2. Если использовать фибоначчиевы кучи для нахождения вершины с наибольшей [math]w[/math], то асимптотика составит [math]O(nm + n^2 \log n)[/math]
3. Если использовать двоичные кучи, то асимптотика составит [math]O(nm \log n + n^2)[/math]

Источники

• Mechthild Stoer, Frank Wagner. A Simple Min-Cut Algorithm
• Алгоритм Штор-Вагнера

Ссылки

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