Caminos

Un camino es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor.

Un camino A es simple si no se repite ningún vértice en el. Dos caminos son independientes si no tienen ningún vértice excepto el primero y el último.

La longitud de un camino es el número de enlaces que tiene el camino. Por ejemplo: 1, 2, 5, 1, 2, 3 es un camino con longitud 5, y 5, 2, 1 es un camino simple de longitud 2.

Un camino de un grafo G = (V, R) es una secuencia de nodos de V en los que cada nodo es adyacente al siguiente mediante un arco de R, ejemplo:

V = {1, 2, 3, 4, 5, 6}

R = {(1, 4), (1, 5), (1, 6), (2, 3), …, (5, 1), (6, 2)}

Caminos: {1, 6, 2, 3}, {5, 1, 4}, …

Existen diferentes tipos de caminos:

· Camino simple: Es el camino que no recorre el mismo arco dos veces. b, d y g es un camino simple, pero b, d, g y b no es un camino simple.

Es un camino en el que todos los nodos contenidos son diferentes, con la posible excepción del primero y el último, que podrían ser el mismo.

· Camino cerrado: Es el camino que no visita un mismo nodo más de una vez. b y d es un camino elemental, pero b, d y g no lo es.