Алгоритм Штор-Вагнера нахождения минимального разреза
Необходимые определения
- неориентированный взвешенный граф с вершинами и рёбрами.
| Определение: |
Разрезом называется такое разбиение множества на два подмножества и , что:
|
| Определение: |
| Весом разреза называется сумма весов рёбер, проходящих через разрез, т.е. таких рёбер, один конец которых принадлежит , а второй конец - .
|
Эту задачу называют "глобальным минимальным разрезом". Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью любого алгоритма нахождения максимального потока (запуская его раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (Mechthild Stoer) и Франком Вагнером (Frank Wagner) в 1994 г.
В общем случае допускаются петли и кратные рёбра, все кратные рёбра можно заменить одним ребром с их суммарным весом а петли не влияют на решение. Поэтому будем считать, что кратных рёбер и петель во входном графе нет.
Алгоритм
Идея алгоритма довольно проста. Будем раз повторять следующий процесс: находить минимальный разрез между какой-нибудь парой вершин и , а затем объединять эти две вершины в одну (создавать новую вершину, список смежности которой равен объединению списков смежности и ). В конце концов, после итерации, останется одна вершина. После этого ответом будет являться минимальный среди всех найденных разрезов. Действительно, на каждой -ой стадии найденный минимальный разрез между вершинами и либо окажется искомым глобальным минимальным разрезом, либо же, напротив, вершины и невыгодно относить к разным множествам, поэтому мы ничего не ухудшаем, объединяя эти две вершины в одну.
Следовательно нам необходимо для данного графа найти минимальный разрез между какой-нибудь парой вершин и . Для этого вводим некоторое множество вершин , которое изначально содержит единственную произвольную вершину . На каждом шаге находится вершина, наиболее сильно связанная с множеством , т.е. вершина , для которой следующая величина максимальна (максимальна сумма весов рёбер, один конец которых , а другой принадлежит ). Этот процесс завершится, когда все вершины перейдут в множество .
minCut(граф G):
v[i] - список вершин, которые были сжаты в i-тую (сначала заполняется i);
for i = 1..n-1
A = Ø;
fill(w, 0);
for j = 1..n-1
s = {s V | s 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 prev;
return minCut - список вершин в минимальном разрезе;
Корректность алгоритма
| Теорема: |
Если добавить в множество по очереди все вершины, каждый раз добавляя вершину, наиболее сильно связанную с , то пусть предпоследняя добавленная вершина — , а последняя — . Тогда минимальный - разрез состоит из единственной вершины — |
| Доказательство: |
|
Рассмотрим произвольный - разрез и покажем, что его вес не может быть меньше веса разреза, состоящего из единственной вершины :
Пусть - вершина, которую мы хотим добавить в , тогда - состояние множества в этот момент. Пусть - разрез множества , индуцированный разрезом . Вершина - активная, если она и предыдущая добавленная вершина в принадлежат разным частям разреза , тогда для любой такой вершины:
- активная вершина, для неё выполняется: Получили утверждение теоремы. Для доказательства воспользуемся методом математической индукции. Для первой активной вершины это неравенство верно, так как все вершины принадлежат одной части разреза, а - другой. Пусть неравенство выполнено для всех активных вершин до , включая , докажем его для следующей активной вершины .
Заметим, что
вершина имела большее значение , чем , так как была добавлена в раньше. По предположению индукции: Следовательно из (**): А из (*) имеем: Вершина и находятся в разных частях разреза , значит равна сумме весов рёбер, которые не входят в , но входят в . |
Асимптотика
- Нахождение вершины с наибольшей за , фаза по итерации в каждой. В итоге имеем
- Если использовать фибоначчиевы кучи для нахождения вершины с наибольшей , то асимптотика составит
- Если использовать двоичные кучи, то асимптотика составит
Применение
Нахождение разреза минимальной стоимости является основой в одном из методов сегментации изображений (сегментацией изображения называется разбиение его на некоторые области, непохожие по некоторому признаку).
Изображение представляется в виде взвешенного графа, вершинами которого являются точки изображения (как правило, пиксели, но, возможно, и большие области, от этого зависит качество сегментации, а также скорость её построения). Вес ребра представляет отражает "разницу" между точками (расстояние в некоторой метрике). Разбиение изображения на однородные области сводится к задаче поиска минимального разреза в графе. Специально для такого рода задач был предложен метод нахождения разреза минимальной стоимости Normalized Cut (J. Shi, J. Malik (1997))
