Изменения

Рассмотрим неориентированный невзвешенный[[Основные определения теории графов|граф]] <tex> G =\langle V, E \rangle </tex>, где <tex>V </tex> {{---}} множество [[Основные определения теории графов| вершин]], <tex>E </tex> {{---}} множество [[Основные определения теории графов|ребер]]. Требуется найти в нем максимальное паросочетание.

Приведем пример, на котором [[Алгоритм Куна для поиска максимального паросочетания|алгоритм Куна]] работать не будет. Рассмотрим граф <tex>G</tex> с множеством вершин <tex>V={1,2,3,4} </tex>, и множеством ребер {{---}}<tex>E={\langle 1,2 \rangle, \langle 2, 3 \rangle, \langle 3, 1 \rangle, \langle 2, 4 \rangle}</tex> и пусть ребро <tex>\langle 2, 3\rangle</tex> взято в паросочетание. Тогда при запуске из вершины <tex>1</tex>, если обход пойдёт сначала в вершину <tex>2</tex>, то он зайдет в тупик в вершине <tex>3</tex>, вместо того чтобы найти увеличивающую цепь <tex>1-3-2-4</tex>. Как видно на этом примере, основная проблема заключается в том, что при попадании в цикл нечётной длины, обход может пойти по циклу в неправильном направлении.