Изменения

'''Венгерский алгоритм ''' (англ. '''Hungarian algorithm''') — алгоритм, решающий задачу о назначениях за полиномиальное время. Оригинальная версия была придумана и разработана Х. Куном в 1955 году и имела асимптотику <tex> O(n^4) </tex>, но позже Эдмонс и Карп (а также, независимо от них, Томидзава) показали, что можно улучшить ее до <tex> O(n^3) </tex>.{{Задача|definition == Постановка задачи == Пусть дан [[Основные определения теории графов|взвешенный полный двудольный граф]] c целыми весами ребер <tex> K_{n, n} </tex>, нужно найти в нем [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях|полное паросочетание минимального веса]]. Вес [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях|паросочетания]] определяется как сумма весов его ребер. Далее будем обозначать левую и правую доли графа за <tex> X </tex> и <tex> Y </tex> соответственно, вес ребра <tex> xy </tex> — как <tex> c(xy) </tex>.}}

== Некоторые полезные утверждения Вспомогательные леммы ==

Выделим в множествах <tex>X</tex> и <tex>Y</tex> подмножества <tex>X', Y'</tex>. Пусть <tex>d = \min \{c(xy)|\ mid x \in X \setminus X', y \in Y'\}</tex>. Прибавим <tex> d </tex> ко всем весам ребер, инцидентных вершинам из <tex>X'</tex>. Затем отнимем <tex> d </tex> от всех весов ребер, инцидентных вершинам из <tex>Y'</tex> (далее для краткости эта операция обозначается как <tex> X' \uparrow\downarrow Y' </tex>). Тогда:

<tex> \mathtt{a[1 \dots n][1 \dots m] } </tex> {{---}} прямоугольная входная матрица, где <tex> \mathtt{n \leq leqslant m } </tex>. Матрица хранится в 1-индексации.

<tex> \mathtt{u[0 \dots n], v[0 \dots n] } </tex> {{---}} массивы потенциалов. Изначально нулевые, что верно для матрицы, состоящей из 0 строк.

<tex> \mathtt{p[0 \dots m] } </tex> {{---}} массив паросочетания. Для каждого стобца <tex> \mathtt{i = 0 \dots m } </tex> он хранит номер соответствующей выбранной строки <tex> \mathtt{p[i] } </tex> (или 0, если ничего не выбрано). Полагаем, что <tex> \mathtt{p[0] } </tex> равно номеру рассматриваемой строки.

<tex> \mathtt{minv[1 \dots m] } </tex> {{---}} массив, хранящий для каждого столбца j вспомогательные минимумы, необходимые для быстрого пересчета потенциала.

<tex> \mathtt{minv[j] = \min_{i \in Z_1}\{a[i][j] - u[i] - v[j]\}} </tex>

<tex> \mathtt{way[1 \dots m] } </tex> {{---}} массив, содержащий информацию о том, где эти минимумы достигаются, чтобы мы могли впоследствии восстановить [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях|увеличивающую цепочку]].

'''for''' i = 0 '''to''' m + 1 заполняем массивы minv[i] = {{---}} <tex> \infty </tex> , used[i] = {{---}} false

== Ссылки См. также == == Источники информации ==* Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — 2010, 368 стр.