Grafo Euleriano-hamiltoneanos.doc

FACULTAD DE CIENCIA Y TECNOLOGIA Caminos y Ciclos de Euler

1

FACULTAD DE CIENCIA Y TECNOLOGIA

Figura 1. Ciclo de Euler. Un ciclo de un grafo o multigrafo, se dice de Euler si pasa por todos los vértices recorriendo cada arista exactamente una vez. Grafo Euleriano. Un grafo que admita un ciclo de Euler se denomina grafo euleriano. Primer Lema. Una condición necesaria para que un grafo o multigrafo sea Euleriano, es que todos sus vértices sean de grado par.

2

FACULTAD DE CIENCIA Y TECNOLOGIA Figura 2.

= {v1,v2,v3,v4,v5,v6,v7,v8,v5,v9,v3,v4,v10,v1} es de Euler En el primer lema se ha visto que si G es un grafo Euleriano, entonces todos sus vértices son de grado par Camino de Euler. Se dice que un camino de un grafo o multigrafo es de Euler si pasa por todos los vértices del mismo, recorriendo cada arista del mismo exactamente una vez. Claramente, el problema de los puentes de konisgberg estará resuelto si encontramos un camino de Euler en el multigrafo de la figura 1. Obsérvese que un camino de Euler en un grafo G puede entenderse también como una forma de dibujar el grafo sin levantar el lápiz del papel y sin pintar dos veces la misma arista. Segundo Lema. Una condición necesaria para que un grafo o multigrafo admita un camino de Euler es que el número de vértices de grado impar sea 2 o ninguno. En el multigrafo de la Figura 1. Hay cuatro vértices de grado impar, luego según el segundo lema no existe en él ningún camino de Euler, de aquí que no exista ningún camino que una dos puntos terrestres cruzando cada uno de los puentes exactamente una vez. Tercer Lema. Si G es un grafo en el que todos sus vértices tienen grado par, entonces para cada par de vértices adyacentes de G, pede encontrarse un ciclo que contiene a la arista que forman ambos TEOREMA. Un grafo o multigrafo G=(V,E) es Euleriano si y solo si es conexo y todos sus vértices tienen grado par. Ejercicio. Un cartero tiene asignadas para el reparto una red de calles representadas en la figura anterior. El reparto de cartas debe comenzar y acabar en la estafeta de correos que se encuentra en el vértice v9 y debe efectuarse sin recorrer dos veces la misma calle.

3

FACULTAD DE CIENCIA Y TECNOLOGIA De acuerdo a lo estudiado, indique si el grafo es Euleriano e indique cual sería la solución si es que existe

4