4.4    Caminos, Ciclos, Circuitos

Caminos

Un camino en un grafo es una sucesión finita en la que aparecen alternadamente vértices y aristas de dicho grafo.

Un camino es una secuencia de arcos en que el extremo final de cada arco coincide con el extremo inicial del siguiente en la secuencia.

 Un camino es simple si no se repiten vértices, excepto posiblemente el primero y el último.

Un ciclo es un camino simple y cerrado.

Camino euleriano: es un camino o circuito que contiene todas las aristas apareciendo cada una de ellas exactamente una vez. Un grafo que admite dicho circuito se denomina grafo euleriano, y sus vértices o tienen grado par o dos de los vértices tienen grado impar.

Camino hamiltoniano: es un camino simple que contiene todos los vértices apareciendo cada uno de ellos exactamente una vez. Un ciclo que a su vez es un camino hamiltoniano se denomina ciclo hamiltoniano, y un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano.