262
правки
Изменения
м
→Калибровка (caliber)
Рассмотрим механизм релаксации: пусть мы уменьшаем <tex>d(u)</tex>. Заметим, что в этом случае <tex>u</tex> не могло лежать в <tex>F</tex> (иначе <tex>d(u)</tex> было не точно). Если <tex>u \in B</tex> - применим <tex>\mathtt{decrease - key}</tex> к <tex>u</tex>. Эта операция либо переместила <tex>u</tex> внутри <tex>B</tex>, либо определила, что метка <tex>d(u)</tex> точна и переместила <tex>u</tex> в <tex>F</tex>.
Если же <tex>u \notin F \hspace{2 mm} \& \hspace{2 mm} </tex> и <tex>u \notin B</tex>, мы применим операцию <tex>\mathtt{insert}</tex>, и <tex>u</tex> запишется в
<tex>F</tex> или <tex>B</tex>, в зависимости от того, выполняется ли условие леммы.
