105
правок
Изменения
м
ё
== Необходимые определения ==
<tex>G</tex> - неориентированный взвешенный граф с <tex>n</tex> вершинами и <tex>m</tex> ребрамирёбрами.
{{Определение |definition=
'''Разрезом''' называется такое разбиение множества <tex>V</tex> на два подмножества <tex>A</tex> и <tex>B</tex>, что:
}}
Эту задачу называют "глобальным минимальным разрезом". Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью любого алгоритма нахождения максимального потока (запуская его <tex>O(n^2) </tex> раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (Mechthild Stoer) и Франком Вагнером (Frank Wagner) в 1994 г.
В общем случае допускаются петли и кратные рёбра, все кратные рёбра можно заменить одним ребром с их суммарным весом а петли не влияют на решение. Поэтому будем считать, что кратных ребер рёбер и петель во входном графе нет.
== Алгоритм ==
Идея алгоритма довольно проста. Будем <tex>n-1</tex> раз повторять следующий процесс: находить минимальный разрез между какой-нибудь парой вершин <tex>s</tex> и <tex>t</tex>, а затем объединять эти две вершины в одну (создавать новую вершину, список смежности которой равен объединению списков смежности <tex>s</tex> и <tex>t</tex>). В конце концов, после <tex>n-1</tex> итерации, останется одна вершина. После этого ответом будет являться минимальный среди всех <tex>n-1</tex> найденных разрезов. Действительно, на каждой <tex>i</tex>-ой стадии найденный минимальный разрез <tex>\langle A,B \rangle</tex> между вершинами <tex>s_i</tex> и <tex>t_i</tex> либо окажется искомым глобальным минимальным разрезом, либо же, напротив, вершины <tex>s_i</tex> и <tex>t_i</tex> невыгодно относить к разным множествам, поэтому мы ничего не ухудшаем, объединяя эти две вершины в одну.
Следовательно нам необходимо для данного графа найти минимальный разрез между какой-нибудь парой вершин <tex>s</tex> и <tex>t</tex>. Для этого вводим некоторое множество вершин <tex>A</tex>, которое изначально содержит единственную произвольную вершину <tex>s</tex>. На каждом шаге находится вершина, наиболее сильно связанная с множеством <tex>A</tex>, т.е. вершина <tex>v \not\in A</tex>, для которой следующая величина <tex dpi = "140">w(v,A) = \sum\limits_{(v,u) \in E, \atop u \in A} w(v,u)</tex> максимальна (максимальна сумма весов рёбер, один конец которых <tex>v</tex>, а другой принадлежит <tex>A</tex>).Этот процесс завершится, когда все вершины перейдут в множество <tex>A</tex>. minCut(граф G): v[i] - список вершин, которые были сжаты в i-тую (сначала заполняется i); for i = 1..n-1 A = Ø; fill(w, 0); for j = 1..n-1 s = {s <tex>\in</tex> V | s <tex>\notin</tex> 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 <tex>\cup</tex> prev; return minCut - список вершин в минимальном разрезе; == Корректность алгоритма =={{Теорема|statement=Если добавить в множество <tex>A</tex> по очереди все вершины, каждый раз добавляя вершину, наиболее сильно связанную с <tex>A</tex>, то пусть предпоследняя добавленная вершина {{---}} <tex>s</tex>, а последняя {{---}} <tex>t</tex>. Тогда минимальный <tex>s</tex>-<tex>t</tex> разрез состоит из единственной вершины {{---}} <tex>t</tex>|proof=Рассмотрим произвольный <tex>s</tex>-<tex>t</tex> разрез <tex>C</tex> и покажем, что его вес не может быть меньше веса разреза, состоящего из единственной вершины <tex>t</tex>: : <tex dpi = '130'>w (\{t\}) \le w (C)</tex>. Пусть <tex>v</tex> - вершина, которую мы хотим добавить в <tex>A</tex>, тогда <tex>A_v</tex> - состояние множества <tex>A</tex> в этот момент. Пусть <tex>C_v</tex> - разрез множества <tex>A_v \cup v</tex>, индуцированный разрезом <tex>C</tex>. Вершина <tex>v</tex> - активная, если она и предыдущая добавленная вершина в <tex>A</tex> принадлежат разным частям разреза <tex>C</tex>, тогда для любой такой вершины: : <tex dpi = '130'>w (v, A_v) \le w (C_v)</tex>. <tex>t</tex> - активная вершина, для неё выполняется: : <tex dpi = '130'>w (t,A_t) \le w (C_t)</tex> : <tex dpi = '130'>w (t,A_t) = w (\{t\}), w (C_t) = w (C)</tex> Получили утверждение теоремы.Для доказательства воспользуемся методом математической индукции.Для первой активной вершины <tex>v</tex> это неравенство верно, так как все вершины <tex>A_v</tex> принадлежат одной части разреза, а <tex>v</tex> - другой. Пусть неравенство выполнено для всех активных вершин до <tex>v</tex>, включая <tex>v</tex>, докажем его для следующей активной вершины <tex>u</tex>. : <tex dpi = '130'> w (u,A_u) \equiv w (u,A_v) + w (u,A_u \setminus A_v)</tex> (*) Заметим, что : <tex dpi = '130'>w (u,A_v) \le w (v,A_v)</tex> (**) вершина <tex>v</tex> имела большее значение <tex>w</tex>, чем <tex>u</tex>, так как была добавлена в <tex>A</tex> раньше.По предположению индукции: : <tex dpi = '130'>w (v,A_v) \le w (C_v)</tex> Следовательно из (**): : <tex dpi = '130'>w(u,A_v) \le w(C_v)</tex> А из (*) имеем: : <tex dpi = '130'>w (u,A_u) \le w (C_v) + w (u,A_u \setminus A_v)</tex> Вершина <tex>u</tex> и <tex>A_u \setminus A_v</tex> находятся в разных частях разреза <tex>C</tex>, значит <tex>w (u,A_u \setminus A_v)</tex> равна сумме весов рёбер, которые не входят в <tex>C_v</tex>, но входят в <tex>C_u</tex>. : <tex dpi = '130'>w (u,A_u) \le w (C_v) + w (u,A_u \setminus A_v) \le w (C_u)</tex> Что и требовалось доказать.}} == Асимптотика ==#Нахождение вершины с наибольшей <tex>w</tex> за <tex>O (n)</tex>, <tex>n-1</tex> фаза по <tex>n-1</tex> итерации в каждой. В итоге имеем <tex>O (n^3)</tex>#Если использовать фибоначчиевы кучи для нахождения вершины с наибольшей <tex>w</tex>, то асимптотика составит <tex>O (nm + n^2 \log n)</tex>#Если использовать двоичные кучи, то асимптотика составит <tex>O (nm \log n + n^2)</tex> == Применение ==Нахождение разреза минимальной стоимости является основой в одном из методов сегментации изображений (сегментацией изображения называется разбиение его на некоторые области, непохожие по некоторому признаку). Изображение представляется в виде взвешенного графа, вершинами которого являются точки изображения (как правило, пиксели, но, возможно, и большие области, от этого зависит качество сегментации, а также скорость её построения). Вес ребра представляет отражает "разницу" между точками (расстояние в некоторой метрике). Разбиение изображения на однородные области сводится к задаче поиска минимального разреза в графе. Специально для такого рода задач был предложен метод нахождения разреза минимальной стоимости [https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CDQQFjAB&url=http%3A%2F%2Fwww.cs.berkeley.edu%2F~malik%2Fpapers%2FSM-ncut.pdf&ei=cP2-UuqhAuSJ4gTnhYCwAg&usg=AFQjCNFn9GZPlFjDUgDofCScu6Wm47qMWQ&sig2=Yufd8LreEQKHe3NGnFVm7A&bvm=bv.58187178,d.bGE&cad=rjt Normalized Cut (J. Shi, J. Malik (1997))] == Источники ==* [http://e-maxx.ru/bookz/files/stoer_wagner_mincut.pdf Mechthild Stoer, Frank Wagner. A Simple Min-Cut Algorithm]* [http://e-maxx.ru/algo/stoer_wagner_mincut Алгоритм Штор-Вагнера]* [http://cgm.computergraphics.ru/content/view/147 Методы сегментации изображения] == Ссылки ==*[[Алгоритм Каргера для нахождения минимального разреза]]*[https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CDQQFjAB&url=http%3A%2F%2Fwww.cs.berkeley.edu%2F~malik%2Fpapers%2FSM-ncut.pdf&ei=cP2-UuqhAuSJ4gTnhYCwAg&usg=AFQjCNFn9GZPlFjDUgDofCScu6Wm47qMWQ&sig2=Yufd8LreEQKHe3NGnFVm7A&bvm=bv.58187178,d.bGE&cad=rjt Метод Normalized Cut] [[Категория: Алгоритмы и структуры данных]][[Категория: Задача о максимальном потоке]]
