Изменения
Нет описания правки
minCut(граф G):
v[i] - список вершин, которые были сжаты в i-тую(сначала заполняется i);
for i = 1..n-1
A = Ø;
Рассмотрим произвольный <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_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>
== Применение ==
Нахождение разреза минимальной стоимости является основой в одном из методов сегментации изображений(сегментацией изображения называется разбиение его на некоторые области, непохожие по некоторому признаку).
Изображение представляется в виде взвешенного графа, вершинами которого являются точки изображения(скорее всего pixels, пиксели но может и области чуть больше, от этого зависит качество сегментации, а также скорость ее построения). Вес ребра представляет отражает "разницу" между точками(расстояние по некоторой введенной метрике). Разбиение изображения на однородные области сводится к задаче поиска минимального разреза в графе. Специально для такого рода задач был предложен метод нахождения разреза минимальной стоимости [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 Normalized Cut(J. Shi, J. Malik (1997))]
== Источники ==
== Ссылки ==
*[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]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]
