Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Grafo de Euler, Algoritmo

No description
by

Yina Paola Arrieta Ramos

on 14 October 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Grafo de Euler, Algoritmo

Grafo de Euler, Algoritmo de Fleury


Gina Arrieta Ramos

design by Dóri Sirály for Prezi
El origen de la teoría de los ciclos eulerianos fue planteado y resuelto por el propio Leonhard Euler en 1736 en un problema que tiene el nombre de Siete puentes de la ciudad de Königsberg (Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia rusa) dando origen a la Teoría de los grafos
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, el antiguo nombre que recibía la ciudad rusa de Kaliningrado, que durante el siglo XVIII formaba parte de Prusia Oriental, como uno de los ducados del Reino de Prusia.

Esta ciudad es atravesada por el río Pregolya, el cual se bifurca para rodear con sus brazos a la isla Kneiphof, dividiendo el terreno en cuatro regiones distintas, las que entonces estaban unidas mediante siete puentes llamados Puente del herrero, Puente conector, Puente verde, Puente del mercado, Puente de madera, Puente alto y Puente de la miel.El problema fue formulado en el siglo XVIII y consistía en encontrar un recorrido para cruzar a pie toda la ciudad, pasando sólo una vez por cada uno de los puentes, y regresando al mismo punto de inicio.

HISTORIA
GRACIAS
Problema de los puentes de Königsberg
El problema, formulado originalmente de manera informal, consistía en responder a la siguiente pregunta:

Dado el mapa de Königsberg, con el río Pregolya dividiendo el plano en cuatro regiones distintas, que están unidas a través de los siete puentes, ¿es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo sólo una vez cada uno, y regresando al mismo punto de partida?


La respuesta es negativa, es decir, no existe una ruta con estas características. El problema puede resolverse aplicando un método de fuerza bruta, lo que implica probar todos los posibles recorridos existentes. Sin embargo, Euler en 1736 en su publicación «Solutio problematis ad geometriam situs pertinentis» demuestra una solución generalizada del problema, que puede aplicarse a cualquier territorio en que ciertos accesos estén restringidos a ciertas conexiones, tales como los puentes de Königsberg.

Análisis y solución del problema

Para dicha demostración, Euler recurre a una abstracción del mapa, enfocándose exclusivamente en las regiones terrestres y las conexiones entre ellas. Cada puente lo representó mediante una línea que unía a dos puntos, cada uno de los cuales representaba una región diferente. Así el problema se reduce a decidir si existe o no un camino que comience por uno de los puntos azules, transite por todas las líneas una única vez, y regrese al mismo punto de partida.

Análisis y solución del problema
Grafo Eulerianos
Un grafo es euleriano si contiene un camino o un circuito euleriano,Todo grafo euleriano debe ser conexo.



Antes de dar una definición completa de los grafos Eulerianos es necesario tener en cuenta unos conceptos de grafos que son necesarios para dicha definición

Antes de dar una definición completa de los grafos Eulerianos es necesario tener en cuenta unos conceptos de grafos que son necesarios para dicha definición
Definición de Grafo Euleriano:
Definiciones:

Camino euleriano:
Es un camino que recorre todos los arcos del grafo una sola vez. Por lo tanto, es un camino simple que transita por todos los arcos del grafo.

Circuito euleriano:
Es un camino euleriano, donde el vértice de partida coincide con el vértice de llegada.
Teorema 1 de Euler
: Sea G un grafo conexo. Entonces G es euleriano si y solo si todos sus vértices tienen grado par.

Teorema del Circuito Euleriano:
Teorema 2 de Euler:
Sea G un grafo conexo que no es euleriano. Entonces G contiene un camino euleriano (no cerrado) si y solo si existen exactamente dos vértices de grado impar. En este caso, cualquier camino euleriano tiene sus extremos en estos dos

vértices.

EJEMPLO
ALGORITMO DE FLEURY
El algoritmo de Fleury permite determinar un circuito de Euler, y un circuito de Euler es aquel ciclo que recorre todos los vértices pasando por todos los lados solamente una vez.Un grafo tiene un circuito de Euler si y solo si es conexo y todos sus vértices tienen valencia par.
reglas básicas del algoritmo de Fleury para encontrar circuitos de Euler.
Regla 1. Cerciórate que la gráfica sea conexa y que todos sus vértices tengan grado par.
Regla 2. Elige un vértice inicial (de manera arbitraria).
Regla 3. En cada caso paso, recorre cualquier arista disponible,eligiendo un puente solo cuando no haya alternativa.
Regla 4. Después de recorrer cualquier arista, borrarla y recorre otra arista disponible. Borra los vértices de grado cero que resulten.
Regla 5. Cuando ya no puedes seguir el recorrido, para.
¡Habrás encontrado un circuito de Euler!
EJEMPLOS DE ALGORITMO DE FLEURY
Ilustraremos el uso del algoritmo del Fleury,mediante el siguiente ejemplo:
La gráfica tiene todos sus vértices grado Par, y al por lo menos tiene un circuito de Euler.
I
nicio:
Elegimos el vértice A.
Pudimos haber elegido cualquier vértice

Paso 1:
Elegimos la arista AB.
Desde a hay tres aristas disponibles. La arista AB, la arista BC y la aristaAD.como ninguna es puente, se puede elegir cualquier.





Paso 2:
Elegimos la arista BC


PASOS PARA RESOLVER EL ALGORITMO
PASOS PARA RESOLVER EL ALGORITMO
PASOS PARA RESOLVER EL ALGORITMO
PASOS PARA RESOLVER EL ALGORITMO
PASOS PARA RESOLVER EL ALGORITMO
Full transcript