1632
правки
Изменения
м
rollbackEdits.php mass rollback
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Для решения таких задач в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес.
[[Файл:Graph.jpg|550px530px|thumb|left|Граф]] [[Файл:Spanforest.jpg|550px530px|thumb|right|Остовный лес в графе]]
====Псевдокод====
'''function''' <tex>\mathrm{add}</tex> ('''Node''' u, '''Node''' v):
'''Edge''' e = <tex>\langle </tex>u, v<tex>\rangle</tex>
e.level = 0
====Псевдокод====
'''function''' <tex>\mathrm{remove}</tex> ('''Node''' u, '''Node''' v):
'''Edge''' e = <tex>\langle </tex>u, v<tex>\rangle</tex>
'''for''' i = e.level '''whiledownto''' i <tex>\geqslant</tex> 0
<tex>G_i</tex> = <tex>G_i\setminus</tex>e<!---delete(<tex>G_i</tex>, e)--->
<tex>F_i</tex> = <tex>F_i\setminus</tex>e<!---delete(<tex>F_i</tex>, e)--->
'''for''' e2 = <tex>\langle </tex>x, y<tex>\rangle</tex> : e2.level == i '''and''' x <tex>\in T_u</tex>
'''if''' y <tex>\in T_v</tex>
'''whilefor''' j = i <tex>\geqslant</tex> '''downto''' 0 <tex>F_iF_j</tex> = <tex>F_iF_j</tex> <tex>\cup</tex> e2<!---insert(<tex>F_i</tex>, e2)--> i--
'''return'''
'''else'''
e2.level++
<tex>G_{i+1}</tex> = <tex>G_{i+1}</tex> <tex>\cup</tex> e2<!---insert(<tex>F_i</tex>, e2)--> i--
== См. также ==
