Изменения
→Оценка времени работы
M = |{все ребра, преобразованные из dashed в solid}| = |{легкие dashed-ребра, преобразованные в solid}| + |{тяжелые dashed-ребра, преобразованные в solid}|
По лемме, количество легких <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->D</tex> - множество solid-ребер, преобразованных в dashed в течение одного <tex>expose</tex>, <tex>D->S</tex> - множество dashed-ребер, преобразованных в solid, <tex>\Delta \Phi _{a}</tex> - увеличение <tex>\Phi _{a}</tex> после одной операции <tex>expose</tex>.
