stringtranslate.com

Trayectoria (teoría de grafos)

Un gráfico de hipercubo tridimensional que muestra una trayectoria hamiltoniana en rojo y una trayectoria inducida más larga en negrita negra.

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.

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

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.

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

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

Notas

  1. ^ McCuaig 1992, pág. 205.
  2. ^ abcdef Bender y Williamson 2010, pág. 162.
  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 caminos". Revista de optimización combinatoria . 38 (1): 150–164. doi :10.1007/s10878-018-00372-z. ISSN  1382-6905.

Referencias