Изменения
Нет описания правки
Пусть дан взвешенный полный двудольный граф <tex> K_{n, n} </tex>, нужно найти в нем полное паросочетание минимального веса. Вес паросочетания определяется как сумма весов его ребер.
== Некоторые полезные соображения ==
{{Лемма
|statement=
Если веса всех ребер графа, инцидентных какой-либо вершине, изменить на одно и то же число, то в новом графе оптимальное паросочетание будет состоять из тех же ребер, что и в старом.
|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=
ну тут кагбе все очевидно, лол
}}
{{Лемма
|statement=
Если веса всех ребер графа неотрицательны и некоторое полное паросочетание состоит из ребер нулевого веса, то оно является оптимальным
|proof=
Действительно, паросочетание с какими-то другими весами ребер имеет больший вес и оптимальным не является.
}}
== Алгоритм ==
Доказанные ранее утверждения позволяют придумать схему алгоритма, решающего задачу о назначениях: нужно найти полное паросочетание из ребер нулевого веса в графе, полученном из исходного преобразованиями, описанными в первых двух леммах.
Алгоритм, решающий задачу, работает с графом, как с матрицей весов.
# Вычитаем из каждой строки значение ее минимального элемента. Теперь в каждой строке есть хотя бы один нулевой элемент.
# Вычитаем из каждого столбца значение его минимального элемента. Теперь в каждом столбце есть хотя бы один нулевой элемент.
# Ищем в текущем графе полное паросочетание из ребер нулевого веса:
## Если оно найдено, то желаемый результат достигнут.
## В противном случае, покроем нули матрицы весов минимальным количеством строк и столбцов (это не что иное, как нахождение минимального контролирующего множества в двудольном графе). Теперь применим преобразование из леммы 2, взяв в качестве <tex> X' </tex> и <tex> Y' </tex> вершины левой и правой долей минимального контролирующего множества. Очевидно, после его выполнения в матрице весов появится новый нуль. После этого перейдем к шагу 1.
== Анализ времени работы ==
<tex> O(n^3) </tex> и баста!
== Ссылки ==
* [http://acm.mipt.ru/twiki/bin/view/Algorithms/HungarianAlgorithmCPP?sortcol=5&table=2&up=0 Статья, которая может помочь]
* [http://ru.wikipedia.org/wiki/Венгерский_алгоритм w:Венгерский алготитм]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/hungarian-2002 Визуализатор алгоритма]
== Литература ==
* Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
[[Категория: Задача о потоке минимальной стоимости]]
