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

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

$G$ - неориентированный взвешенный граф с $n$ вершинами и $m$ рёбрами.

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

Разрезом называется такое разбиение множества $V$ на два подмножества $A$ и $B$, что: $A, B \subset V$; $A, B \neq \emptyset$; $A \cap B = \emptyset$; $A \cup B = V$.

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

Весом разреза называется сумма весов рёбер, проходящих через разрез, т.е. таких рёбер, один конец которых принадлежит $A$, а второй конец - $B$. $w(A, B) =$ $\sum\limits_{uv \in E, u \in A, v \in B} w(u, v)$

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

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

Алгоритм

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

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

minCut(граф G):
  v[i] - список вершин, которые были сжаты в i-тую (сначала заполняется i);
  for i = 1..n-1
    A = Ø;
    fill(w, 0);
    for j = 1..n-1
      s = {s $\in$ V | s $\notin$ A, w[s] - max};
      if (j != n-1)
        A += s;
        пересчитываем связность w[i] для остальных вершин; 
        prev = s;
      else
        if (w[s] < minCost)
          minCost = w[s];
          minCut = v[s];
        s' = s $\cup$ prev;
  return minCut - список вершин в минимальном разрезе;

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

Теорема:

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

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

$\triangleright$

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

$\triangleleft$

Асимптотика

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

Применение

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

Изображение представляется в виде взвешенного графа, вершинами которого являются точки изображения (как правило, пиксели, но, возможно, и большие области, от этого зависит качество сегментации, а также скорость её построения). Вес ребра представляет отражает "разницу" между точками (расстояние в некоторой метрике). Разбиение изображения на однородные области сводится к задаче поиска минимального разреза в графе. Специально для такого рода задач был предложен метод нахождения разреза минимальной стоимости Normalized Cut (J. Shi, J. Malik (1997))

Источники

• Mechthild Stoer, Frank Wagner. A Simple Min-Cut Algorithm
• Алгоритм Штор-Вагнера
• Методы сегментации изображения

Ссылки

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