Diseño y Análisis de

Algoritmos
ASC14

Euler y Hamilton

Augusto Cortez Vásquez

Euler y Hamilton
Augusto Cortez Vásquez 1
 Paseo Eureliano
Ciclo de Euler
Camino de Hamilton
Ciclo de Hamilton
Grafo de Petersen
Aplicaciones

Euler y Hamilton
2
Augusto Cortez Vásquez
Conceptos preliminares
En Teoría de Grafos, denominamos Camino a una secuencia de
vértices dentro de un grafo G, tal que exista una arista entre
cada vértice o nodo y el siguiente.

Se dice que dos vértices están conectados si existe un camino que vaya
de uno a otro, de lo contrario estarán desconectados.

Dos vértices pueden estar conectados por varios caminos.

El número de aristas dentro de un camino es su longitud.

Los vértices adyacentes están conectados por un camino de

longitud 1

Los segundos vecinos por un camino de longitud 2.

Si un camino empieza y termina en el mismo vértice se le

llama ciclo.

Euler y Hamilton
3
Augusto Cortez Vásquez
Caminos de longitud 1 (A,C) (B,G) …..

Caminos de longitud 2 (A,C,F) (B,G,E) …..

Caminos de longitud 3 (A,C,F,H) (B,G,E,C ) …..

Euler y Hamilton
4
Augusto Cortez Vásquez
Ejemplo 1

Caminos de A a H

longitud 1 (A,H)
longitud 2 (A,D,H) , (A,B,H)
longitud 3 (A,B,D, H)
longitud 4 (A,C,E,G, H)
longitud 5 (A,C,B, E,G, H) Euler y Hamilton
5
Augusto Cortez Vásquez
 Problema del paseo
Eureliano

Leonhard Euler escribió en 1736 el primer artículo sobre

teoría de grafos. Este articulo incluye una solución al
problema de los puentes de Königsberg.

Una trayectoria o camino en un grafo G es un

camino de Euler si incluye a cada una de sus
aristas solo una vez, puede ser necesario o no que se
comience y termine en el mismo vértice.

Un circuito o ciclo de Euler es un camino

de Euler que es a la vez un circuito, es decir inicia y
termina en el mismo vértice. Un ejemplo sencillo de esto
es el problema común de trazar una figura geométrica
sin levantar el lápiz del papel.

Euler y Hamilton
6
Augusto Cortez Vásquez
Un poco de historia
El problema de los puentes de Königsberg, también llamado más
específicamente problema de los siete puentes de Königsberg, es un
célebre problema matemático, resuelto por Leonhard Euler en 1736 y cuya
resolución dio origen a la Teoría de Grafos.

Su nombre se debe a Königsberg, la ciudad de Prusiana oriental y luego

de Alemania que desde 1945 se convertiría en la ciudad rusa fr Kaliningrado.

El problema se enuncia de la siguiente forma: Dos islas en el rio Pregel, en

Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es
posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra
firme, cruzando cada puente una sola vez y volviendo al punto de partida?
Euler y Hamilton
7
Augusto Cortez Vásquez
Euler enfocó el problema representando cada parte de tierra por un
punto y cada puente, por una línea, uniendo los puntos que se
corresponden. Entonces, el problema anterior se puede trasladar a
la siguiente pregunta: ¿se puede recorrer el dibujo sin repetir las
líneas?

Euler demostró que no era posible puesto que el número de líneas

que inciden en cada punto no es par (condición necesaria para entrar
y salir de cada punto, y para regresar al punto de partida, por caminos
distintos en todo momento).

Euler y Hamilton
8
Augusto Cortez Vásquez
Ejemplo 2
A, C,B,E,D no es ,

Euler y Hamilton
9
Augusto Cortez Vásquez
 Euler y Hamilton
10
Augusto Cortez Vásquez
 Euler y Hamilton
11
Augusto Cortez Vásquez
Ejemplo 3
Aplicación
Se presenta una aplicación que verifica si una secuencia de nodos
corresponde a un camino eureliano en un grafo.

El grafo se representa mediante un vector de cabeceras a las listas de

adyacencias de cada vértice del grafo.

Lista[i] contiene la cabecera de la lista de nodos adyacentes al vértice i.

Por simplicidad se asume que el valor de cada vértice es un entero, por tanto,
el índice k del vector lista, corresponde al vértice k, y contiene la cabecera
de los nodos adyacentes al vértice k.

Luego se ingresa una secuencia que es almacenada en una lista. Se recorre la

lista, verificando si corresponde o no a un camino eureliano.
Euler y Hamilton
12
Augusto Cortez Vásquez
Funcion VerificaEureiano()
Inicio
Leer G
Leer L
Si (Eureliano(G,L))
Escribir " La secuencia si es un camino eureliano"
Sino
Escribir " La secuencia no es un camino eureliano "
FinSi
Fin

Euler y Hamilton
13
Augusto Cortez Vásquez
 Euler y Hamilton
14
Augusto Cortez Vásquez
 Euler y Hamilton
15
Augusto Cortez Vásquez
Ejemplo 4

Euler y Hamilton
16
Augusto Cortez Vásquez
Ejemplo 5

