Много где пишут, что его корректность очевидно следует из теоремы Бержа. Однако не понятно, почему если увеличивающая цепь существует, алгоритм её найдет?
Ответ
Если я правильно понял, идея вот в чём. Пусть и правда существует увеличивающая цепь. Поскольку мы перебираем все стартовые вершины, мы в нашем переборе попробуем начать и со стартовой вершины увеличивающей цепи (которая, как мы предположили, существует). Мы перебираем по сути все чередующиеся цепочки (в терминах из текста по ссылке @ReinRaus) из этой вершины, так что при переборе мы должны добраться и до той самой существующей цепи.
Комментариев нет:
Отправить комментарий