Фрагмент из книги:
Для поиска увеличивающего пути можно попробовать запустить поиск в глубину из свободной вершины. Обход должен идти по чередующимся ребрам из паросочетания и не из него. Если найдется свободная вершина, то это будет означать наличие увеличивающего пути. Рассмотрим подробнее. Пусть есть некоторая вершина v при обходе и мы перебираем всех ее соседей не из паросочетания. Тогда в случае, если соседняя вершина и свободная, то найден увеличивающий путь, если насыщенная, но не посещенная, то надо ее посетить и запустить обход из ее пары в паросочетании.








