Изменения
Нет описания правки
#Если использовать фибоначчиевы кучи для нахождения вершины с наибольшей <tex>w</tex>, то асимптотика составит <tex>O(nm + n^2 \log n)</tex>
#Если использовать двоичные кучи, то асимптотика составит <tex>O(nm \log n + n^2)</tex>
== Применение ==
Нахождение разреза минимальной стоимости является основой в одном из методов сегментации изображений(сегментацией изображения называется разбиение его на некоторые области, непохожие по некоторому признаку).
Изображение представляется в виде взвешенного графа, вершинами которого являются точки изображения(скорее всего pixels, но может и области чуть больше, от этого зависит качество сегментации, а также скорость ее построения). Вес ребра представляет отражает "разницу" между точками(расстояние по некоторой введенной метрике). Разбиение изображения на однородные области сводится к задаче поиска минимального разреза в графе. Специально для такого рода задач был предложен метод нахождения разреза минимальной стоимости 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 Методы сегментации изображения]
== Ссылки ==
*[http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Каргера_для_нахождения_минимального_разреза Алгоритм Каргера нахождения минимального разреза]
*[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]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]
