Изменения

Введём функцию <tex>l(e):eE{\rightarrow}[0;\log n]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Уровни ребра можно распределить любым способом, но для всех <tex> i </tex> должно выполняться следующее свойство: размер каждой компоненты связности <tex>G_i</tex> не превосходит <tex>\dfrac{n}{2^i}</tex>. Здесь графы <tex>G_i</tex> определяются так: <tex>G_i=\langle V, E\rangle: \{E \mid l(E) \geqslant i\}</tex>. Очевидно, что <tex>G_{\log n} \subseteq G_{\log n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0</tex>. Выделим в них остовные леса таким образом, что <tex>F_{\log n} \subseteq F_{\log n-1} \subseteq \ldots \subseteq F_1 \subseteq F_0</tex>, где <tex>F_i</tex> {{---}} остовный лес графа <tex>G_i</tex>.