Изменения

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