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 Φ(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