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 , os caminhos como , os ciclos como , etc.[1]​.