6

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

2
  • 1
    Вас не затруднит сформулировать теорему и алгоритм? Или хотя бы привести ссылку на формулировку.
    – VladD
    30 янв 2013 в 16:58
  • e-maxx.ru/algo/kuhn_matching
    – ReinRaus
    30 янв 2013 в 17:04

1 ответ 1

3

Если я правильно понял, идея вот в чём.

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.