sábado, 19 de dezembro de 2015

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.

Sem comentários:

Enviar um comentário