Camiño (teoría de grafos)

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 Φ(ei) = {vi, vi + 1} para . 
 Así temos que  é a secuencia de vértices do camiño. 
 O camiño está pechado se v1 = vn, 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

Categoría:Teoría de grafos