262
правки
Изменения
м
→Удаление пропущенных вершин
Тогда, корректной верхней оценкой охвата <tex>(u,v)</tex> является <tex>\overline{r}(u,v)=\ell(u,v)+out\textrm{-}penalty(v)</tex>. Аналогично, <tex>\overline{r}(v,w)=\ell(v,w)+in\textrm{-}penalty(v)</tex>. Зная это, мы можем удалить вершину <tex>v</tex> и смежные ей рёбра из графа и обновить соответствующие значения пенальти для её соседей.
Такую же процедуру можно проделать с двусторонней линией, т.к. помимо оценок, указанных выше , можно добавить:
* <tex>\overline{r}(w,v)=\ell(w,v)+out\textrm{-}penalty(v)</tex>
* <tex>\overline{r}(v,u)=\ell(v,u)+in\textrm{-}penalty(v)</tex>
