Изменения

Пусть дан взвешенный полный двудольный граф <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)|\ x \in X \setminus X', y \in Y'\}</tex>. Прибавим <tex> d </tex> ко всем весам ребер, инцидентных вершинам из <tex>X'</tex>. Затем отнимем <tex> d </tex>, прибавить, а потом от всех весов ребер, инцидентных вершинам из <tex>Y</tex>, отнять <tex>d = \min \{c(x, y)|x \in X', y \in Y\backslash Y'\}</tex>, то. Тогда:

#* В противном случае, покроем нули матрицы весов минимальным количеством строк и столбцов (это не что иное, как [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах|нахождение минимального контролирующего множества вершинного покрытия в двудольном графе]]). Теперь применим преобразование из леммы 2. Пусть множества вершин минимального вершинного покрытия из левой и правой долей — <tex> X_c </tex> и <tex> Y_c </tex> соответственно, взяв в качестве тогда берем <tex> X' = X_c, Y' = Y \setminus Y_c </tex>. Для этого преобразования <tex> d </tex> будет минимумом по всем ребрам между <tex> X \setminus X_c </tex> и <tex> Y' \setminus Y_c </tex> вершины левой и правой долей минимального контролирующего множества. Очевидно, то есть, ребер нулевого веса здесь нет, поэтому, после его выполнения в матрице весов появится новый нуль. После этого перейдем к шагу 1.

Поиск максимального паросочетания или минимального контролирующего множества в двудольном графе совершается за <tex> O(n^23) </tex> операций. При каждом повторении шагов 1-3 в матрице весов появляется новый нуль, который увеличивает размер максимального паросочетания хотя бы на 1, поэтому всего будет совершено <tex> O(n) </tex> итераций внешнего цикла. Поэтому , суммарная асимптотика работы данного данной версии венгерского алгоритма — <tex> O(n^4) </tex>. В книге Асанова, а также в реализации на C++ по ссылке ниже предложена оптимизация, которая позволяет улучшить время работы до <tex> O(n^3) </tex>.