Изменения

{{Лемма|id = Lemma1|statement= На пути от вершины до корня не больше <tex>log(n)</tex> легких ребер. Каждая вершина имеет не более одного тяжелого ребра}}

Операция <tex>u</tex> осуществляется с помощью последовательности преобразований dashed-ребра в solid-ребро и другого solid-ребра в dashed-ребро. Обозначим количество таких преобразований за <tex>M</tex>. Найдем количество таких преобразований сделанных в течение <tex>expose(u)</tex>. Пусть <tex>H</tex> - множество всех тяжелых ребер, <tex>L</tex> - все легкие ребра, <tex>S \rightarrow D</tex> - множество solid-ребер, преобразованных в dashed в течение одного <tex>expose</tex>, <tex>D \rightarrow S</tex> - множество dashed-ребер, преобразованных в solid.

<tex>M = |\{все ребра, преобразованные из dashed в solidD \rightarrow S\}| = |\{легкие dashed-ребра, преобразованные в solidL \cap D \rightarrow S\}| + |\{тяжелые dashed-ребра, преобразованные в solidH \cap D \rightarrow S\}|</tex>

По лемме, количество легких <tex>dashed</tex>-ребер, преобразованных в <tex>solid</tex>, будет не больше, чем <tex>\log n</tex>.

Обозначим за <tex>F</tex> лес деревьев, в которых каждое ребро либо solid, либо dashed, a <tex>F'</tex> - лес, получившийся из <tex>F</tex> после одного вызова <tex>expose</tex>. Определим потенциал <tex>\Phi _{a}(F) = n - 1 - |\{heavy solid-edges\}|</tex>. Пусть <tex>H</tex> - множество всех тяжелых ребер, <tex>L</tex> - все легкие ребра, <tex>S \rightarrow D</tex> - множество solid-ребер, преобразованных в dashed в течение одного <tex>expose</tex>, <tex>D \rightarrow S</tex> - множество dashed-ребер, преобразованных в solid, <tex>\Delta \Phi _{a}</tex> - увеличение <tex>\Phi _{a}</tex> после одной операции <tex>expose</tex>.