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