100
правок
Изменения
Нет описания правки
|proof=
[[Файл:Kuhn.png|thumb|left|300x300px|Пунктиром обозначено существование пути между двумя вершинами.]]
Доказательство от противного. Допустим в паросочетание внесли изменения вдоль дополняющей цепи <tex>(y \rightsquigarrow z)</tex> и относительно вершины <tex>x</tex> появилась дополняющая цепь. Заметим, что эта дополняющая цепь должна вершинно пересекаться с той цепью, вдоль которой вносились изменения, иначе такая же дополняющая цепь существовала и в исходном паросочетании.
}}
==Алгоритм==
