Download - Monografia de Algoritmo de Fleury
UNIVERSIDAD NACIONAL DEL ALTIPLANO
FACULTAD DE INGENIERIA
ELECTRICA
ESCUELA PROFESIONAL DE INGENIERIA DE
UNIVERSIDAD NACIONAL DEL ALTIPLANO
PUNO
FACULTAD DE INGENIERIA MECANICA
ELECTRICA, ELECTRONICA, Y SISTEMAS
ESCUELA PROFESIONAL DE INGENIERIA DE
SISTEMAS
MONOGRAFIA
ALGORITMO DE FLEURY
PRESENTADO POR:
COAQUIRA PINTO, WILBER
MAMANI QUISPE, EDWIN
DOCENTE:
Mg. COYLA IDME, ELMER
PUNO- PERÚ
2011
Pág. 1
UNIVERSIDAD NACIONAL DEL ALTIPLANO
MECANICA
ELECTRONICA, Y SISTEMAS
ESCUELA PROFESIONAL DE INGENIERIA DE
Pág. 2
Dedicatoria
A mis padres, mis hermanos
quienes siempre me han brindado
el apoyo moral e incondicional
durante mi formación profesional.
Edwin
Quiero dedicar este trabajo, a la persona más
importante de mi vida, mi madre, quien cuyo
esfuerzo ha hecho este logro, también a mi
padre y mis hermanos, por el apoyo que me
brindaron, por su cariño, por su compresión,
pero sobre todo por haberme ayudado a formar
me como profesional.
Wilber
Pág. 3
INTRODUCCIÓN
Una de las partes de la teoría de grafos, es esta teoría que permite modelar
de forma simple cualquier grafo conexo de grado par, ciclo y circuito Euleriano;
y es por esto que su ámbito de aplicación es muy general y cubre áreas que
van desde la misma matemática.
En la teoría de grafos y algoritmo de Fleury podemos decir: Si una grafica
conexa tiene exactamente dos vértices de grado impar, entonces sabemos por
los teoremas de Euler que no tiene un circuito Euler pero si tiene al menos una
trayectoria de Euler que empieza y termina en dichos vértices.
El algoritmo de Fleury (Grafos Eulerianos) que permite encontrar una
trayectoria o circuito de Euler. Y un puente es una arista tal que al quitarla del
grafo, el grafo se convierte en un grafo disconexo.
Y también Podemos encontrar una trayectoria de Euler usando una versión
modificada del algoritmo de Fleury.
Entonces decimos que el Algoritmo de Fleury nos permite construir un camino
Euleriano en un gráfico de Euler dado combinando ciclos.
Pág. 4
PRESENTACIÓN
El presente monografía es el producto de un revisión bibliográfica
consecuentemente en la redacción del presente trabajo de investigación,
con el fin que el estudiante de ingeniería de sistemas sea haga familiar los
temas que se tratan en el presente trabajo de investigación
El presente monografía consta de los siguientes capítulos:
CAPÍTULO I : En este capítulo, trabajaremos las nociones básicas de la
teoría de grafos. Nuestra intención en este capítulo no es hacer un estudio
extenso de la teoría de grafos, sino más bien una introducción a la teoría
de graficas. Se da conocer algunos conceptos y resultados mínimos para
destacar su gran utilidad para una optima comprensión del algoritmo de
Fleury.
CAPÍTULO II : En este capítulo se da a conocer sobre circuito de Euler y
sus definiciones básicas de diferentes fuentes bibliográficas se define sobre
un circuito que contiene todas las aristas de G recibe el nombre de circuito
Euleriano ha tratarse más adelante.
CAPÍTULO III: En este capítulo consideramos algunos problemas que
involucran el hallazgo un camino con alguna propiedad especial en un
gráfico dado. Y así mismo se desarrolla el algoritmo de Fleury por encontrar
un camino Euleriano en un gráfico de Euler dado explicado con ejemplo; a
tratarse más adelante en sección correspondiente.
Pág. 5
PROLOGO
Los circuitos de Euler y una de sus áreas principales como el algoritmo de
Fleury ocupan hoy en día un lugar muy importante en los conocimientos
básicos que deben adquirir las personas que se dedican al estudio de las
ciencias de la computación e ingenierías y las matemáticas aplicadas a la
computación.
Además la Teoría de Grafos puede servir para el modela miento de sistemas,
la simulación, la estructuración de datos y el análisis y diseño de algoritmo.
El presente trabajo de investigación (monografía) pretende ser una guía
introductoria para que esta pueda ser comprendida de una forma satisfactoria.
El tema central de esta monografía es una introducción al algoritmo de Fleury,
considerando los grafos y los circuitos Eulerianos como una estructura
dinámica que pretende explicar el camino Euleriano con el algoritmo de Fleury
aplicadas en la vida real.
Los autores
Pág. 6
En este capítulo, trabajaremos las nociones básicas de la teoría de grafos.
Nuestra intención en esta sección no es hacer un estudio extenso de los
grafos. Lo que corresponde a una materia conocida como Teoría de Grafos
y que es tan amplia como la propia Programación matemática. Nuestra
intención es dar unos conceptos y resultados mínimos para destacar su
gran utilidad para una optima comprensión del algoritmo de Fleury.
A si mismo se hará una introducción a los conceptos básicos de la teoría
de grafos con el fin de entender el algoritmo de Fleury.
CAPITULOCAPITULOCAPITULOCAPITULO
1 Introducción a GrafosIntroducción a GrafosIntroducción a GrafosIntroducción a Grafos
Pág. 7
1.1 Teoría de grafos
Los grafos son una estructura de datos no lineal, la cual se puede usar
para modelar diversas aplicaciones Es una parte importante de la
Matemáticas aplicadas en la computación, lo que le da un carácter
bastante amplio y complejo.
Figura Nº 01
Los grafos se presentan con frecuencia en la vida real, tal es el caso de
una red de carreteras que enlace un cierto grupo de ciudades aquí los
nodos de la red o ciudades representan los vértices de grafo. Las
carreteras que unen las ciudades representan los arcos o arista, así a cada
arco se asocia una información tal como la distancia entre ciudades,
consumo de gasolina, costo de mantenimiento, etc.
1.2 ¿Qué es un grafo?
MICHA (2003)1. Una grafo es un diagrama que consiste de puntos
(llamados vértices) unidos por líneas (llamadas aristas). Cada arista
conecta a dos vértices.
´
1 MICHA, Elías. (2003). Matemáticas discretas, México D.F. pág. 18.
Pág. 8
SALAZAR (2001) 2.Los grafos tratan de dotarnos de herramientas graficas
que facilitan el estudio de algunos problemas que aparecen frecuentemente
en la práctica. Fundamentalmente hay dos tipos de grafos, orientados y no
orientados.
BORREGO y RECIO (2006)3.Un grafo G es un conjunto finito, no vacío de
vértices V (G) y un conjunto de aristas E (G) que puede ser vacío formado
por pares no ordenados de elementos pertenecientes a V (G). Solo se
establecerá un orden cuando hablemos de grafos dirigidos y a las aristas
se las denomina arcos.
En conclusión podemos afirmar que un grafo G consiste de un conjunto
finito no vacio de objetos llamado vértices y de un conjunto de parejas no
ordenadas de vértices llamadas aristas. Denotaremos por V (G) al conjunto
de vértices de una grafica G y por A (G) al conjunto de aristas.
1.2.1 Elementos
MARTINES y QUIROGA (2010) 4. Un grafo consiste de nodos y
arcos. En general, cada nodo puede contener más de un valor, sin
embargo, el caso particular es que almacene una única llave, de
tal forma que por esta se identifique a cada elemento.
1.2.2 Estructura
MARTINES y QUIROGA (2010) 5. Posee una estructura de red.
Cada arco establece una relación uno a uno entre dos nodos. Un
par de nodos puede estar conectado por un único arco. Pero cada
nodo puede conectarse a cualquier conjunto de nodos.
2 SALAZAR GONZALES, J. Pablo. (2001).Programación Matemática, Madrid-España. pág. 259. 3 BORREGO R., R. y RECIO D., D. (2006). MANUAL DE ALGORÍTMICA, Proyecto fin de carrera Escuela Técnica Superior de Ingeniería Informática Departamento Matemáticas Aplicadas I, universidad de Sevilla-España. pág. 8 4 MARTINES, Román y QUIROGA, Elda. (2010). Estructuras De Datos (Referencia Practica Con Orientación a Objetos), Armenia. pág. 221 5 MARTINES, R. y QUIROGA, E. (2010). pág. 221
Pág. 9
EJEMPLO
Este ejemplo se conoce como el problema de los servicios públicos, y se
refiere a la necesidad de conectar tres casas A, B y C a tres servicios públicos:
gas, agua y electricidad. Por razones de seguridad es necesario que las
conexiones no se crucen entre sí. ¿Es posible conectar los servicios?
Grafica Nº 02
1.3 Grafos orientados
SALAZAR (2001) 6. el grafo orientado (o dirigido) a una pareja de conjuntos
G = (N, A) donde N es un conjunto finito de elementos, y A es un conjunto
finito de pares ordenados a = (i, j), siendo i y j elementos de N. A cada
elemento de N se le llama nodo, y a cada elemento de A se le llama arco.
Al primer nodo de un arco a = (i, j) � A, es decir, a i, se le llama origen de a
y al segundo nodo, es decir, a j, se le llama destino de a.
6 SALAZAR G. Ob. Cit. pag.260.
Pág. 10
Ejemplo de grafo dirigido.
Grafica Nº 03
1.4 Grafos no orientados
SALAZAR (2001) 7.Dado un grafo orientado G = (N, A), si sucede que (i, j)
� � implica cine (j. i) � A, entonces en muchas aplicaciones conviene que
cada una de estas parejas de arcos sea sustituida por un único par no
ordenado, simplificando así el grafo. Aparecen así los grafos no orientados.
Se llama grafo no orientado (o no dirigido) a una pareja de conjuntos G =
(N, E) donde N es un conjunto finito de elementos, y E es un conjunto finito
de pares no ordenados e = [i, j] = [j,i], siendo i y j elementos de N. A cada
elemento de A* se le llama nodo, y a cada elemento de E se le llama arista.
Cuando una arista e está formada por los nodos i y j. entonces se dice que
la arista e es incidente al nodo i (y al nodo j), y que i y j son los nodos
extremos de e8.
7 SALAZAR G. Ob. Cit. pag.263.
Pág. 11
Ejemplo de grafo ponderado no dirigido.
Grafica Nº 04
Pág. 12
En este capítulo se da a conocer sobre circuito de Euler y sus
definiciones básicas .Entonces podemos decir que un circuito que
contiene todas las aristas de G recibe el nombre de circuito Euleriano.
Es decir que un circuito Euleriano es una trayectoria que empieza y
termina en el mismo vértice, pasa por cada vértice al menos una vez
y sólo una vez por cada arista.
CAPITULOCAPITULOCAPITULOCAPITULO
2 Circuito EulerianoCircuito EulerianoCircuito EulerianoCircuito Euleriano
Pág. 13
2.1 CIRCUITO EULERIANO
Cuando se posee una red no dirigida conexa se puede disertar un circuito
que recorra todos SIJS nodos, partiendo de un nodo especifico Y regresando
a ÉL, pero sin pasar más de una vez por cada arco, además escogiendo el
circuito de forma tal que el recorrido sea mínimo. Este tipo de problema se
resuelve hallando un circuito Euleriano de longitud mínima.
2.2 Definiciones básicas
2.2.1 Grado
SEYMOUR (2007)9. El grado de un vértice es el número de
aristas que se encuentran en ese vértice. En un sentido más
formal El grado de un vértice v en un grafo g, se escribe grd (v),
es igual al número de aristas en G que contienen a v; es decir,
que inciden sobre v. puesto que cada arista se cuenta dos veces
al contar lo grados de los vértices de G.
MARTINES y QUIROGA (2010) 10. Grado de un grafo es el
máximo grado de sus nodos. Donde este se define como la
cantidad de aristas que inciden en ese nodo. En el caso de
dígrafos se distingue entre el grado_entrada y el grado_salida. El
primero define la cantidad de arcos en los que el nodo es el
destino y el segundo es la cantidad de arcos donde es el origen.
2.2.2 Vértices adyacentes
MICHA (2003)11. Dos vértices son adyacentes si comparten una
sola arista.
2.2.3 Trayectoria
MICHA (2003)12. Una trayectoria es una sucesión de vértices con
la propiedad de que cada vértice es adyacente al siguiente y tal
que en la correspondiente sucesión de aristas; todas las aristas
9 SEYMOUR LIPSCHUTE, Marc L. (2007). Matemáticas Discretas, Tercera Edición, México. pág. 157. 10 MARTINES, R. y QUIROGA, E. (2010). Ob. Cit. pág. 221. 11 MICHA, E. (2003). Ob. Cit. pág. 26. 12 MICHA, E. (2003). Ob. Cit. pág. 26.
Pág. 14
son distintas. Es decir que un vértice si puede aparecer en una
Trayectoria más de una vez.
2.2.4 Camino
SALAZAR (2001) 13Se llama camino a una secuencia de aristas
donde cada par de aristas consecutivas son ambas incidentes con
un mismo nodo. Los nodos no necesariamente comunes de la
primera y de las últimas aristas se llaman extremos Del camino,
mientras que los comunes se llaman intermedios.
Un camino se dice simple si sus nodos intermedios son todos
diferentes, se dice elemental si sus aristas son todas diferentes,
se dice ciclo si sus extremos son un mismo nodo. Obviamente
todo camino simple es elemental, pero no recíprocamente.
SCHEINERMAN (2001)14.Es una sucesión de lados que van de
un vértice x aun vértice w (dichos lados pueden repetir) pero no
se puede repetir vértices.
2.2.5 Ciclo
SCHEINERMAN (2001)15.Un ciclo es una caminata de longitud
mínima de vértices, en la que el primero y el último vértice son el
mismo, pero no se repiten otros vértices. El termino ciclo también
se refiere a un sub (grafica) formada por los vértices y aristas de
la caminata. En otras palabras, un ciclo es un grafica de forma
G= (V,E).
MARTINES y QUIROGA (2010) 16. En un grafo dirigido, el ciclo es
un camino donde el nodo de inicio y el nodo de terminación son el
mismo.
13 SALAZAR G. Ob. Cit. pág. 264-265. 14 SCHEINERMAN R. Edward (2001). Matemáticas discretas, México. p. 371. 15 SCHEINERMAN R. (2001). Ob. Cit. pág.377. 16 MARTINES, R. y QUIROGA, E. (2010). Ob. Cit. pág. 221.
Pág. 15
2.2.6 Circuito
MICHA (2003)17. Un circuito es una trayectoria que inicia y
termina en el mismo vértice.
2.2.7 Grafo conexo
MICHA (2003)18. Un grafo es conexo si cualesquiera dos de sus
vértices se pueden unir por una trayectoria. Si una grafica no es
conexa, se dice que es disconexa.
SEYMOUR (2007)19.Un grafo G es conexo si existe un camino
entre dos de sus vértices. En términos formales, en el supuesto
que cualquier v este unido consigo mismo, la relación “v esta
unido con u” es una relación de equivalencia sobre el conjunto de
vértices de un grafo G y las clases de equivalencia de la relación
constituyen los componentes conexos de G.
2.2.8 Grafica disconexa
MICHA (2003)20. Una grafica disconexa está formada de varios
pedazos, cada uno de los cuales es una grafica conexa. A los
pedazos se les llama componentes de la grafica.
2.2.9 Circuito Euleriano
SEYMOUR (2007)21. En una red conexa un circuito que recorra
todos los nodos y todos los arcos pasando una vez por cada arco,
se llama circuito euleriano. Si la red no es conexa puede
ocurrir que no exista un circuito euleriano.
17 MICHA, E. (2003). Ob. Cit. pág. 27. 18 MICHA, E. (2003). Ob. Cit. pág. 26. 19 SEYMOUR LIPSCHUTE, Marc L. (2007). Matemáticas Discretas, Tercera Edición, México. p.160. 20 MICHA, E. (2003). Ob. Cit. pág. 26. 21 SEYMOUR, M (2007). Ob. Cit. pág.169.
Pág. 16
2.2.10 Trayectoria Euleriana
BERNARD, KOLMAN y SHARRON (1997)22. Una trayectoria en
una grafica G es una trayectoria de Euler si incluye a cada una de
las aristas solo una vez. Un circuito de Euler es una trayectoria de
Euler que es a la vez un circuito.
CALCEDO y DE GARCIA (2010)23. el problema de determinar un
circuito euleriano de longitud mínima de una red conexa, también
es llamado El Problema del Cartero o Problema Chino del cartero
el cual apareció formulado por primera vez por M. K. Kwan en el
Chínese Mathematical Journal. Sus orígenes remontan a 1736
cuando Léonard Euler estudió el problema de los puentes de
Konigsberg.
2.3 Puentes de Konigsberg
MALVA, VIVIANA Y YANINA. (2005) 24.La ciudad de Konigsberg. Situada
en Prusia Oriental, en la época de Euler (1707-1783) y hoy perteneciente a
Rusia con el nombre de Kaliningrado es atravesada por el río Pregel o
Pregolia. La parte central de la ciudad se encuentra sobre una isla del rio
llamada Kniphof que se une a las dos orillas por cuatro puentes, dos a lado:
un quinto puente une a Kniphof con otra Isla que también está unida a las
orillas por dos puentes, uno hacía cada orilla.
VALIENTE, G. (2001)25. El origen de la teoría de grafos se asocia a
menudo con la resolución que dio Euler del llamado problema de los
puentes de Kiinigsberg (1736). Esta antigua ciudad prusiana. Dividida per
el rio Progel, que bordea la isla de Kneiphof, tenía siete puentes dispuestos
como indica la figura 7.1. Los habitantes de esta ciudad se planteaban la
cuestión siguiente: es posible, paseando. Hacer un recorrido que pase una 22 BERNARD Robert, KOLMAN Busby y SHARRON Ross. (1997).Estructuras De Matemáticas Discretas Para La Computación, México. p. 204. 23 CALCEDO B., Alfredo, W. DE GARCIA G. y M. P. R. María (2010). Introducción a la teoría de grafos, primera Edición, pág. 45. 24 MALVA A., S. I. C. Viviana y F. Yanina. (2005).Matemática Discreta con aplicaciones a las ciencias de la programación y de la computación. Universidad nacional de Litoral, Santa fe-Argentina. pág. 332 25 VALIENTE, Gabriel. (2001). Matemática Discreta, Barcelona-España. pág. 142.
Pág. 17
única vez por cada uno de los siete puentes La resolución que dio Euler de
este problema no solamente respondía a esta cuestión, sino que introducía
la noción de grafo y resolvía al mismo tiempo un problema de carácter mis
general.
Grafica Nº 05
Pág. 18
En este capítulo nosotros consideramos algunos problemas que
involucran el hallazgo un camino con alguna propiedad especial en un
gráfico dado o dígrafos. Primero, nosotros describimos el algoritmo de
Fleury por encontrar un camino Euleriano en un gráfico de Euler dado.
Y luego algunos ejemplos de algoritmo de Fleury de la cual describimos
un algoritmo por encontrar un camino más corto de cualquier vértice
dado a otro. Con algunos ejemplos didácticos.
CAPITULOCAPITULOCAPITULOCAPITULO
3 Algoritmo de FleuryAlgoritmo de FleuryAlgoritmo de FleuryAlgoritmo de Fleury
Pág. 19
3.1 TRAYECTORIAS Y CIRCUITOS EULERIANOS CON FLEUR Y
Una Trayectoria de Euler es una trayectoria que recorre todas las aristas de un
grafo conexo. Análogamente, un Circuito de Euler es un circuito que recorre
todas las aristas de un grafo conexo. En las secciones anteriores se dejaron
abiertas preguntas, como la de los puentes de Konigsberg y la firma del diablo,
es claro que todas estas preguntas se resumen a encontrar un circuito de Euler
en los grafos correspondientes, esto motiva a una pregunta un poco más
general.
¿Para qué grafos existe un circuito de Euler?
¿Para qué grafos existe una trayectoria de Euler?
Los dos siguientes teoremas dan respuesta a esto.
3.1.1 TEOREMA 1.- Existencia de trayectorias de Eul er. .
1. Si un grafo tiene más de dos vértices de grado impar, entonces no
puede tener una trayectoria de Euler.
2. Si un grafo conexo tiene exactamente dos vértices de grado impar,
entonces tiene por lo menos una trayectoria de Euler. Cualquier
trayectoria de Euler debe iniciar en uno de los vértices de grado
impar y terminar en el otro.
Una explicación sencilla del anterior teorema es la siguiente. Euler observó que
para encontrar una trayectoria en un grafo que cruce una sola vez cada arista
es necesario que cada vez que la trayectoria tome una arista para llegar a un
vértice, debe haber otra arista distinta que permita abandonarlo para poder
continuar con el recorrido.
De esta manera si un vértice tiene grado impar existe una arista más que llega
al vértice que las que salen de el, o viceversa, esto convierte al vértice en un
punto final o punto inicial. Por tanto para que exista una trayectoria de Euler es
necesario que exista a los más dos vértices de grado impar.
Pág. 20
La existencia de la trayectoria cuando el grafo es conexo se verá mas adelante
con el algoritmo de Fleury.
Ahora, sino se desea una trayectoria sino un circuito de Euler es necesario que
el punto final coincida con el punto inicial, por tanto el grafo no puede tener
vértices de grado impar como lo muestra el siguiente teorema.
3.1.2 TEOREMA 2. Existencia de circuitos de Euler .
1. Si en un grafo algún vértice tiene grado impar, entonces no puede
tener un circuito de Euler.
2. Si todos los vértices de un grafo conexo tienen grado par, entonces
hay por lo menos un circuito de Euler.
3.2 ALGORITMO DE FLEURY
Definición.- 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.
Por lo que definiremos sobre el algoritmo de Fleury que define diferentes
autores que se describe en ello.
Según MICHA (2003) 26 , en su libro “Matemáticas Discretas” define algoritmo
de Fleury.
Los teoremas de Euler nos proporcionan criterios muy simples para decidir si
una grafica posee una trayectoria o un circuito de Euler. Desafortunadamente
los teoremas de Euler no nos ayudan a encontrarlos en el caso de que si
26 MICHA, E. (2003). Ob. Cit. pág. 37.
Pág. 21
existan. Ya vimos el caso de graficas sencillas podemos reconstruir las
trayectorias o circuitos de Euler por medio de ensayo y error.
Por ejemplo, si nos dan una grafica con solo 6 vértices, todo de grado par, es
muy probable que sea tan fácil construir un circuito de Euler por medio de
ensayo y error como por medio de la aplicación de un procedimiento
sistemático. Sin embargo, la mayoría de las graficas que surgen de situaciones
prácticas pueden tener cientos o miles de vértices. Para este tipo de graficas es
necesario usar un algoritmo. Ya vimos que en una grafica conexa, un puente
es una arista tal al la, la grafica se vuelve disconexa.
El algoritmo de Fleury nos instruye que viajemos por un puente solo como
último recurso. Es decir, solamente podemos usar un puente cuando este sea
la única arista que se pueda usar para continuar el recorrido. En un lenguaje
coloquial podemos resumir la regla fundamental del algoritmo de Fleury en la
siguiente frase:
“ No cruces un puente a menos que no te quede otro remedio”
GRIMALDI (1994) 27, en su libro “Introduction to Graph Theory”,en donde
señala sobre el algoritmo de Fleury para hallar un circuito Euleriano en un grafo
simple G= (V, E) Euleriano:
Comenzamos de un vértice cualquiera v, elegimos una arista e1 = {v, u},
entonces formamos la cadena v, u. Y luego en u, elegimos una arista e2 = {u,
w}
y formamos la cadena v,u,w y así sucesivamente.
Para que la cadena obtenida al final del proceso sea euleriana en cada paso i
debemos elegir para continuar la cadena, una nueva arista ei tal que si
quitamos esta arista en el grafo G [ E- { e1, ...., ei-1 } ] se obtenga un grafo
conexo.
27
RALPH GRIMALDI. Addison Wesley. (1994).Introduction to Graph Theory. Editorial Prentice Hall. pág. 115
Pág. 22
SÁEZ, Alfonso 28, en su texto “Matemática discreta” de la Universidad de
Valladolid, en donde señala sobre el algoritmo de Fleury (Grafos Eulerianos)
que permite encontrar una trayectoria o circuito de Euler. Y un puente es una
arista tal que al quitarla del grafo, el grafo se convierte en un grafo disconexo.
Los pasos a seguir en el algoritmo de Fleury para encontrar una trayectoria de
Euler son:
1. Verificar que el grafo cumpla con los criterios de grafos Eulerianos
(todos los vértices deben tener grado par, salvo dos como mucho).
2. Escoger un vértice de grado impar. En caso de que no exista, se
puede escoger cualquier vértice.
3. En cada paso, recorre cualquier arista disponible, eligiendo un puente
solo cuando no haya alternativa. Al recorrer la arista borrarla y
continuar el proceso hasta que todos los vértices tengan grado cero.
M. ALDOUS, Joan, ROBIN J. Wilson (2000)29. En el Capítulo 3señala
sobre El Algoritmo de Fleury, en donde describe cómo construir un camino
Euleriano en un gráfico de Euler dado combinando ciclos. Otra manera de
construir un camino Euleriano es usar el siguiente algoritmo.
Algoritmo de Fleury
Paso 1.- Se comienza en un vértice cualquiera �� .
(O en un impar si hay dos vértices impares)
Paso 2.- Si se ha construido el camino �� �� �� ��... �� �� con
aristas distintas, se elige la arista siguiente �� con las
condiciones:
28 POBLACIÓN SÁEZ, Alfonso Jesús, Matemática discreta (Universidad de Valladolid). pág. 40.
29 M.ALDOUS, Joan, ROBIN J. Wilson (2000) Graph and Aplications.Editorial Springer, Londres.pág. 202
Pág. 23
(1) �� incidente con �
(2) no ser puente en el grafo G−{�� �� �� … � }
(Salvo que no haya alternativa).
Paso 3.- Se sigue hasta que el camino contenga todas las aristas.
RAMOS, S. y SARAVIA 30,en su libro” Investigación Operativa Teoría de
Grafos o Redes” de la Universidad pontificia Comillas, España. En desarrolla
sobre el Algoritmo de Fleury.
Si una red es conexa y tal que todos sus vértices son de grado par es
posible recorrer todas sus aristas de un solo trazo sin necesidad de corregir el
trayecto según el siguiente esquema:
� Salir de un vértice cualquiera.
� Cada vez que recorramos una arista procedemos a tacharla.
� Cuando todas las aristas que inciden en un vértice han sido
“tachadas”, “tachamos” dicho vértice.
� No utilizar nunca una arista que, en el momento considerado, sea
un itsmo.
Ross y C. Wright (1990) 31 en su texto “Matemáticas Discretas” en donde
señala sobre los pasos de algoritmo de Fleury.
Paso 1. Empiece en cualquier vértice V de valencia impar si es que lo
haya. Si no lo haya empiece en cualquier vértice V. Sea Vs = [ V
] y sea Es= [ ].
Paso 2. Si no hay ninguna arista que pase por V, pare.
30
RAMOS A., L. Pedro, SÁNCHEZ P., SARAVIA A., V. Begoña. Investigación Operativa Teoría de Grafos o Redes. Universidad pontificia Comillas, España. . pág. 69.
31 K. Ross y C. Wright (1990) Matemáticas Discretas, pág. 423
Pág. 24
Paso 3. Si hay exactamente una arista que pase por V, digamos arista
(E, [V, W]), entonces sustraiga a arista E del grafo A (G) y a V
sus vértices V(G) y siga con el paso 5.
Paso 4. Si hay más de una arista en V, elija una de ellas, digamos E, tal
que arista (E, [V, W] ), de tal modo que su eliminación no
desconecte la gráfica; quite entonces a E de A(G).
Paso 5. Añada W al final de � , añada E al final de Es, reemplace V por
W y regrese al paso 2.
Según el autor MICHA (2003) 32 , define las reglas básicas del algoritmo de
Fleury para encontrar circuitos de Euler.
Regla 1. Cerciórate que la grafica 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!)
BORREGO R., Rafael y R. DOMÍNGUEZ. Daniel 33 en el Proyecto fin de
carrera de la Escuela Técnica Superior de Ingeniería Informática Departamento
Matemáticas Aplicadas I.
1. “El algoritmo de Fleury trata de buscar una trayectoria euleriana en un
grafo conexo y en el que no existen más de dos vértices de grado impar.
2. La implementación del algoritmo se ha realizado mediante
técnicas de programación dinámica combinada.
32
MICHA,E;(2004) Ob. Cit. Pág. 38. 33 BORREGO R., Rafael y R. D. Daniel, Proyecto fin de carrera Escuela Técnica Superior de Ingeniería Informática Departamento Matemáticas Aplicadas I.pag. 174.
Pág. 25
3. La heurística seguida para encontrar la trayectoria euleriana es
la siguiente. Se comprueba que previamente que el grafo
satisface las condiciones para que exista dicha trayectoria.
4. Seguidamente no situamos en unos de los vértices impares si
existen o en caso contrario uno cualquiera de grado par.
5. A continuación de todos los vértices adyacentes respecto al que
estamos situados escogemos el primero según orden existente en la
matriz de adyacencias y al ser posible que no sea una arista puente
salvo que no exista ninguna otra alternativa.
6. Una vez seleccionada la arista, esta no vuelve a tenerse en cuenta
por lo que es como si la hubiéramos eliminado del grafo.
7. Repetimos este proceso hasta recorrer todas las aristas del grafo,
pudiendo repetir vértices.
Según SARAVIA (1996) 34El algoritmo de Fleury permite obtener los ciclos
Eulerianos para algunas redes particulares. Así, si A es una red conexa,
múltiple v tal que todos sus vértices son de grado par podemos recorrer
todas las aristas de un solo trazo, sin que tengamos que corregir nuestro
trayecto, si seguimos la siguiente regla:
� salir de un vértice cualquiera,
� cada vez que recorramos una arista procederemos a tacharla.
� no utilizaremos nunca una arista que, en el momento considerado,
sea un istmo; es decir, cuya supresión genere dos componentes co-
nexas cada una de las cuales tenga al menos una arista.
Gracias a los teoremas de Euler es posible saber si un grafo dado tiene
trayectorias o circuitos de Euler, lastimosamente estos teoremas no indican la
manera de encontrar dicho recorrido. En esta sección se mostrarán una serie
de instrucciones muy sencillas conocidas como El algoritmo de Fleury las
cuales permitirán encontrar una trayectoria o circuito de Euler en caso de que
este exista. Una definición preliminar necesaria es la de puente. Un puente es
una arista tal que al quitarla grafo se convierte en un grafo disconexo.
34
SARAVIA V. Ángel (1996).Investigación Operativa, editorial Ortega, España .pág. 28.
Pág. 26
Los pasos a seguir en El Algoritmo de Fleury para encontrar una trayectoria
de Euler son los siguientes:
1. Verificar que el grafo cumpla con las hipótesis expuestas en los
teoremas trayectorias de Euler.
2. Escoger un vértice de grado impar. En caso de que no exista, se
puede escoger cualquier vértice.
3. En cada paso, recorre cualquier arista disponible, eligiendo un puente
solo cuando no haya alternativa. Al recorrer la arista borrarla y
continuar el proceso hasta que todos lo vértices tengan grado cero.
3.3 EJEMPLOS DE ALGORITMO DE FLEURY
Ilustraremos el uso del algoritmo del Fleury considerando algunos ejemplos.
que a continuación se explica con el siguiente ejemplo:
EJEMPLO 01:
La grafica de la figura tiene todo sus vértices de grado para, y por tanto tiene al menos un circuito de Euler.
Inicio: Elegimos el vértice A.
Pudimos haber elegido cualquier vértice
B
D
C E A G
F
H
Pág. 27
Paso 1: Elegimos la arista AB.
Desde a hay tres aristas disponibles. La arista AB, la arista BC y la arista
AD.como ninguna es puente, se puede elegir cualquier.
Paso 2: Elegimos la arista BC.
No hay alternativa.
Paso 3: Elegimos la arista CA.
Desde C hay dos aristas disponibles. La arista CA y la arista CD.
Paso 4: Elegimos la arista AD.
Desde A hay dos aristas disponibles. La arista AD y la arista AG.
B
A
B
C A
B
C A
B
A
D
C
Pág. 28
Paso 5 y 6: Elegimos la arista DC Y CE.
No hay alternativa en cada paso.
Paso 7: Elegimos la arista EG.
Desde E hay tres aristas disponibles. La arista EG, la arista EF y la arista EA. Como ninguna es un puente, se puede elegir cualquiera.
Paso 8: Elegimos la arista GF.
Desde C hay tres aristas disponibles. La arista GF y GH no son puentes y se puede elegir cualquier de ellas. La arista GA no se puede elegir porque es puente.
Paso 9, 10 11 y 12: Elegimos la arista FE, EH, HG y GA.
No hay alternativa en cada caso.
B
C A
B
A
B
C E E G
F
E G
B
A C
D
Pág. 29
Como ya no podemos seguir, ¡hemos terminado! El circuito de Euler que
obtuvimos es: A, B, C, A, D, C, E, G, F, E, H, G, A que es uno de
los varios circuitos posibles.
EJEMPLO 02:
La grafica tiene de la figura tiene un circuito de Euler. Sabemos esto porque
todo los vértices tiene grado par .aunque esta gráfica es muy simple y
podemos encontrar a un circuito de Euler por ensayo y error, lo encontraremos
usando el algoritmo de Fleury para entender cómo funciona
Inicio: Elegimos el vértice F.
Paso 1: Elegimos la arista FC.
B
D
C E A G
F
H
A B
C D E F
A B
C D E F
Pág. 30
Paso 2: Elegimos la arista CD.
Paso 3: Elegimos la arista DA.
Paso 4: Elegimos la arista AC.
A B
C D E F
A B
C D E F
A B
C D E F
Pág. 31
Paso 5: Elegimos la arista CE.
Paso 6, 7,8 y 9: Elegimos la arista EA, AB, BD, y DF.
Como ya no podemos seguir, ¡hemos terminado! El circuito de Euler que
obtuvimos es: F, C, D, A, C, E, A, B, D, F que es uno de los varios circuitos
posibles.
3.4 ALGORITMO DE FLEURY PARA ENCONTRAR CIRCUITO DE EULER
Nos preguntamos ¿Qué pasa en el caso de trayectoria de Euler?
MICHA (2003)35, sostiene Si una grafica conexa tiene exactamente dos vértices
de grado impar, entonces sabemos por los teoremas de Euler que no tiene un
circuito Euler pero si tiene al menos una trayectoria de euler que empieza y
termina en dichos vértices. Podemos encontrar una trayectoria de euler usando
una versión modificada del algoritmo de Fleury.
35
MICHA, E. (2004) Ob. Cit. Pág. 42-43.
A B
C D E F
A B
C D E F
1
2
3
4
5
6
7
8
9
Pág. 32
Esta modificación consiste:
Regla 1 modificada: cerciórate que la gráfica sea conexa y que tenga
exactamente dos vértices de grado impar.
Regla 2 modificada: elige como vértice inicial uno de los vértices de
grado impar.
¡Cuando se apliquen estas reglas, el recorrido terminara en el otro vértice de
grado impar!
3.4.1 EULERIZACION Y SEMI- EULERIZACION DE GRAFICA S
Supongamos que necesitamos diseñar una ruta eficiente para un camión
recolector de basura que debe recorrer todas las calles del mapa de la
siguiente gráfica
A B c
D
E G
En donde cada arista representa una calle y cada intersección de calles está
representada por un vértice, constituye un modelo matemático para el
problema.
En términos del grafica se puede diseñar la ruta más eficiente para camión
recolector de basura en:
Entonces la pregunta es ¿podemos encontrar un circuito de Euler o una
trayectoria de Euler en la gráfica?
F
Pág. 33
Como la gráfica tiene cuatro vértices de grado impar (A, B, F y G),la respuesta
es no.
¿Cómo encontrar una ruta que cubra todas las calles y en la que el número de
calles que tenga que volver a recorrer sea el menor posible?
En la siguiente grafica se muestra que se obtiene al agregarle una copia de
cada de las aristas AB y FG a la gráfica anterior.
A 1 B 6 c
2
8 12 D 5
3 11
E G
El efecto agregar dos aristas al gráfica es el de eliminar los cuatro vértices de
grado impar. Todos los vértices de la gráfica son de grado par y por tanto tiene
un circuito de Euler.
En este recorrido estamos viajando a lo largo de todas las aristas de la
grafica, pero pasando dos veces por las aristas AB y FG. A pesar de que éste
no es un circuito de Euler para la grafica original, es un circuito que describe el
recorrido más eficiente (con menor de aristas duplicadas)que cubre toda la
gráfica y que inicia y termina en el vértice A.
F 9 4
10
7
Pág. 34
3.5 PSEUDOCODIGO DEL ALGORITMO DE FLEURY .
Bondy 36 en “Graph Theory”,donde da sobre programación de el Algoritmo
de Fleury.
1: nodo = SeleccionarNodo( ConjuntoNodos) (La función
“SeleccionarNodo” elegirá un nodo de grado impar si es posible)
2: WHILE (ConjuntoNodos ≠ VACÍO ) DO
arista = SeleccionarAristaAdyacenteNodo(nodo) (La función
“SeleccionarAristaAdyacenteNodo” elegirá una arista puente
solamente como último recurso)
3: ConjuntoAristas = ConjuntoAristas – arista
ConjuntoNodos=QuitarVercicesCardinalidadCero(ConjuntoNodos)
IF ConjuntoNodos ≠ VACÍO THEN
nodo = SeleccionarNodoAdyacenteArsita( arista, ConjuntoNodos)
END IF
END WHILE
4: FIN DEL ALGORITMO.
3.6 COLORACIÓN DE GRAFO CON EL ALGORITMO DE FLEURY
La Coloración de Grafo con el Algoritmo de Fleury 37. Para un camino de Euleriano:
1. Escoge uno de los dos vértices de grado impar como el arranque el punto.
2. Viaje encima de cualquier borde en cuyo levantamiento no irrumpirá el gráfico los componentes desconectados.
3. Color que el borde simplemente cruzó, y entonces viaja encima de cualquier borde de quien el levantamiento no romperá el subalterno-gráfico restante en los componentes desconectados.
4. Repite hasta que todos los bordes estén coloreados (es decir cruzó).
36 J. A. Bondy, U. S. R. Murdy.Graph Theory. Pag. 87 37 Eulerian Paths and Circuits, Reading: Lecture Notes x9.3; Epp x11.2 (mayo 2011) slide 14.
Pág. 35
3.7 PROBLEMA DEL CARTERO
3.7.1 ALGORITMO DEL CARTERO CHINO
Es una aplicación de la solución de redes de flujo con arcos dirigidos. Hay un
número de rutas que se pueden trazar uniendo una serie de vértices de tal
manera de visitarlos a todos al menos una vez.38
Euler planteó el problema de trasladar un desfile militar atravesando los
siete puentes de su ciudad natal. Estudiando la configuración de los puentes y
las calles encontró que no existía solución factible y propuso una serie de
leyes matemáticas para hallar todos los recursos existentes en una red. Así se
ha definido como un circuito Euler a toda ruta que, sea continua, que cubra
cada arco de la red al menos una vez y que regrese a su punto de partida.
Si los arcos no son unicursivos, (en una sola dirección) se pueden
utilizar reglas muy sencillas para saber si hay una solución de ruta Euler.
Si el número de vértices en la red es un número impar, existe una solución tipo
Euler; de ser un número par, no existe dicha solución y algunos arcos deben
ser trazados más de una vez.
Fue una revista china de matemáticas donde se planteó por primera vez
una solución óptima a un circuito Euler. Describiendo las actividades de un
cartero en caminar su ruta postal (en otras palabras "la ruta del cartero chino").
En este problema la ruta buscada es la que reduce la distancia viajando a lo
largo de las calles (arcos) un sentido único y de regreso a su central de
correos.
Suposiciones en que se basan estos algoritmos.
38
Curso de Investigaciones de operaciones II (2007-I), Facultad de Ingeniería Industrial y de Sistemas. Universidad Nacional de Ingeniería.pag.9.
Pág. 36
1. Los costos unitarios de transportación son independientes de la cantidad
de residuos sólidos transportados.
2. Se cuenta con un número óptimo de sitios de disposición final o de
estaciones de transferencia.
3. La generación de residuos sólido es fija, no variable y siempre fijada en
un sitio.
4. No existen restricciones de capacidad en el sitio de disposición final o
estación de transferencia al aceptar los residuos sólidos recolectados.
5. El tiempo en que la solución óptima es aplicable es limitado (o en otras
palabras no está incluido el factor tiempo en la formación del algoritmo).
3.7.2 APLICACIÓN UTILIZANDO EL ALGORITMO DEL CARTE RO.
Hallar la ruta optima de entrega de correspondencia partiendo del punto A
abarcando todos los nodos y regresando al punto de partida, utilizando un
tiempo y costo óptimo.39
En el diagrama adjunto mostramos el circuito de recorrido del cartero.
39
Curso de Investigaciones de operaciones II (2007-I). Ob. Cit. Pág. 17.
Pág. 37
Solución:
3.8.3 DIAGRAMA DEL ALGORITMO DEL CARTERO CHINO
Este diagrama muestra que existe otra alternativa para resolver el algoritmo del
cartero utilizando otros algoritmos, como el de Fleury, Edmonds, Diestra, Euler,
etc.40
40
Curso de Investigaciones de operaciones II (2007-I). Ob. Cit. Pág. 24.
Pág. 38
Pág. 39
CONCLUSIONES
Luego de entender la teoría presentada en las secciones anteriores es posible
argumentar una respuesta a los teoremas de Euler sobre el algoritmo de
Fleury se concluye que:
Los teoremas de Euler nos proporcionan criterios muy simples para decidir si
una grafica posee una trayectoria o un circuito de Euler. Desafortunadamente
los teoremas de Euler no nos ayudan a encontrarlos en el caso de que si
existan.
El algoritmo de Fleury nos instruye que viajemos por un puente solo como
último recurso. Es decir, solamente podemos usar un puente cuando este sea
la única arista que se pueda usar para continuar el recorrido.
Gracias a los teoremas de Euler es posible saber si un grafo dado tiene
trayectorias o circuitos de Euler.
El algoritmo de Fleury las cuales permitirán encontrar una trayectoria o circuito
de Euler en caso de que este exista. Una definición preliminar necesaria es la
de puente.
Pág. 40
RECOMENDACIONES
Se sugiere a los docentes del curso de estructuras descrestas a seguir
fomentando la investigación, y a que ello ayuda al estudiante de
ingeniería de sistemas y áreas a fines a su formación profesional.
Así mismo a los docentes de la escuela profesional de ingeniería de
sistemas, que tiene en sus cursos respectivamente que desarrollan en
las aulas pedagógicas; se hagan las investigaciones para que el
estudiante pueda adecuarse a la competitividad y a la excelencia.
Se sugiere a la dirección de estudios incorporar el curso de
investigación científica, y se realice talleres de investigación.
Pág. 41
BIBLIOGRAFÍA
BORREGO ROPERO, Rafael y RECIO DOMÍNGUEZ, Daniel. (2006). Manual
de algorítmica, Proyecto fin de carrera Escuela Técnica Superior de Ingeniería
Informática Departamento Matemáticas Aplicadas I, universidad de Sevilla-
España.
CALCEDO B., Alfredo, W. DE GARCIA G. y M. P. R. María (2010). Introducción
a la teoría de grafos, primera Edición, ediciones Elizcom, Quindío - Armenia.
Eulerian Paths and Circuits, Reading: Lecture Notes x9.3; Epp x11.2 (mayo
2011)
J. A. Bondy, U. S. R. Murdy.Graph Theory
K. Ross y C. Wright (1990) Matemáticas Discretas, Editorial Prentice Hall-
Mexico.
M. ALDOUS, Joan, ROBIN J. Wilson (2000) Graph and Aplications.Editorial
Springer, Londres-Inglaterra.
M.G.Sánchez–Torrubia,C.Torres–Blanc, J. Castellanos, Defining eMathTeacher
Tools and Comparing them with e&bLearning web based tools. Proceedings of
the 2007 International Conference on Engineering and Mathematics (ENMA
2007). (Bilbao, Spain, 7-9 July 2007).
MALVA A.,S. Ingrid C. , Viviana y F. Yanina. (2005).Matemática Discreta con
aplicaciones a las ciencias de la programación y de la computación. Primera
Edición, Universidad nacional de Litoral, Santa fe-Argentina.
MICHA, Elías (2003).Matemáticas Discretas. Editorial Limusa Grupo noriega
editores. Mexico.
Pág. 42
POBLACIÓN SÁEZ, Alfonso Jesús. Matemática discreta (Universidad de
Valladolid)
RALPH GRIMALDI. Addison Wesley.(1994). Introduction to Graph Theory.
Editorial Prentice Hall-México.
RAMOS A., L. Pedro, SÁNCHEZ P., SARAVIA A., V. Begoña. Investigación
Operativa Teoría de Grafos o Redes. Universidad pontificia Comillas, Madrid-
España.
SALAZAR GONZALES, J. Pablo. (2001).Programación Matemática, Ediciones
de santos, Madrid-España.
SARAVIA VIEJO, Ángel (1996).Investigación Operativa. Universidad pontificia
comillas, Editorial Ortega, España
Pág. 43
INDICE
Dedicatoria……………………………………………………………………. Presentación…………………………………………………………………. Introducción……………….…………………………………………………. Prologo …….………………………………………………………………….
CAPITULO I :INTRODUCCION A GRAFOS 1.1 Teoría de grafos ………………………………………………………. 1.2 ¿Qué es un grafo?........................................................................ 1.3 Elementos……………………………………………………………… 1.4 Estructura……………………………………………………………… 1.5 Grafos orientados ……………………………………………………. 1.6 Grafos no orientados …………………………………………………
CAPITULO II:CIRCUITO EULERIANO
2.1 Definiciones básicas……………………………………………… 2.2 Definiciones básicas………………………………………………. 2.2.1 Grado…………………………………………………………… 2.2.2 Vértices adyacentes…………………………………………… 2.2.3 Trayectoria……………………………………………………… 2.2.4 Camino…………………………………………………………. 2.2.5 Ciclo……………………………………………………………. 2.2.6 Circuito……………………………………………………. 2.2.7 Grafo conexo……………………………………………… 2.2.8 Grafica disconexa…………………………………………….. 2.2.9 Circuito Euleriano…………………………………………….. 2.2.10 Trayectoria Euleriana……………………………………….. 2.3 Puentes de Konigsberg…………………………………………..
CAPITULO III:ALGORITMO DE FLEURY 3.1 Trayectorias y circuitos Eulerianos con Fleury …………………….. 3.1.1 Teorema 1.- existencia de trayectorias de Euler………………….. 3.1.2 Teorema 2. Existencia de circuitos de Euler……………………… 3.2 Algoritmo de Fleury (definiciones bibliogarficas).…………………. 3.3 Ejemplos de algoritmo de Fleury……………………………………… 3.4 Algoritmo de Fleury para encontrar circuito de Euler……………….. 3.4.1 Eulerizacion y Semi- Eulerizacion de graficas……………………… 3.5 Pseudocódigo del algoritmo de Fleury……………………………….. 3.6 Coloración de grafo con el algoritmo de Fleury ……………………. 3.7 Problema del cartero …………………………………………………. 3.7.1 Algoritmo del cartero chino…………………………………………. 3.7.2 Aplicación utilizando el algoritmo del cartero…………………….. 3.7.3 Diagrama del algoritmo del cartero chino…………………………. Conclusiones………………………………………………………………… Recomendaciones…………………………………………………………… Bibliografía……………………………………………………………………
Pág. 2 Pág. 3 Pág. 4 Pág. 5
Pág. 7 Pág. 7 Pág. 8 Pág. 8 Pág. 9 Pág.10
Pág.13 Pág. 13 Pág.13 Pág.13 Pág.13 Pág.14 Pág.14 Pág.15 Pág.15 Pág.15 Pág.15 Pág.16 Pág.16
Pág.19 Pág.19 Pág.20 Pág.20 Pág.26 Pág.31 Pág.32 Pág.33 Pág.34 Pág.35 Pág.35 Pág.36 Pág.37 Pág.39 Pág.40 Pág.41