Доказательство корректности алгоритма Куна для нахождения максимального паросочетания

#алгоритм #графы

Много где пишут, что его корректность очевидно следует из теоремы Бержа. Однако не
понятно, почему если увеличивающая цепь существует, алгоритм её найдет?    

Ответы

Ответ 1

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