Camino (teoría de grafos)

En teoría de grafos, un camino (en inglés, walk, y en ocasiones traducido también como recorrido)^[1]​ es una sucesión de vértices y aristas dentro de un grafo, que empieza y termina en vértices, tal que cada vértice es incidente con las aristas que le siguen y le preceden en la secuencia.^[2]​ Dos vértices están conectados o son accesibles si existe un camino que forma una trayectoria para llegar de uno al otro; en caso contrario, los vértices están desconectados o bien son inaccesibles.^[1]​

Dos vértices pueden estar conectados por varios caminos. La longitud de un camino es su número de aristas. Así, en un grafo no dirigido, los vértices adyacentes están conectados por un camino de longitud 1, los segundos vecinos por un camino de longitud 2, y así sucesivamente. Un grafo no dirigido es conexo si todos sus vértices están conectados a través de un camino.^[2]​ Un grafo conexo cuyos vértices y aristas permiten definir un camino es un grafo camino.

Dado un grafo ${displaystyle G=(V,E)}$, un camino es una sucesión de vértices ${displaystyle v_{1}v_{2}ldots v_{n+1}}$ y aristas ${displaystyle l_{1}l_{2}ldots l_{n}}$ tales que ${displaystyle l_{i}={v_{i},v_{i+1}}}$ (en caso que el grafo sea no dirigido), o bien ${displaystyle l_{i}=(v_{i},v_{i+1})}$ (en caso de que sea dirigido), para todo ${displaystyle iin {1,ldots ,n}}$. La longitud del camino es ${displaystyle n}$.^[2]​^[1]​

Existen varios conceptos derivados del de camino:^[2]​

Las definiciones de trayectorias anteriores también se aplican a grafos dirigidos, siempre y cuando los caminos respeten la dirección de las aristas entre cada vértice y el siguiente. Sin embargo, si en un grafo dirigido se desea prescindir de la dirección de las aristas y considerar sus trayectorias como si se tratara de un grafo no dirigido, entonces a los caminos se les conoce como semicaminos, a los recorridos como semirrecorridos, a los ciclos como semiciclos, etc.^[1]​

En el contexto del análisis de redes sociales, para las redes sociales representadas como grafos ponderados, es decir, con pesos en las aristas, el valor de un camino o semicamino puede definirse como el valor mínimo de todas las aristas que contiene.^[3]​ Un camino a nivel c es un camino entre un par de vértices tal que todas las aristas que contiene son mayores o iguales al valor c.^[4]​ Dos vértices son accesibles a nivel c si existe un camino a nivel c entre ellos.^[5]​ La longitud de un camino en un grafo ponderado corresponde a la suma de los valores de las aristas incluidas en dicho camino.^[6]​^[1]​

---