Изменения

2. Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида : <tex> v -> L(v) -> L(L(v)) -> ... ->P(v) </tex>

2.<tex> R(P(v))>=x^{R(v)}</tex>

Амортизированная стоимость<tex> S= {\sum_{get} \limits} ({\sum_{u \in get,u \in T1} \limits 1} + {\sum_{u \in get,u \in T2} \limits 1} + {\sum_{u \in get,u \in T3} \limits 1} ) / m </tex> , где <tex> {u \in get } </tex> означает что ребро <tex> u </tex> было пройдено во время выполнения текущего <tex> get </tex> . В силу того что <tex>{\sum_{u \in get,u \in T1} \limits 1} = O(1) </tex> получаем <tex> S = O(1) + {\sum_{get} \limits}( {\sum_{u \in get,u \in T2} \limits}1)/m+ {\sum_{get} \limits}( {\sum_{u \in get,u \in T3} \limits}1)/m </tex> , где . После K ребер из второго класса <tex> R(v1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>  Из выше сказанного и первого следствия второй леммы получаем что <tex> {\sum_{u \in get ,u \in T2} \limits} = log^*_x(log_2(n)) = O(log^*(n)) </tex> . Для того чтоб <tex> log^*_x </tex> означает что ребро существовал необходимо чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex> Рассмотрим сумму <tex> {\sum_{get} \limits} ( {\sum_{u \in get,u \in T3} \limits} 1)/m < {\sum_{get} \limits} ( {\sum_{u \in get,u \in T3} \limits} 1)/n </tex> было пройдено во время выполнения текущего Из первого утверждения следует <tex> get R(P(x)) </tex> только увеличивается при переходе по ребру из Т3.Как максимум через <tex> x^R(k) </tex>переходов ребро перестанет появлятся в классе Т3.