Caminos y ciclos

CAMINOS Y CICLOS
Camino o trayectoria es el recorrido desde un V0 (vértice inicial) a Vn (vértice destino) de longitud n, es una sucesión alternante de n + 1 vértices y n aristas que comienza en elvértice V0 y termina en el Vn . Formalmente significa: comience en el vértice v0; recorra la arista e1 hasta v1; siga por la arista e2 hasta v2, y así sucesivamente.
(v_0', e_1', v_1', e_2', v_2',…. v_{n - 1}, e_n, v_n)
Donde la arista e_i es incidente sobre los vértices v_{i - 1} y v_i para i = 1, … n.
Ejemplo:

Construyamos un camino en G desde el vértice 1 hasta el vértice 2 de longitud4.
Camino o trayectoria de G: (1, e_1, 2, e_2, 3, e_3, 4, e_4, 2)
Además, el mismo camino se puede representar así: (1, 2, 3, 4, 2)
En caso de que no se repita ningún vértice entonces recibe elnombre de camino simple, por ejemplo: (1, 2, 3,4) y (7, 6, 5,2)
IMPORTANTE
Sean v y w vértices en un grafo G.
* Un camino simple o trayectoria de v a w es una ruta de v a w sin vérticesrepetidos.
* Un ciclo (o circuito) es un camino de longitud diferente de cero de v a v sin aristas repetidas.
* Un ciclo simple es un ciclo de v a v en el que no hay vértices repetidos, exceptopor el inicio y el fin que son iguales a v.
Tomando como referencia la grafica anterior, vamos a determinar si tiene caminos simples, ciclo y ciclo simple.

Una vez aprendido las definicionesanteriores y comprendido el ejemplo, pasamos a estudiar lo que son las gráficas conexas.
Una grafica G es conexa si dados cualesquiera dos vértices v y w en G existe una trayectoria de v a w.
Lagrafica que se muestra no es conexa por cuanto no existe trayectoria de v_3 a v_5

Ejercicio
Realice el ejercicio 19 de la página 325 del texto base.
CICLO DE EULER Y DE HAMILTON
CICLO DE EULERSi una grafica G tiene un ciclo de euler, entonces G es conexa y todo vértice tiene grado par (2, 4, 6 …).

Ejemplo:
Verificar si la siguiente gráfica tiene ciclo de Euler.

Observamos que...