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 "Vértice (teoría de grafos)") y aristas "Arista (teoría de grafos)") 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 "Vecindad (teoría de grafos)") 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 , un camino es una sucesión de vértices y aristas tales que (en caso de que el grafo sea no dirigido), o bien (en caso de que sea dirigido), para todo . La longitud del camino es .[2]​[1]​.

Contenido

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

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 , a los recorridos como , a los ciclos como , etc.[1]​.