Camino (teoría de grafos)

En teoría de grafos , un camino en un grafo es una secuencia finita o infinita de aristas que une una secuencia de vértices que, según la mayoría de las definiciones, son todos distintos (y dado que los vértices son distintos, también lo son las aristas). Un camino dirigido (a veces llamado dipath ^{[ 1 ]} ) en un grafo dirigido es una secuencia finita o infinita de aristas que une una secuencia de vértices distintos, pero con la restricción adicional de que todas las aristas estén dirigidas en la misma dirección.

Los caminos son conceptos fundamentales de la teoría de grafos, descritos en las secciones introductorias de la mayoría de los textos sobre el tema. Véanse, por ejemplo, Bondy y Murty (1976) , Gibbons (1985) o Diestel (2005) . Korte et al. (1990) abordan temas algorítmicos más avanzados relacionados con caminos en grafos.

Definiciones

Caminata, sendero y camino

Un camino es una secuencia finita o infinita de aristas que une una secuencia de vértices . ^{[ 2 ]}

Sea

G = (V, E, Φ)

un grafo. Un camino finito es una secuencia de aristas

(e 1, e 2, ..., e n - 1)

para la cual existe una secuencia de vértices

(v 1, v 2, ..., v n)

tal que

Φ (e i) = {v i, v i + 1}

para

i = 1, 2, ..., n - 1

.

(v 1, v 2, ..., v n)

es la secuencia de vértices del camino. El camino es cerrado si

v 1 = v n

, y es abierto en caso contrario. Un camino infinito es una secuencia de aristas del mismo tipo descrito aquí, pero sin primer ni último vértice, y un camino semiinfinito (o rayo ) tiene un primer vértice pero no un último vértice.

Un sendero es un camino en el que todos los bordes están bien definidos. ^{[ 2 ]}
Un camino es un sendero en el que todos los vértices (y por lo tanto también todas las aristas) son distintos. ^{[ 2 ]}

Si $w = (e 1, e 2, ..., e n - 1)$ es un camino finito con secuencia de vértices $(v 1, v 2, ..., v n)$ , entonces se dice que $w$ es un camino desde $v 1$ hasta $v n$ . De manera similar, ocurre con un sendero o una senda. Si existe un camino finito entre dos vértices distintos , entonces también existe un sendero finito y una senda finita entre ellos.

Algunos autores no exigen que todos los vértices de un camino sean distintos y, en su lugar, utilizan el término " camino simple" para referirse a un camino en el que todos los vértices son distintos.

Un grafo ponderado asocia un valor ( peso ) a cada arista. El peso de un recorrido (o camino) en un grafo ponderado es la suma de los pesos de las aristas recorridas. A veces se utilizan términos como costo o longitud en lugar de peso.

Paseo guiado, sendero guiado y camino guiado

Un camino dirigido es una secuencia finita o infinita de aristas dirigidas en la misma dirección que une una secuencia de vértices . ^{[ 2 ]}

Sea

G = (V, E, Φ)

un grafo dirigido. Un camino dirigido finito es una secuencia de aristas

(e 1, e 2, ..., e n - 1)

para la cual existe una secuencia de vértices

(v 1, v 2, ..., v n)

tal que

Φ (e i) = (v i, v i + 1)

para

i = 1, 2, ..., n - 1

.

(v 1, v 2, ..., v n)

es la secuencia de vértices del camino dirigido. El camino dirigido es cerrado si

v 1 = v n

, y es abierto en caso contrario. Un camino dirigido infinito es una secuencia de aristas del mismo tipo descrito aquí, pero sin primer ni último vértice, y un camino dirigido semiinfinito (o rayo ) tiene un primer vértice pero no un último vértice.

Un sendero señalizado es un recorrido señalizado en el que todos los bordes están claramente definidos. ^{[ 2 ]}
Un camino dirigido es un sendero dirigido en el que todos los vértices son distintos. ^{[ 2 ]}

Si $w = (e 1, e 2, ..., e n - 1)$ es un camino dirigido finito con secuencia de vértices $(v 1, v 2, ..., v n)$ , entonces se dice que $w$ es un camino desde $v 1$ hasta $v n$ . De manera similar, para un sendero dirigido o una senda. Si hay un camino dirigido finito entre dos vértices distintos , entonces también hay un sendero dirigido finito y una senda dirigida finita entre ellos.

Un "camino dirigido simple" es un camino en el que todos los vértices son distintos.

