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

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

1. ­Вычитают из каждой строки её минимальный элемент (строчное редуцирование).
2. ­Из полученной матрицы для каждого столбца вычитают минимальный элемент столбца (столбцовое редуцирование).

Наша исходная матрица (4×4) выглядит так:

3  5  4  6   2  7  2  5   4  8  3  9   5  6  2  7

...