Detour

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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