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[1]) 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
[editar | editar a fonte]- Sexa G = (V, E, Φ) un grafo. Un camiño finito é unha secuencia de arestas (e1, e2, ..., en − 1) para a que hai unha secuencia de vértices (v1, v2, ..., vn) tal que Φ(ei) = {vi, vi + 1} para i = 1, 2, ..., n − 1.
- Así temos que (v1, v2, ..., vn) é 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.[2]
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
[editar | editar a fonte]- 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
[editar | editar a fonte]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
[editar | editar a fonte]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.[3]
Notas
[editar | editar a fonte]- ↑ McCuaig 1992, p. 205.
- ↑ 2,0 2,1 Bender & Williamson 2010, p. 162.
- ↑ Chen, Yong; Goebel, Randy; Lin, Guohui; Su, Bing; Xu, Yao; Zhang, An (2019-07-01). "An improved approximation algorithm for the minimum 3-path partition problem". Journal of Combinatorial Optimization 38 (1): 150–164. ISSN 1382-6905. doi:10.1007/s10878-018-00372-z.
Véxase tamén
[editar | editar a fonte] |
Wikimedia Commons ten máis contidos multimedia na categoría: Camiño |
Bibliografía
[editar | editar a fonte]- Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability.
- Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. North Holland. p. 12-21. ISBN 0-444-19451-7.
- Diestel, Reinhard (2005). Graph Theory. Springer-Verlag. pp. 6–9. ISBN 3-540-26182-6.
- Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press. pp. 5–6. ISBN 0-521-28881-9.
- Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (1990). Paths, Flows, and VLSI-Layout. Springer-Verlag. ISBN 0-387-52685-4.
- McCuaig, William (1992). "Intercyclic Digraphs". En Robertson, Neil; Seymour, Paul. Graph Structure Theory. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, Seattle, 22 de xuño a 5 de xullo de 1991. American Mathematical Society. p. 205.
