Detour distance

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

Detour distance --- расстояние обхода.

Let G be a nontrivial connected graph. For distinct vertices u and v of G, the detour distance D(u,v) between u and v is the length of the longest u-v path in G. Thus 1 \leq D(u,v) \leq
n-1, where D(u,v) = 1 if and only if uv is a bridge of G and D(u,v) = n-1 if and only if G contains a hamiltonian u-v path.