689
правок
Изменения
м
* [http://ru.wikipedia.org/wiki/Венгерский_алгоритм w:Венгерский алготитм]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/hungarian-2002 Визуализатор алгоритма]
кое-что исправил
Венгерский алгоритм — алгоритм, придуманный решающий задачу о назначениях за полиномиальное время. Оригинальная версия была придумана и разработана Х. Куном в 1955 годуи имела асимптотику <tex> O(n^4) </tex>, решает задачу о назначениях за но позже Эдмонс и Карп (а также, независимо от них, Томидзава) показали, что можно улучшить ее до <tex> O(n^3) </tex> операций.
== Постановка задачи ==
Если веса всех ребер графа, инцидентных какой-либо вершине, изменить на одно и то же число, то в новом графе оптимальное паросочетание будет состоять из тех же ребер, что и в старом.
|proof=
Полное паросочетание для каждой вершины содержит ровно одно ребро, инцидентное этой вершине. Указанная операция изменит на одно и то же число вес любого паросочетания. При изменении весов всех ребер, инцидентных ейданной вершине, на одно и то же число, выбранное ребро останется оптимальным.
}}
|statement=
Выделим в множествах <tex>X</tex> и <tex>Y</tex> подмножества <tex>X', Y'</tex>. Если прибавить ко всем весам ребер, инцидентных вершинам из <tex>X</tex>, прибавить, а потом от всех весов ребер, инцидентных вершинам из <tex>Y</tex>, отнять <tex>d = \min \{c(x, y)|x \in X', y \in Y\backslash Y'\}</tex>, то:
# веса Веса всех ребер графа останутся неотрицательными;.
# Веса ребер вида <tex>xy</tex>, где <tex>x \in X', y \in Y'</tex> или <tex>x \in X \backslash X', y \in Y \backslash Y'</tex>, не изменятся.
|proof=
Рассмотрим матрицу весов графа. Не умаляя общности, можно сказать, что множества <tex> X' </tex> и <tex> Y' </tex> состоят из первых элементов множеств <tex> X </tex> и <tex> Y </tex> соответственно (мы упорядочиваем множества по номерам вершин). Тогда вся матрица делится на 4 блока:
<table border = '1' bordercolor = 'black' rules = 'rowsall' cellpadding = '5'>
<tr>
<td> </td>
</table>
Веса группы <tex> A </tex> будут сначала увеличены, а потом уменьшены на <tex> d </tex>, поэтому они не изменятся, веса группы <tex> D </tex> вообще изменяться не будут. Все веса группы <tex> B </tex> будут уменьшены на <tex> d </tex>, но <tex> d </tex> - — минимум среди этих весов, поэтому они останутся неотрицательными.
}}
# Ищем в текущем графе полное паросочетание из ребер нулевого веса:
#
## * Если оно найдено, то желаемый результат достигнут, алгоритм закончен.## * В противном случае, покроем нули матрицы весов минимальным количеством строк и столбцов (это не что иное, как нахождение минимального контролирующего множества в двудольном графе). Теперь применим преобразование из леммы 2, взяв в качестве <tex> X' </tex> и <tex> Y' </tex> вершины левой и правой долей минимального контролирующего множества. Очевидно, после его выполнения в матрице весов появится новый нуль. После этого перейдем к шагу 1.
== Анализ времени работы ==
Поиск максимального паросочетания или минимального контролирующего множества в двудольном графе совершается за <tex> O(n^2) </tex> операций. При каждом повторении шагов 1-3 в матрице весов появляется новый нуль, который увеличивает размер максимального паросочетания хотя бы на 1, поэтому всего будет совершено <tex> O(n) </tex> итераций внешнего цикла. Поэтому суммарная асимптотика работы данного алгоритма - — <tex> O(n^3) </tex>.
== Ссылки ==
* [http://ru.wikipedia.org/wiki/Венгерский_алгоритм Венгерский алготитм в Википедии]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/hungarian-2002 Визуализатор алгоритма]
* [http://acm.mipt.ru/twiki/bin/view/Algorithms/HungarianAlgorithmCPP?sortcol=5&table=2&up=0 Реализация венгерского алгоритма на C++]
== Литература ==
* Асанов М., Баранский В., Расин В. - — Дискретная математика: Графы, матроиды, алгоритмы — 2010, 368 стр.
[[Категория: Задача о потоке минимальной стоимости]]
