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