36
правок
Изменения
Новая страница: «== Алгоритм Штор-Вагнера нахождения минимального разреза == == Необходимые определения == <...»
== Алгоритм Штор-Вагнера нахождения минимального разреза ==
== Необходимые определения ==
<tex>G</tex> - неориентированный взвешенный граф с <tex>n</tex> вершинами и <tex>m</tex> ребрами.
{{Определение |definition=
'''Разрезом''' называется такое разбиение множества <tex>V</tex> на два подмножества <tex>A</tex> и <tex>B</tex>, что:
* <tex>A, B \subset V</tex>;
* <tex>A, B \neq \emptyset</tex>;
* <tex>A \cap B = \emptyset</tex>;
* <tex>A \cup B = V</tex>.
}}
{{Определение |definition=
'''Весом разреза''' называется сумма весов рёбер, проходящих через разрез, т.е. таких рёбер, один конец которых принадлежит <tex>A</tex>, а второй конец - <tex>B</tex>.
* <tex>w(A, B) =</tex> <tex dpi = "140">\sum\limits_{uv \in E, u \in A, v \in B} w(u, v)</tex>
}}
Эту задачу называют "глобальным минимальным разрезом". Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью любого алгоритма нахождения максимального потока (запуская его O(n^2) раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (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>G</tex> - неориентированный взвешенный граф с <tex>n</tex> вершинами и <tex>m</tex> ребрами.
{{Определение |definition=
'''Разрезом''' называется такое разбиение множества <tex>V</tex> на два подмножества <tex>A</tex> и <tex>B</tex>, что:
* <tex>A, B \subset V</tex>;
* <tex>A, B \neq \emptyset</tex>;
* <tex>A \cap B = \emptyset</tex>;
* <tex>A \cup B = V</tex>.
}}
{{Определение |definition=
'''Весом разреза''' называется сумма весов рёбер, проходящих через разрез, т.е. таких рёбер, один конец которых принадлежит <tex>A</tex>, а второй конец - <tex>B</tex>.
* <tex>w(A, B) =</tex> <tex dpi = "140">\sum\limits_{uv \in E, u \in A, v \in B} w(u, v)</tex>
}}
Эту задачу называют "глобальным минимальным разрезом". Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью любого алгоритма нахождения максимального потока (запуская его O(n^2) раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (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>).
