Ruta (teoría de grafos)
En teoría de grafos , un camino en un gráfico es una secuencia finita o infinita de aristas que se une a 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 gráfico dirigido es una secuencia finita o infinita de aristas que une una secuencia de vértices distintos, pero con la restricción añadida 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 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 grafos.
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 de v 1 a v n . Del mismo modo para un sendero o un camino. Si hay una caminata finita 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 un camino sean distintos y, en su lugar, usan el término camino simple para referirse a dicho camino.
Un gráfico ponderado asocia un valor ( peso ) con cada borde del gráfico. El peso de una caminata (o sendero o ruta) en un gráfico ponderado es la suma de los pesos de los bordes recorridos. A veces se usan las palabras costo o longitud en lugar de peso.
Si w = ( e 1 , e 2 , …, e n − 1 ) es una caminata dirigida finita con secuencia de vértices ( v 1 , v 2 , …, v n ) entonces se dice que w es una caminata de v 1 a v norte _ Del mismo modo para un sendero dirigido o un camino. Si hay una caminata dirigida finita entre dos vértices distintos , entonces también hay un camino dirigido finito y un camino dirigido finito entre ellos.
