Изменения

<tex> R(P(v))>R(v) </tex>

|proof=

1.<tex> R(L(v))>R(v) </tex>

Обозначим эти классы <tex> T1,T2,T3 </tex>

Амортизированная стоимость<tex> S= {\sum_{get} \limits} ({\sum_{v \in get,v \in T1} \limits 1} + {\sum_{v \in get,v \in T2} \limits 1} + {\sum_{v \in get,v \in T3} \limits 1} ) / m </tex> , где <tex> {v \in get } </tex> означает что ребро начало которого находится в <tex> v </tex> было пройдено во время выполнения текущего <tex> get </tex>.

Ребро <tex> v </tex> эквивалентно вершине в которой оно начинается.

При <tex> x < 2~~~{\sum_{get} \limits}~ {\sum_{v \in get,v \in T3} \limits} 1/n < { 2 \over 2-x } = = O(1) </tex>.

В результате <tex> S=O(1)+O(1)+O(1)=O(1) </tex>.

}}