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 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 (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>
Нахождение разреза минимальной стоимости является основой в одном из методов сегментации изображений (сегментацией изображения называется разбиение его на некоторые области, непохожие по некоторому признаку).
Изображение представляется в виде взвешенного графа, вершинами которого являются точки изображения (как правило, пиксели, но, возможно, и большие области, от этого зависит качество сегментации, а также скорость ее её построения). Вес ребра представляет отражает "разницу" между точками (расстояние в некоторой метрике). Разбиение изображения на однородные области сводится к задаче поиска минимального разреза в графе. Специально для такого рода задач был предложен метод нахождения разреза минимальной стоимости [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))]
== Источники ==
