47
правок
Изменения
→Время работы алгоритма
{{Лемма
|statement=
Пусть <tex>1 \le k \le 2m</tex>. Тогда множеству <tex>M</tex> с функцией приспособленности <tex>k</tex> соответствует не менее <tex>k/2</tex> путей.
|proof=
В множестве <tex>M</tex> каждая вершина, не имеющая пары, является крайней в некотором пути. Таким образом, каждому отдельному пути в <tex>M</tex> соответсвует пара вершин, поэтому
