693
правки
Изменения
→Обобщение задачи для произвольных графов
== Обобщение задачи для произвольных графов ==
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Но мы можем в каждой компоненте связности выделить [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес. Граф и его остовный лес {{---}} одно и то же с точки зрения связности.
[[Файл:Graph.jpg|550px|thumb|left|Произвольный граф]] [[Файл:Spanforest.jpg|550px|thumb|right|Остовный лес в графе]]
Введём функцию <tex>l(e):e{\rightarrow}[0;\mathrm{\log} n]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Будем рассматривать графы <tex>G_i=\langle V, E\rangle: {E|l(E) \geqslant i}</tex>. Очевидно, что <tex>G_{\mathrm{\log}n} \subseteq G_{\mathrm{\log}n-1} \subseteq ... \subseteq G_1 \subseteq G_0</tex>. Выделим в них остовные леса таким образом, чтобы <tex>F_{\mathrm{\log}n} \subseteq F_{\mathrm{\log}n-1} \subseteq ... \subseteq F_1 \subseteq F_0</tex>, где <tex>F_i</tex> {{---}} остовный лес графа <tex>G_i</tex>.
Когда мы добавляем ребро, то мы можем сделать его ребром уровня <tex>0</tex>. Тогда изменится только <tex>G_0</tex> и, возможно, <tex>F_0</tex> (это произойдёт в том случае, если компоненты связности слились в одну, иначе же связность между каждой парой не изменилась, и остовный лес также не изменился.
При удалении
<!--При выполнении операции add что-то хорошее, а с удалением не всё так просто.-->
<!-- === Псевдокод === xz -->
