En teoría de grafos , un camino en un gráfico 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). Una ruta dirigida (a veces llamada dipath [1] ) en un gráfico 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.
Las rutas son conceptos fundamentales de la teoría de grafos y 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) cubren temas algorítmicos más avanzados relacionados con rutas en gráficos.
Sea G = ( V , E , ϕ ) una gráfica. Un paseo 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 yo , v yo + 1 } para i = 1, 2,…, n − 1 . ( v 1 , v 2 ,…, v n ) es la secuencia de vértices de la caminata. El paseo está cerrado si v 1 = v n y está abierto en caso contrario. Un recorrido infinito es una secuencia de aristas del mismo tipo descrito aquí, pero sin primer ni último vértice, y un recorrido semiinfinito (o rayo ) tiene un primer vértice pero ningún último vértice.
Un sendero es un paseo en el que todos sus bordes son distintos. [2]
Un camino es un sendero en el que todos los vértices (y por tanto también todas las aristas) son distintos. [2]
Si w = ( e 1 , e 2 ,…, e n − 1 ) es un recorrido finito con secuencia de vértices ( v 1 , v 2 ,…, v n ) , entonces se dice que w es un recorrido desde v 1 hasta v n . Lo mismo ocurre con un sendero o un camino. Si hay un camino finito entre dos vértices distintos , entonces también hay un camino finito y un camino finito 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 donde todos los vértices son distintos.
Un gráfico ponderado asocia un valor ( peso ) con cada borde del gráfico. El peso de una caminata (o sendero o camino) en un gráfico ponderado es la suma de los pesos de los bordes atravesados. A veces se utilizan las palabras costo o longitud en lugar de peso.
Caminata dirigida, sendero dirigido y camino dirigido
Un paseo 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 , ϕ ) una gráfica dirigida. Un paseo 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 yo , v yo + 1 ) para yo = 1, 2,…, norte − 1 . ( v 1 , v 2 ,…, v n ) es la secuencia de vértices de la caminata dirigida. El recorrido dirigido está cerrado si v 1 = v n y está abierto en caso contrario. Un recorrido dirigido infinito es una secuencia de aristas del mismo tipo descrito aquí, pero sin primer ni último vértice, y un recorrido dirigido semiinfinito (o rayo ) tiene un primer vértice pero ningún último vértice.
Un sendero dirigido es un paseo dirigido en el que todos los bordes son distintos. [2]
Un camino dirigido es un camino dirigido en el que todos los vértices son distintos. [2]
Si w = ( e 1 , e 2 ,…, e n − 1 ) es un recorrido dirigido finito con secuencia de vértices ( v 1 , v 2 ,…, v n ) , entonces se dice que w es un recorrido desde v 1 hasta v n . Lo mismo ocurre con un sendero dirigido o un camino. Si hay un camino finito dirigido entre dos vértices distintos , entonces también hay un camino finito dirigido y un camino finito dirigido entre ellos.
Un "camino dirigido simple" es un camino donde todos los vértices son distintos.
Un gráfico dirigido ponderado asocia un valor ( peso ) con cada borde del gráfico dirigido. El peso de una caminata dirigida (o sendero o camino) en un gráfico dirigido ponderado es la suma de los pesos de los bordes atravesados. A veces se utilizan las palabras costo o longitud en lugar de peso.
Ejemplos
Un gráfico es conexo si hay caminos que contienen cada par de vértices.
Un grafo dirigido está fuertemente conexo si hay caminos dirigidos con orientación opuesta que contienen cada par de vértices.
Un camino tal que ningún borde del gráfico conecte dos vértices de camino no consecutivos se llama camino inducido .
Un camino que incluye todos los vértices del gráfico sin repeticiones se conoce como camino hamiltoniano .
Dos caminos son independientes de los vértices (alternativamente, internamente disjuntos de vértices ) si no tienen ningún vértice interno en común. De manera similar, dos caminos son independientes de los bordes (o de bordes disjuntos ) si no tienen ningún borde interno en común. Dos caminos internamente separados por vértices son separados por bordes, pero lo contrario 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 conectado es la distancia más grande (definida anteriormente) entre pares de vértices del gráfico.
Encontrar caminos
Existen varios algoritmos para encontrar los 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 cualquier otro vértice en gráficos dirigidos y no dirigidos con pesos de borde no negativos (o sin pesos de borde), mientras que el algoritmo Bellman-Ford se puede aplicar a gráficos dirigidos con pesos de borde negativos. . El algoritmo Floyd-Warshall se puede utilizar para encontrar los caminos más cortos entre todos los pares de vértices en gráficos dirigidos ponderados.
El problema de la partición de ruta
El problema de partición de k-path es el problema de dividir un gráfico dado en una colección más pequeña de caminos disjuntos de vértices de longitud como máximo k . [3]
^ 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 rutas". 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 del Norte. pag. 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 . Prensa de la Universidad de Cambridge. págs. 5–6. ISBN 0-521-28881-9.
McCuaig, William (1992). «Dígrafos intercíclicos» . En Robertson, Neil; Seymour, Paul (eds.). Teoría de la estructura de grafos . Conferencia conjunta de investigación de verano de AMS-IMS-SIAM sobre Graph Minors, Seattle, 22 de junio - 5 de julio de 1991. Sociedad Matemática Estadounidense. pag. 205.
