Изменения

Перейти к: навигация, поиск
Общий метод: новая тема
В описании общего метода не установлено никаких ограничений на алгоритм поиска максимального паросочетания. Соответственно, мы НЕ можем с уверенностью сказать, что для любого способа поиска максимального паросочетания на любой итерации алгоритма, у нас не будет добавляться ребро, которое было удалено на прошлой итерации, подразумевавшееся ненужным для увеличения паросочетания. И, как следствие, алгоритм теоретически может зациклится. Это серьезное упущение в доказательстве, которое даже ставит под сомнение корректность алгоритма. В связи с чем, прошу автора статьи срочно принять нужные меры.
 
== Общий метод ==
 
Утверждение о том, что добавляется 0 неверно. Контрпример:
012
000
034
 
В нем Xc это вторая строка, а Yc первый столбец. После указанных в статье преобразований таблица будет иметь вид:
001
100
023
 
То есть количество нулей не изменилось.
1
правка

Навигация