Венгерский алгоритм решения задачи о назначениях

Венгерский алгоритм, придуманный Х. Куном в 1955 году, решает задачу о назначениях за [math] O(n^3) [/math] операций.

Постановка задачи

Пусть дан взвешенный полный двудольный граф [math] K_{n, n} [/math], нужно найти в нем полное паросочетание минимального веса. Вес паросочетания определяется как сумма весов его ребер.

Некоторые полезные соображения

Лемма:

Если веса всех ребер графа, инцидентных какой-либо вершине, изменить на одно и то же число, то в новом графе оптимальное паросочетание будет состоять из тех же ребер, что и в старом.

Доказательство:

[math]\triangleright[/math]

Полное паросочетание для каждой вершины содержит ровно одно ребро, инцидентное этой вершине. Отсюда все следует.

[math]\triangleleft[/math]

Далее будем рассматривать только графы с неотрицательной весовой функцией, так задачу о назначениях на остальных графах можно свести к этим.

Лемма:

Выделим в множествах [math]X[/math] и [math]Y[/math] подмножества [math]X', Y'[/math]. Если прибавить ко всем весам ребер, инцидентных вершинам из [math]X[/math], прибавить, а потом от всех весов ребер, инцидентных вершинам из [math]Y[/math], отнять [math]d = \min{c(x, y)|x \in X', y \in Y\backslash Y'}[/math], то: веса всех ребер графа останутся неотрицательными; Веса ребер вида [math]xy[/math], где [math]x \in X', y \in Y'[/math] или [math]x \in X \backslash X', y \in Y \backslash Y'[/math], не изменятся.

Доказательство:

[math]\triangleright[/math]

ну тут кагбе все очевидно, лол

[math]\triangleleft[/math]

Лемма:

Если веса всех ребер графа неотрицательны и некоторое полное паросочетание состоит из ребер нулевого веса, то оно является оптимальным

Доказательство:

[math]\triangleright[/math]

Действительно, паросочетание с какими-то другими весами ребер имеет больший вес и оптимальным не является.

[math]\triangleleft[/math]

Алгоритм

Доказанные ранее утверждения позволяют придумать схему алгоритма, решающего задачу о назначениях: нужно найти полное паросочетание из ребер нулевого веса в графе, полученном из исходного преобразованиями, описанными в первых двух леммах.

Алгоритм, решающий задачу, работает с графом, как с матрицей весов.

1. Вычитаем из каждой строки значение ее минимального элемента. Теперь в каждой строке есть хотя бы один нулевой элемент.
2. Вычитаем из каждого столбца значение его минимального элемента. Теперь в каждом столбце есть хотя бы один нулевой элемент.
3. Ищем в текущем графе полное паросочетание из ребер нулевого веса:
   1. Если оно найдено, то желаемый результат достигнут.
   2. В противном случае, покроем нули матрицы весов минимальным количеством строк и столбцов (это не что иное, как нахождение минимального контролирующего множества в двудольном графе). Теперь применим преобразование из леммы 2, взяв в качестве [math] X' [/math] и [math] Y' [/math] вершины левой и правой долей минимального контролирующего множества. Очевидно, после его выполнения в матрице весов появится новый нуль. После этого перейдем к шагу 1.

Анализ времени работы

[math] O(n^3) [/math] и баста!

Ссылки

• Статья, которая может помочь
• w:Венгерский алготитм
• Визуализатор алгоритма

Литература

• Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.