100
правок
Изменения
Нет описания правки
|statement=
Если из вершины <tex>x</tex> не существует дополняющей цепи относительно паросочетания <tex>M</tex>, то если паросочетание <tex>M'</tex> получается из <tex>M</tex> изменением вдоль дополняющей цепи, то из <tex>x</tex> не существует дополняющей цепи в <tex>M'</tex>.
|proof=Доказательство от противного! Рассмотрим изменения, которые мы внесли в <tex>M</tex> вдоль дополняющей цепи, чтобы получить паросочетание <tex>M'</tex>[[Файл:Kuhn. В этой цепи все промежуточные вершины были насыщенными, а концы свободные. После изменения вдоль этой цепи все вершины, лежащие на этой цепи станут насыщенными. Допустим, что из <tex>x</tex> появилась дополняющая цепь относительно <tex>M'</tex>. Тогда появившаяся дополняющая цепь должна проходить хотя бы через одну из концевых вершин в той дополняющей цепи, относительно которой вносили изменения, поскольку иначе такая же дополняющая цепь была и в паросочетании <tex>M</tex>. Однако поскольку в паросочетании <tex>M</tex> концевые вершины цепи, вдоль которой вносили изменения, не насыщены, то из вершины <tex>x</tex> в паросочетании <tex>M</tex> есть все равно есть дополняющая цепь. Надо рассмотреть часть дополняющей цепи в <tex>M'</tex>, ограниченную концом текущей дополняющей цепи и концом той дополняющей цепи, вдоль которой вносили изменения, такую что вершина <tex>x</tex> будет промежуточной. Легко заметить, что в такой цепи все промежуточные вершины насыщенные, а концы свободны, поэтому она является дополняющей. Значит, мы пришли к противоречию, поскольку в паросочетании <tex>M</tex> нет дополняющих цепей из вершины <tex>x</tex>png|thumb|left|300x300px|Пунктиром обозначено существование пути между двумя вершинами.]]
}}
==Алгоритм==
