Trayectoria (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 como 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 deben estar dirigidas en la misma dirección.
Las trayectorias son conceptos fundamentales de la teoría de grafos, que se describen en las secciones introductorias de la mayoría de los textos de teoría de grafos. Véase, por ejemplo, Bondy y Murty (1976), Gibbons (1985) o Diestel (2005). Korte et al. (1990) tratan temas algorítmicos más avanzados relacionados con las trayectorias en grafos.
Definiciones
Paseo, sendero y camino
- Sea G = ( V , E , ϕ ) un grafo. Un paseo finito es una secuencia de aristas ( e 1 , e 2 , …, e n − 1 ) para la que 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 paseo. El paseo es cerrado si v 1 = v n , y es abierto en caso contrario. Un paseo infinito es una secuencia de aristas del mismo tipo descrito aquí, pero sin primer ni último vértice, y un paseo semi-infinito (o rayo ) tiene un primer vértice pero no un último vértice.
- Un sendero es un paseo en el que todos los bordes son distintos. [2]
- Un camino es un sendero en el que todos los vértices (y por lo tanto también todos los bordes) son distintos. [2]
Si w = ( e 1 , e 2 , …, e n − 1 ) es un paseo finito con secuencia de vértices ( v 1 , v 2 , …, v n ) entonces se dice que w es un paseo desde v 1 hasta v n . Lo mismo ocurre con un sendero o un camino. Si hay un paseo finito entre dos vértices distintos , entonces también hay un sendero finito y un camino finito entre ellos.
Algunos autores no requieren que todos los vértices de una ruta sean distintos y en su lugar utilizan el término ruta simple para referirse a una ruta en la que todos los vértices son distintos.
Un gráfico ponderado asocia un valor ( peso ) a cada arista del gráfico. El peso de un paseo (o sendero o camino) en un gráfico ponderado es la suma de los pesos de las aristas recorridas. A veces se utilizan las palabras costo o longitud en lugar de peso.
Paseo dirigido, sendero dirigido y camino dirigido
- Un recorrido 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 paseo dirigido finito es una secuencia de aristas ( e 1 , e 2 , …, e n − 1 ) para la que existe una secuencia de vértices ( v 1 , v 2 , …, v n ) tales 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 paseo dirigido. El paseo dirigido es cerrado si v 1 = v n , y es abierto en caso contrario. Un paseo dirigido infinito es una secuencia de aristas del mismo tipo descrito aquí, pero sin primer ni último vértice, y un paseo dirigido semi-infinito (o rayo ) tiene un primer vértice pero no un último vértice.
- Un sendero dirigido es un paseo dirigido en el que todos los bordes son distintos. [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 paseo dirigido finito con secuencia de vértices ( v 1 , v 2 , …, v n ), entonces se dice que w es un paseo desde v 1 hasta v n . Lo mismo ocurre con un sendero dirigido o un camino. Si hay un paseo dirigido finito entre dos vértices distintos , entonces también hay un sendero dirigido finito y un camino dirigido finito entre ellos.
Una "ruta dirigida simple" es una ruta donde todos los vértices son distintos.
Un gráfico dirigido ponderado asocia un valor ( peso ) a cada arista del gráfico dirigido. El peso de un paseo (o sendero o camino) dirigido en un gráfico dirigido ponderado es la suma de los pesos de las aristas recorridas. A veces se utilizan las palabras costo o longitud en lugar de peso.
Ejemplos
- Un gráfico está conexo si hay caminos que contienen cada par de vértices.
- Un gráfico dirigido está fuertemente conectado si hay caminos dirigidos orientados de manera opuesta que contienen cada par de vértices.
- Una ruta tal que ningún borde del gráfico conecta dos vértices de ruta no consecutivos se denomina ruta inducida .
- Una ruta que incluye todos los vértices del gráfico sin repeticiones se conoce como ruta hamiltoniana .
- Dos caminos son independientes de los vértices (o, alternativamente, internamente disjuntos o internamente disjuntos en los vértices ) si no tienen ningún vértice o arista interna en común. De manera similar, dos caminos son independientes de las aristas (o disjuntos en las aristas ) si no tienen ninguna arista en común. Dos caminos internamente disjuntos son disjuntos en las aristas, pero lo inverso no es necesariamente cierto.
- La distancia entre dos vértices en un gráfico 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 gráfico conexo es la distancia más grande (definida anteriormente) entre pares de vértices del gráfico.
Encontrar caminos
Existen varios algoritmos para encontrar caminos más cortos y más largos en gráficos, con la importante distinción de que el primer problema es computacionalmente mucho más fácil que el segundo.
El algoritmo de Dijkstra produce una lista de caminos más cortos desde un vértice de origen hasta todos los demás vértices en grafos dirigidos y no dirigidos con pesos de aristas no negativos (o sin pesos de aristas), mientras que el algoritmo Bellman-Ford se puede aplicar a grafos dirigidos con pesos de aristas negativos. El algoritmo 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 la partición de rutas
El problema de partición de k-caminos es el problema de particionar un gráfico dado en una colección más pequeña de caminos disjuntos en vértices con una longitud de k como máximo . [3]
Véase también
- Glosario de teoría de grafos
- Gráfico de ruta
- Cadena poligonal
- Problema del camino más corto
- Problema del camino más largo
- Algoritmo de Dijkstra
- Algoritmo de Bellman-Ford
- Algoritmo de Floyd-Warshall
- Caminata auto-evitante
- Gráfico de ruta más corta
Notas
- ^ McCuaig 1992, pág. 205.
- ^ abcdef Bender y Williamson 2010, pág. 162.
- ^ Chen, Yong; Goebel, Randy; Lin, Guohui; Su, Bing; Xu, Yao; Zhang, An (1 de julio de 2019). "Un algoritmo de aproximación mejorado para el problema de partición mínima de 3 caminos". Revista de optimización combinatoria . 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. Holanda Septentrional. pág. 12-21. ISBN 0-444-19451-7.
- Diestel, Reinhard (2005). Teoría de grafos. Springer-Verlag. págs. 6–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). "Dígrafos intercíclicos" . En Robertson, Neil; Seymour, Paul (eds.). Teoría de la estructura de grafos . Conferencia de investigación de verano conjunta AMS–IMS–SIAM sobre grafos menores, Seattle, 22 de junio – 5 de julio de 1991. American Mathematical Society. pág. 205.
