Изменения

Перейти к: навигация, поиск

Задача о динамической связности

3 байта добавлено, 12:34, 8 января 2018
Обобщение задачи для произвольных графов
Введём функцию <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 ... \ldots \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>.
[[Файл:Another_edge.jpg|200px|thumb|right]]
693
правки

Навигация