262
правки
Изменения
м
→Reach
Пусть вершина <tex>v</tex> лежит на кратчайшем пути <tex>P: s \rightsquigarrow t</tex>. Тогда, назовём <b>охватом (reach)</b> вершины <tex>v</tex> относительно <tex>P</tex> величину <tex>r(v,P) = \min\{dist(s,v), dist(v,t)\}</tex>. Охватом вершины относительно всего графа назовём величину <tex>r(v) = \max\limits_{P} r(v,P)</tex> - максимум по всем кратчайшим путям, содержащим <tex>v</tex>.
Помимо этого, будет полезным ввести понятие охвата ребра. Назовём охватом ребра <tex>(v,w)\in P</tex> относительно <tex>P</tex> величину <tex>\min\{dist(s,v), dist(w,t)\}</tex>. Аналогично, охватом ребра относительно всего графа назовём величину <tex>r(v,w) = \max\limits_{P} r((v,w),P)</tex> - максимум по всем кратчайшим путям, содержащим <tex>(v,w)</tex>.
[[Файл:reach1.jpg|right]]
Заметим, что вершины с большим охватом находятся вблизи середины некоторого длинного кратчайшего пути, то есть
