Detour

Материал из WikiGrapp
Версия от 16:03, 24 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''Detour''' --- обходной путь. Let <math>P_{G}(v_{0},v_{1}, \ldots, v_{p})</math> be the shortest path from <math>v_{0}</math> to <math>v_{p}</math> i…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Detour --- обходной путь.

Let [math]\displaystyle{ P_{G}(v_{0},v_{1}, \ldots, v_{p}) }[/math] be the shortest path from [math]\displaystyle{ v_{0} }[/math] to [math]\displaystyle{ v_{p} }[/math] in a biconnected graph [math]\displaystyle{ G }[/math]. A detour from [math]\displaystyle{ v_{i} }[/math] to [math]\displaystyle{ v_{p} }[/math], denoted by [math]\displaystyle{ P_{G-e}(v_{i},v_{p}) }[/math], is the shortest path from [math]\displaystyle{ v_{i} }[/math] to [math]\displaystyle{ v_{p} }[/math] that does not contain the edge [math]\displaystyle{ e = (v_{i},v_{i+1}) }[/math].