Grafos

UNIVERSIDAD NACIONAL DEL ALTIPLANO PUNO FACULTAD DE INGENIERIA MECANICA ELECTRICA, 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

Dedicatoria

A mis padres, mis hermanos quienes siempre me han brindadoel 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. 2

INTRODUCCIÓN

Unade 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, entoncessabemos 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 unatrayectoria 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. 3

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 elestudiante 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 degraficas. 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ásadelante. 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. 4

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 elaná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...