Camino (teoría de grafos)

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]

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).

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

• 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.