47
правок
Изменения
→Время работы алгоритма
Пусть <tex>1 \le k \le 2m</tex>. Тогда множество <tex>M</tex> с функцией приспособленности <tex>k</tex> содержит не менее <tex>k/2</tex> элементов.
|proof=
Во множестве <tex> T_i =\sum\limits_{k = F(i)}^{i} a_k , i = \overline{0, n} \Rightarrow</tex> необходимо менять те <tex>iM</tex>каждая вершина, не имеющая пары, является крайней в некотором пути. Таким образом, для которых <tex>a_{k}</tex> попадает каждому отдельному пути в <tex>T_i \RightarrowM</tex> необходимые <tex> i </tex> удовлетворяют условию <tex>F(i) < k <= i</tex>.соответсвует пара вершин, поэтому
}}
