• Author / Uploaded
• JOse

Citation preview

Grafos Eulerianos y Hamiltonianos Teoria de Grafos

JOSE EDUARDO TIRADO VERBEL

UNIVERSIDAD DE CORDOBA INGENIERIA DE SISTEMAS IX SEMESTRE MONTERIA 2013

DEFINICION Grafos Eulerianos: El matemático suizo Leonhard Euler (1707-1783) escribió el primer artículo científico relativo a grafos, el que apareció en San Petersburgo, donde a partir de un problema concreto se hace la pregunta ¿en cuáles grafos se puede encontrar un camino cerrado que recorra todas las aristas una sola vez? Esta pregunta termina dando origen a los dos siguientes teoremas:  Un grafo conexo con todos sus vértices de grado par contiene un recorrido cerrado que pasa una y sólo una vez por cada una de las aristas. Todo grafo que admite tal recorrido es llamado euleriano.

 Un grafo conexo contiene un recorrido Sab que pasa una sola vez por cada arista si y sólo si a y b son los únicos vértices de grado impar. Todo grafo que admite tal recorrido es llamado semieuleriano Grafos hamiltonianos: Son los grafos que admiten un recorrido que pase exactamente una vez por cada uno de los vértices del grafo, los mismos son llamados así en honor al físico-matemático irlandés William Rowan Hamilton (1805-1865), que fue uno de los primeros en estudiar el tema. Produjo un juego de ingenio llamado “la vuelta al mundo”, que consistía en buscar un recorrido especial sobre un dodecaedro regular construido en madera. Los vértices de dicho poliedro representaban ciudades importantes del planeta y las aristas eran conexiones entre ellas, el recorrido consistía en pasar exactamente una vez por cada una de las ciudades. Tales recorridos se llaman cerrados o abiertos, según se regrese o no al punto de partida, respectivamente.

EJEMPLO Grafo Euleriano

Grafo Hamiltoniano

DIFERENCIAS •

Un ciclo euleriano es un camino euleriano que comienza y acaba en el mismo vértice.

•

Un camino hamiltoniano es un camino que recorre todos los vértices de un grafo sin pasar dos veces por el mismo vértice.

•

A diferencia de los grafos eulerianos, no hay una caracterización de cuando un grafo tiene un ciclo o un camino hamiltoniano.