Euler y Hamilton
Augusto Cortez Vásquez 17
Ciclo Hamiltoniano
Un ciclo hamiltoniano (ciclo H ) es
aquel ciclo en un grafo que contiene
cada vértice en C exactamente una
vez excepto el primero y el ultimo
que aparecen dos veces.

Un camino hamiltoniano, en el
campo matemático de la teoría de
grafos, es un camino de un grafo, Cuando existe tal ciclo
una sucesión de aristas adyacentes, hamiltoniano , lo
que visita todos los vértices del grafo llamaremos ciclo
una sola vez. Si además el último hamiltoniano y un grafo que
vértice visitado es adyacente al posea un ciclo hamiltoniano
primero, el camino es un se llama grafo hamiltoniano.
ciclo hamiltoniano

Euler y Hamilton
18
Augusto Cortez Vásquez
Condiciones necesarias para que un
grafo sea hamiltoniano.

• Un grafo hamiltoniano ha de ser conexo.

• Un grafo hamiltoniano no puede tener vértices de grado

1: en todos los vértices deben incidir al menos dos
aristas, la de “entrada” y la de “salida”.

• Si S es un subconjunto del conjunto de vértices de un

grafo G, escribimos G − S para designar el subgrafo que
aparece al eliminar todos los vértices de S y todas las
aristas adyacentes a los vértices de S.

Euler y Hamilton
19
Augusto Cortez Vásquez
Ejemplo 6

Euler y Hamilton
20
Augusto Cortez Vásquez
Ejemplo 7

Aplicación
Se presenta una aplicación que verifica si una secuencia de nodos
corresponde a un camino hamiltoniano en un grafo.
El grafo se representa mediante un vector de cabeceras a las listas de
adyacencias de cada vértice del grafo.
Lista[i] contiene la cabecera de la lista de nodos adyacentes al vértice i.

Por simplicidad se asume que el valor de cada vértice es un entero, por

tanto el índice k del vector lista, corresponde al vértice k, y contiene la
cabecera de los nodos adyacentes al vértice k.

Luego se ingresa una secuencia que es almacenada en una lista . Se recorre

la lista, verificando si corresponde o no a un camino hamiltoniano

Euler y Hamilton
21
Augusto Cortez Vásquez
Funcion VerificaHamiltoniano()
Inicio
Leer G
Leer L
Si (Hamiltoniano(G,L) )
Escribir " La secuencia si es un camino hamiltoniano"
Sino
Escribir " La secuencia no es un camino hamiltoniano "
FinSi
Fin

Euler y Hamilton
22
Augusto Cortez Vásquez
Ejemplo 8

Euler y Hamilton
Augusto Cortez Vásquez 23
Ejemplo 9

Euler y Hamilton
24
Augusto Cortez Vásquez
Ejemplo 10

Euler y Hamilton
25
Augusto Cortez Vásquez
 Euler y Hamilton
26
Augusto Cortez Vásquez
En teoría de grafos, el grafo de
Petersen es un grafo no dirigido
con 10 vértices y 15 aristas . Es un grafo
pequeño que sirve como ejemplo y
contraejemplo para muchos problemas
en la teoría de grafos. El grafo de
Petersen lleva el nombre de Julio
Petersen, quien en 1898 lo construyó
para ser el grafico cubico sin puentes
más pequeño que no se puede 3-
colorear.
Características
a) Es un grafo regular de grado 3.
b) Dos vértices adyacentes no tienen vecinos en común, pero, no es
bipartito, pues existen varios ciclos de longitud impar.
c) Dos vértices no adyacentes tienen exactamente un vecino en
común.

Euler y Hamilton
27
Augusto Cortez Vásquez
Ciclos y caminos hamiltonianos
El grafo de Petersen tiene un camino
hamiltomiano pero no un ciclo
hamiltoniano. Es el grafo cúbico sin
puente más pequeño sin ciclo
hamiltoniano.
Es grafo es hipoamiltoniano, lo
que significa que aunque no tiene un
ciclo hamiltoniano, al eliminar cualquier
vértice se convierte en hamiltoniano, y
es el grafo hipoamiltoniano más
pequeño.

W1 : 1,2,3,4,9,7,10,8,6,1 No consideramos
W2 : 1,2,7,10,8,3,4,9,6,1
W3 : 1,6,8,10,7,9,4,3,2,1 el vértice 5
W4 : 1,6,9,4,3,8,10,7,2

Euler y Hamilton
28
Augusto Cortez Vásquez
 Ejemplo 11

W1 : 1,2,3,8,6,9,7,10,5,1

W2 : 1,5,10, 7,9, 6,8,3,2,1 No consideramos

W3 : 1,6,9,7,2,3, 8, 10,5,1
el vértice 4

Euler y Hamilton
29
Augusto Cortez Vásquez
 A
El grafo es eureliano
y hamiltoniano

C B

Euler y Hamilton
30
Augusto Cortez Vásquez
A D

C E

El grafo es eureliano y no hamiltoniano

Euler y Hamilton
31
Augusto Cortez Vásquez
 A D

C E

El grafo no es eureliano , pero si hamiltoniano

Euler y Hamilton
32
Augusto Cortez Vásquez
 A F D

C E

El grafo no es eureliano y no es hamiltoniano

Euler y Hamilton
33
Augusto Cortez Vásquez