Em geral

Na teoria dos grafos, um walk (em inglês, walk, e às vezes também traduzido como tour)[1]​ é uma sucessão de vértices "Vértice (teoria dos grafos)") e arestas "Edge (teoria dos grafos)") dentro de um gráfico, que começa e termina em vértices, de modo que cada vértice é incidente com as arestas que o seguem e o precedem na sequência.[2]​ Dois vértices são conectados ou acessíveis se houver um caminho que forma uma trajetória para ir de um até o outro. outro; Caso contrário, os vértices ficam desconectados ou inacessíveis.[1]​.

Dois vértices podem ser conectados por vários caminhos. O comprimento de um caminho é o seu número de arestas. Assim, em um gráfico não direcionado, os vértices adjacentes são conectados por um caminho de comprimento 1, os segundos vizinhos "Vizinhança (teoria dos grafos)") por um caminho de comprimento 2 e assim por diante. Um grafo não direcionado é conectado se todos os seus vértices estiverem conectados por meio de um caminho.[2]​ Um grafo conectado cujos vértices e arestas permitem que um caminho seja definido é um grafo de caminho.

Dado um gráfico, um caminho é uma sequência de vértices e arestas tais que (no caso do gráfico não ser direcionado), ou (no caso de ser direcionado), para todos. O comprimento do caminho é .[2][1]​.

Contenido

Existen varios conceptos derivados del de camino:[2]​.

Trajetórias em gráficos direcionados

As definições de caminhos acima também se aplicam a grafos direcionados, desde que os caminhos respeitem a direção das arestas entre cada vértice e o próximo. No entanto, se em um gráfico direcionado você deseja ignorar a direção das arestas e considerar suas trajetórias como se fosse um gráfico não direcionado, então os caminhos são conhecidos como semicaminhos, os caminhos como semicaminhos, os ciclos como semiciclos, etc.[1]​.

Trajetórias em gráficos ponderados

No contexto da análise de redes sociais, para redes sociais representadas como grafos ponderados, ou seja, com pesos nas arestas, o valor de um caminho ou meio caminho pode ser definido como o valor mínimo de todas as arestas que ele contém. no nível c entre eles.[5]​ O comprimento de um caminho em um grafo ponderado corresponde à soma dos valores das arestas incluídas nesse caminho.[6]​[1]​.