Caminho (teoria dos grafos)

Um grafo hipercubo mostrando um caminho hamiltoniano em vermelho e o caminho induzido mais longo em negrito.

Em teoria dos grafos, um caminho em um grafo é uma sequência finita ou infinita de vértices conectados por uma sequência de arestas que, na maioria das definições, são todos diferentes uns dos outros. O primeiro vértice é chamado de vértice inicial e o último é chamado de vértice final. Em um grafo direcionado, um caminho dirigido (às vezes chamado de dipath) é uma sequência de arestas que se conectam a uma sequência de vértices, mas com a restrição de que as arestas sejam todas dirigidas no mesmo sentido.

Os caminhos são conceitos fundamentais de teoria de grafos, descrito nas seções introdutórias da maioria dos textos sobre teoria dos grafos.

Definição formal

Um passeio de distância $k$ em um grafo é uma sequência alternante de vértices e arestas $v_{0},e_{1},v_{1},e_{2},v_{2},\ldots ,e_{k},v_{k}$, que começa e termina em vértices. Um caminho é um passeio na qual todos os vértices (exceto possivelmente o primeiro e o último) são distintos, enquanto uma trilha é um passeio no qual todas as arestas (ou edges, em inglês) são distintas.

Certos autores requerem que as arestas e vértices sejam distintos. Alguns, porém, não procedem dessa forma, preferindo usar o termo caminho simples ao invés para se referir a um caminho que não repete vértices. Um caminho simples em um grafo $G$ é uma sequência de vértices de $G$, por exemplo, $({v_{i_{1}},v_{j_{1}}},...,{v_{i_{r}},v_{j_{r}}})$, tal que $v_{j_{a}}=v_{i_{a+1}}$ para todo $1\leq a\leq r-1$.

Se o grafo é não dirigido, então os nós de $e_{i}$ são $v_{i}$ e $v_{i+1}$. Se o grafo é dirigido, então $e_{i}$ é um arco de $v_{i}$ a $v_{i+1}$.

Tipos de caminhos

• Um caminho infinito é uma sequência alternante do mesmo tipo descrito acima, mas sem um primeiro ou último vértice, enquanto um caminho semi-infinito tem um primeiro vértice $v_{0}$ mas nenhum último vértice.
• Um grafo ponderado, também chamado de valorado, associa um valor (peso) a cada aresta no grafo. O peso de um caminho em um grafo ponderado é a soma dos pesos das arestas percorridas.
• Um ciclo de comprimento r é um caminho constituído por r + 1 vértices, onde o primeiro vértice é igual ao último. Note que a escolha do vértice inicial em um ciclo é arbitrária.
• Um caminho sem vértices repetidos é chamado de caminho simples e um ciclo sem vértices repetidos com exceção do inicial/final é um ciclo simples. Por vezes o termo "simples" é omitido de "caminho simples" e "ciclo simples", embora essa não seja a regra.
• Um grafo é conexo se há caminhos contendo cada par de vértices, ou seja, se para quaisquer dois vértices, existe um caminho que começa em um e termina no outro.
• Um gráfico direcionado é fortemente conectado se há caminhos direcionados opostos contendo cada par de vértices.
• Um caminho que não há arestas do grafo conectando dois vértices não consecutivos é chamado de caminho induzido.
• Um caminho que passa uma única vez em todos os vértices do grafo é conhecido como um caminho hamiltoniano.
• Um ciclo simples que envolva todos os vértices de um grafo é chamado de ciclo hamiltoniano.
• Dois caminhos são independentes nos vértices se eles não têm qualquer vértice em comum. Da mesma forma, dois caminhos são independente nas arestas se eles não têm qualquer aresta em comum. Dois caminhos independentes nos vértices são independentes nas arestas, mas o inverso não é necessariamente verdadeiro.
• A distância entre dois vértices em um grafo é o comprimento do caminho mais curto entre eles, se houver, caso contrário, a distância é infinita.
• O diâmetro do grafo é a maior distância (definida acima) entre os pares de vértices do grafo.

Encontrando caminhos

Vários algoritmos existem para encontrar os caminhos mais curto e mais longo em grafos, com a diferença de que o primeiro problema é computacionalmente mais fácil do que o último.

O algoritmo de Dijkstra produz uma lista de caminhos mais curtos de um vértice "fonte" a todos os outros vértices em grafos direcionados e não-direcionados com pesos não-negativos nas arestas (ou nenhum peso), enquanto o algoritmo de Bellman–Ford pode ser aplicado para grafos dirigidos com pesos negativos nas arestas. O algoritmo de Floyd–Warshall pode ser usado para encontrar o menor caminho entre todos os pares de vértices em grafos ponderados dirigidos.

Veja também

• Lista de termos técnicos relacionados à teoria dos grafos
• Poligonal
• Problema do caminho mínimo
• Problema do caminho mais longo
• Algoritmo de Dijkstra
• Algoritmo de Bellman-Ford
• Algoritmo de Floyd-Warshall
• Caminho autoevitante

Bibliografia

• Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. [S.l.]: North Holland. pp. 12–21. ISBN 0-444-19451-7  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Diestel, Reinhard (2005). Graph Theory 3rd ed. [S.l.]: Graduate Texts in Mathematics, vol. 173, Springer-Verlag. pp. 6–9. ISBN 3-540-26182-6 
• Gibbons, A. (1985). Algorithmic Graph Theory. [S.l.]: Cambridge University Press. pp. 5–6. ISBN 0-521-28881-9 
• Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (Eds.) (1990). Paths, Flows, and VLSI-Layout. [S.l.]: Algorithms and Combinatorics 9, Springer-Verlag. ISBN 0-387-52685-4  !CS1 manut: Nomes múltiplos: lista de autores (link)