234
правки
Изменения
→Оценка времени работы
По лемме, количество легких dashed-ребер, преобразованных в solid, будет не больше, чем <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 - |\{H \cap solid-edges\}|</tex>, <tex>\Delta \Phi _{a}</tex> {{--- }} увеличение <tex>\Phi _{a}</tex> после одной операции <tex>expose</tex>.
{{Лемма
