Camino (teoría de grafos)

En teoría de grafos, un camino (walk), ruta (path) o recorrido 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) 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.

Definiciones

Caminar, sendero y sendero

• Un paseo es una secuencia finita o infinita de aristas que une una secuencia de vértices.

Sea G = (V, E, ϕ) una gráfica. Un recorrido finito es una secuencia de aristas (e ₁, e ₂, …, e _{n − 1}) para las cuales existe una secuencia de vértices (v ₁, v ₂, …, v _n) tal que ϕ (e _i) = { v _yo, v _{yo + 1} } para yo = 1, 2,..., norte - 1. (v ₁, v ₂, …, v _n) es la secuencia de vértices de la caminata. El camino está cerrado si v ₁ = 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 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.
• Un camino es un sendero en el que todos los vértices (y por tanto también todas las aristas) son distintos.

Si w = (e ₁, e ₂, …, e _{n − 1}) es un recorrido finito con secuencia de vértices (v ₁, v ₂, …, v _n) entonces se dice que w es un recorrido de v ₁ 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 exigen que todos los vértices de un camino sean distintos y, en cambio, utilizan el término camino simple para referirse a un camino en el que 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 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.

Caminata dirigida, sendero dirigido y camino dirigido

• Un camino dirigido es una secuencia finita o infinita de aristas dirigidas en la misma dirección que une una secuencia de vértices.

Sea G = (V, E, ϕ) un grafo dirigido. Un recorrido dirigido finito es una secuencia de aristas (e ₁, e ₂, …, e _{n − 1}) para las cuales existe una secuencia de vértices (v ₁, v ₂, …, v _n) tal que ϕ (e _i) = (v _yo, v _{yo + 1}) para yo = 1, 2, …, norte− 1. (v ₁, v ₂, …, v _n) es la secuencia de vértices de la caminata dirigida. El camino dirigido es cerrado si v ₁ = v _n, y está abierto en caso contrario. Una caminata dirigida infinita es una secuencia de aristas del mismo tipo que se describe aquí, pero sin primer ni último vértice, y una caminata dirigida (o rayo) semi-infinita tiene un primer vértice pero no un último vértice.

• Un sendero dirigido es una caminata dirigida en la que todos los bordes son distintos.
• Un camino dirigido es un sendero dirigido en el que todos los vértices son distintos.

Si w = (e ₁, e ₂, …, e _{n − 1}) es una caminata dirigida finita con secuencia de vértices (v ₁, v ₂, …, v _n) entonces se dice que w es una caminata de v ₁ 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.

Algunos autores no requieren que todos los vértices de un camino dirigido sean distintos y, en su lugar, usan el término camino dirigido simple para referirse a dicho camino dirigido.

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 ruta) en un gráfico dirigido ponderado es la suma de los pesos de los bordes atravesados. A veces se usan las palabras costo o longitud en lugar de peso.

Ejemplos

• Un grafo es 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 en la 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 (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 disjuntos de los bordes) si no tienen ningún borde interno en común. Dos caminos disjuntos de vértice internamente son disjuntos de borde, 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 de lo contrario la distancia es infinita.
• El diámetro de un gráfico conexo es la distancia más grande (definida arriba) entre pares de vértices del gráfico.

Encontrar caminos

Existen varios algoritmos para encontrar las rutas más cortas y más largas en los 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 las rutas más cortas desde un vértice de origen a 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 de Floyd-Warshall se puede utilizar para encontrar los caminos más cortos entre todos los pares de vértices en gráficos dirigidos ponderados.