Camiño (teoría de grafos)

[dereita|miniatura| Un grafo de hipercubo tridimensional que mostra un [camiño hamiltoniano en vermello e un camiño inducido máis longo en negro groso.]]
Na teoría de grafos, un **camiño** nun grafo é unha secuencia finita ou infinita de arestas que une unha secuencia de vértices que, segundo a maioría das definicións, son todos distintos (e dado que os vértices son distintos, as arestas tamén o son). 

Un **camiño orientado** (ás veces chamado **dipath** en inglés) nun grafo orientado é unha secuencia finita ou infinita de arestas que une unha secuencia de vértices distintos, pero coa restrición engadida de que as arestas estean todas orientadas na mesma dirección.

## Definicións 
* Un **camiño** é unha secuencia finita ou infinita de arestas que une unha secuencia de vértices.

: Sexa  un grafo. Un camiño finito é unha secuencia de arestas  para a que hai unha secuencia de vértices  tal  que *Φ*(*e**i*) = {*v**i*, *v**i* + 1} para . 
: Así temos que  é a *secuencia de vértices* do camiño. 
: O camiño está *pechado* se *v*1 = *v**n*, e está *aberto* se non son iguais. 
: Un camiño infinito é unha secuencia de arestas do mesmo tipo descrito aquí, pero sen primeiro nin último vértice, e un paseo semiinfinito (ou raio) ten un primeiro vértice pero non o último.

*
* Un **camiño simple** é un camiño no que todos os vértices (e, polo tanto, tamén todas as arestas) son distintas.

Un grafo ponderado asocia un valor (*peso*) con cada aresta do grafo. O *peso dun camiño* nun grafo ponderado é a suma dos pesos das arestas percorridas. Ás veces úsanse as palabras *custo* ou *lonxitude* en lugar de peso.

Os mesmos conceptos aplican nun **grafo orientado**.

## Exemplos 
* Un grafo é conexo se hai camiños que conteñen cada par de vértices.
* Un grafo dirixido é fortemente conexo se hai camiños orientados de orientación oposta que conteñen cada par de vértices.
* Un camiño tal que ningunha aresta do grafo liga dous vértices de camiños non consecutivos chámase camiño inducido.
* Un camiño que inclúe todos os vértices do grafo sen repeticións coñécese como camiño hamiltoniano .
* 

## Atopando camiños 
Existen varios algoritmos para atopar os camiños máis curtos e longos nos grafos, coa importante distinción de que o primeiro problema é computacionalmente moito máis sinxelo que o segundo.

O algoritmo de Dijkstra produce unha lista de camiños máis curtos desde un vértice de orixe ata calquera outro vértice en grafos orientados e non orientados con pesos de arestas non negativos (ou sen pesos nas arestas), mentres que o algoritmo de Bellman-Ford pódese aplicar a grafs dirixidos con pesos de arestas negativos. 

O algoritmo de Floyd-Warshall pódese usar para atopar os camiños máis curtos entre todos os pares de vértices en grafos orientados ponderados.

## O problema da partición do camiño 
O problema **de partición de k-camiños**  é o problema de particionar un grafo dado nunha colección máis pequena de camiños con vértices disxuntos de lonxitude como máximo *k*.

## Notas 
## Véxase tamén 
### Bibliografía 
* 
* 
* 
* 
* 
* 

### Outros artigos 
* Glosario de teoría de grafos
* Grafo de camiño
* Cadea poligonal
* Algoritmo de Dijkstra
* Algoritmo de Bellman-Ford
* Algoritmo de Floyd-Warshall