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.

Definición formal

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 de 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 i\in \{1,\ldots ,n\}}$ . La longitud del camino es ${\displaystyle n}$ .^[2]​^[1]​

Tipos de trayectorias relacionadas

 

Conceptos de conectividad en grafos, derivados de la noción de camino. En gris se mencionan traducciones alternativas del castellano. En cursivas el término original en inglés.

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

• Un recorrido (en inglés, trail, a veces traducido como rastro)^[1]​ es un camino sin aristas repetidas.
• Un camino cerrado es un camino cuyo vértice inicial y final coinciden.
• Un camino abierto es un camino cuyo vértice inicial y final no coinciden.
• Un camino simple (en inglés, path, a veces traducido como camino)^[1]​ es un camino sin vértices repetidos, salvo quizás el primero y el último (por lo tanto, es un tipo especial de recorrido, pues tampoco tiene aristas repetidas).
• Un circuito (en inglés, circuit) es un recorrido que además es un camino cerrado.
• Un ciclo (en inglés, cycle) es un camino simple que además es un camino cerrado.
• Un ciclo euleriano es un ciclo que pasa por todas las aristas del grafo una única vez.
• Un ciclo hamiltoniano es un ciclo que pasa por todos los vértices del grafo una única vez (en caso de que el vértice inicial y final no coinciden, se suele hablar también de camino hamiltoniano).

Trayectorias en grafos dirigidos

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]​

Trayectorias en grafos ponderados

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]​

Véase también

• Grafo camino
• Grafo conexo
• Camino hamiltoniano
• Ciclo euleriano
• Problema del camino más corto

Referencias

1. Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
2. Carrasco Pacheco, José Luis; Contreras Ordaz, Marco Antonio (2017). Modelado dinámico por inspección para convertidores de potencia CD a CD commutados: Un enfoque basado en grafos. Universidad Tecnológica de la Mixteca. Consultado el 25 de abril de 2021. 
3. Peay, E. R. (1980). «Connectedness in a general model for valued networks». Social Networks 2. pp. 385-410. doi:10.1016/0378-8733(80)90005-2.  Falta la |url= (ayuda)
4. Doreian, P. (1969). «A note on the detection of cliques in valued graphs». Sociometry 32. pp. 237-242. doi:10.2307/2786266.  Falta la |url= (ayuda)
5. Doreian, P. (1974). «On the connectivity of social networks». Journal of Mathematical Society 3. pp. 245-258. doi:10.1080/0022250X.1974.9989837.  Falta la |url= (ayuda)
6. Flament, C. (1972) [1963]. «Teoría de grafos y estructura de grupos» [Applications of graph theory to group structure]. Madrid: Tecnos.  Falta la |url= (ayuda)

Bibliografía

• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053. 

•   Datos: Q1415372