Un grafo dirigido ponderado asocia un valor ( peso ) a cada arista. El peso de un recorrido dirigido (o camino) en un grafo dirigido ponderado es la suma de los pesos de las aristas recorridas. En ocasiones, se utilizan términos como costo o longitud en lugar de peso.

Ejemplos

Un grafo está conectado si existen caminos que contienen cada par de vértices.
Un grafo dirigido está fuertemente conectado si existen caminos dirigidos de orientación opuesta que contienen cada par de vértices.
Un camino tal que ninguna arista del grafo conecta dos vértices de camino no consecutivos se denomina camino inducido .
Un camino que incluye todos los vértices del grafo sin repeticiones se conoce como camino hamiltoniano .
Dos caminos son independientes en cuanto a vértices ( o disjuntos internamente ) si no comparten ningún vértice ni arista. Del mismo modo, dos caminos son independientes en cuanto a aristas (o disjuntos en cuanto a aristas ) si no comparten ninguna arista. Dos caminos disjuntos internamente son disjuntos en cuanto a aristas, pero lo contrario no es necesariamente cierto.
La distancia entre dos vértices en un grafo es la longitud del camino más corto entre ellos, si existe, y en caso contrario la distancia es infinita.
El diámetro de un grafo conexo es la mayor distancia (definida anteriormente) entre pares de vértices del grafo.

Encontrar caminos

Existen varios algoritmos para encontrar los caminos más cortos y más largos en grafos, con la importante distinción de que el primer problema es computacionalmente mucho más fácil que el segundo.

El algoritmo de Dijkstra genera una lista de los caminos más cortos desde un vértice de origen a todos los demás vértices en grafos dirigidos y no dirigidos con pesos de arista no negativos (o sin pesos de arista), mientras que el algoritmo de Bellman-Ford se puede aplicar a grafos dirigidos con pesos de arista negativos. El algoritmo de Floyd-Warshall se puede utilizar para encontrar los caminos más cortos entre todos los pares de vértices en grafos dirigidos ponderados.

El problema de partición de rutas

El problema de partición de k caminos es el problema de particionar un grafo dado en una colección más pequeña de caminos disjuntos en vértices de longitud como máximo k . ^{[ 3 ]}

Véase también

Notas

↑ McCuaig 1992 , pág. 205.
1 2 3 4 5 6 Bender & Williamson 2010 , pág. 162.
↑ Chen, Yong; Goebel, Randy; Lin, Guohui; Su, Bing; Xu, Yao; Zhang, An (2019-07-01). "Un algoritmo de aproximación mejorado para el problema de partición de 3 caminos mínimos" . Journal of Combinatorial Optimization . 38 (1): 150– 164. doi : 10.1007/s10878-018-00372-z . ISSN 1382-6905 .

Referencias

Bender, Edward A.; Williamson, S. Gill (2010). Listas, decisiones y gráficos. Con una introducción a la probabilidad .
Bondy, JA; Murty, USR (1976). Teoría de grafos con aplicaciones . North Holland. págs. 12-21 . ISBN 0-444-19451-7.
Diestel, Reinhard (2005). Teoría de grafos . Springer-Verlag. págs. 6 a 9. ISBN 3-540-26182-6.
Gibbons, A. (1985). Teoría algorítmica de grafos . Cambridge University Press. pp. 5–6 . ISBN 0-521-28881-9.
Korte, Bernhard ; Lovász, László ; Prömel, Hans Jürgen; Schrijver, Alejandro (1990). Rutas, flujos y diseño VLSI . Springer-Verlag. ISBN 0-387-52685-4.
McCuaig, William (1992). "Digrafos intercíclicos" . En Robertson, Neil ; Seymour, Paul (eds.). Teoría de la estructura de grafos . Conferencia conjunta de investigación de verano AMS-IMS-SIAM sobre menores de grafos, Seattle, 22 de junio - 5 de julio de 1991. Sociedad Matemática Americana. pág. 205.

[FOOTNOTEMcCuaig1992205-1] McCuaig 1992 , pág. 205.

[FOOTNOTEBenderWilliamson2010162-2] 1 2 3 4 5 6 Bender & Williamson 2010 , pág. 162.

[3] Chen, Yong; Goebel, Randy; Lin, Guohui; Su, Bing; Xu, Yao; Zhang, An (2019-07-01). "Un algoritmo de aproximación mejorado para el problema de partición de 3 caminos mínimos" . Journal of Combinatorial Optimization . 38 (1): 150– 164. doi : 10.1007/s10878-018-00372-z . ISSN 1382-6905 .

[ 1 ]

[ 2 ]

[ 3 ]