Passeios, trilhos e caminhos

Um passeio (walk) num grafo é uma sucessão de lados adjacentes (com um vértice comum), sem qualquer outra restrição. É o que fazemos quando passeamos numa cidade, em que podemos repetir ruas, esquinas, etc.
Um trilho (trail) é um passeio em nenhum lado é percorrido mais que uma vez. Num passeio citadino, seria aquele que não passa duas vezes pela mesma rua.
Um caminho (path) é um passeio que não passa duas vezes pelo mesmo nó. Acharíamos estranho se alguém nos indicasse um caminho para um determinado ponto numa cidade que passasse duas vezes pela mesma esquina.
O caminho mais curto entre dois pontos é um caminho geodésico, e o seu comprimento é a distância entre os dois pontos.
Um circuito é um caminho fechado, que se inicia e termina no mesmo nó ou vértice.

Nesta rede, por exemplo, temos
 - um passeio: 1 - 2 - 3 - 4 - 2 - 1
 - um trilho: 1 - 2 - 3 - 4 - 6 - 2
 - um caminho: 1 - 2 - 3 - 4 - 5
 - um caminho geodésico: 1 - 6 - 5
 - um circuito: 1 - 2 - 4 - 6 - 1.

Distância, excentricidade e diâmetro

A distância entre dois nós é medida pelo número mínimo de lados que é necessário percorrer para chegar de um nó ao outro (distância geodésica). Numa rede direccionada, cada lado só pode ser percorrido no sentido permitido.
A excentricidade de um nó é a distância (geodésica) entre esse nó e o nó mais afastado onde se pode chegar partindo do nó em causa.
Por exemplo, nesta rede

o nó 1 tem excentricidade 3, pois tem o nó 5 à distância 3 (dois caminhos: 1 - 2 - 4 - 5 e 1 - 3 - 4 - 5), os nós 2 e 3 têm excentricidade 2, o nó 4 tem excentricidade 1 (do nó 4 só se pode chegar ao nó 5) e o nó 5 tem excentricidade 0 (de 5 não se chega a nenhum outro nó).
A maior distância é o diâmetro da rede, neste caso, 3.
Podemos ver o relatório produzido pelo software SocNetV

De notar a simplicidade com que podemos calcular estes valores com o recurso a software apropriado.